본문 바로가기

Algorithm/BOJ

 (95)
[BOJ] 2580. 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 해결방법 전형적인 스도쿠 문제이다. 스도쿠 문제를 해결하는 원리만 알면 쉽게 풀 수 있는 문제인데 python3로 제출하면 시간초과가 나왔다. 그렇기에 pypy3로 제출,,, 2차원 배열에서 인덱스 값이 0에 해당하는 인덱스 위치를 zero라는 리스트레 append한다. dfs 백트래킹을 이용해서 탐색을 해야하는데, 1 ~ 9 까지 for문을 돌고 0인 위치에서 행과 열, 3X3 정사각형에 ..
[BOJ] 1987. 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. 해결방법 상하좌우를 이동하면서 배열에 넣고 방문 여부 체크를 하도록 했다. 방문 체크를 하기 때문에 중복으로 들어가는 알파벳이 없고, DFS 재귀를 이용해서 계속적으로 그래프를 탐색할 수 있다. 위를 인지하고 완전 탐색을 이용하여 해결하였는데,,, 시간초과가 떠버렸다.... 아마 이유는 리스트에서 append와 pop을 사용한 문제인 것 같았다. 물론 set()를 이용한 add, re..
[BOJ] 2529. 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 1. 해결방법 완전탐색 백트래킹을 이용하여 문제를 해결하였다. 아이디어는 쉽지만 코드로 옮기는 과정에서 3시간 정도 잡아 먹은 것 같다.. 역시 아직 알고리즘을 더 해야겠다. 각 숫자 0 ~ 9는 하나만 들어가야 하므로, 방문 여부 체크는 반드시 해주어야 하고 첫 번째 숫자는 부등호와 상관없이 s 문자열에 포함되어야 하는 부분을 신경 써주면 된다. 가장 중요한 부분은 부등호에 맞게 큰 값과 작은 값이 들어가야..
[BOJ] 10971. 외판원 순회 2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 해결항법 순회라는 조건이 붙었다. 예를 들어 문제의 N이 4라면 시작점에서 부터 순회를 해야하고 4이기 때문에 정사각형의 모형으로 순회를 할 것이다. 이 점을 유의하고 완전탐색 백트래킹 방법으로 하면 된다. 본인도 문제 이해가 어려웠고, 어떻게 순회하면서 재귀를 돌 것인가에 대해서 고민을 엄청 했다. 이에 관련해서는 코드에서 dfs() for문을 ..
[BOJ] 15686. 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 해결 방법 완전 탐색 (백트래킹) 문제이다. 본인은 dfs말고 조합으로 접근하였다. 물론 두 가지다 하겠지만 순열, 조합 라이브러리를 사용한 경험이 적다보니 완전 탐색 알고리즘에서 다 사용해볼 예정이다. 접근 방식은 치킨집의 위치와 집의 위치를 각 리스트에 저장한다. 먼저 치킨집을 for문 돌고, 다음으로 집을 for문 돈다. 그 전에 조합을 이용해서 M만큼의 치킨집을 ..
[BOJ] 1463. 1로 나누기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 해결방법 DP문제이다. 본인은 DP로 해결해야할지 감은 왔지만 해결을 전혀 하지 못했다... 먼저 [0]을 N + 1만큼 리스트를 만들어준다. [1], [2]의 값은 0, 1로 정해져 있으므로, 2부터 N + 1까지 for문을 돈다 i를 2부터 돌면서 dp[i]의 값을 dp[i - 1]에 + 1을 무조건 해주고, if문으로 2와 3으로 나누어 지는지 차례대로 비교해야한다. 물론 둘다 비교해야한다 비교해서 최솟값을 dp[i]에 갱신한다. 진짜 너무 어려웠다.... DP 공부가 많이 부족한 듯 하다. 2. 정..
[BOJ] 1806. 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. 해결방법 투 포인터를 이용한다. 주의해야될 점은 left, right를 0, 0을 초기 값을 설정해야한다. 0, 1로 설정했더니 첫 인덱스 값이 15가 넘어버리는 테스트 케이스에서 실패를 한 것 같았다. 2. 정답코드 import sys input = sys.stdin.readline N, S = map(int, input().split()) nums = list(map(int..
[BOJ] 4485. 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 출발 점에서 목적 점 까지 가는데 사용하는 최송 비용 : 다익스트라 - 간선, 인접리스트 저장 - 거리 비용 배열 저장 - 힙이 빌때까지 다음 반복 - 힙의 최솟값을 꺼냄 - 상하좌우 이동하면서 최솟값을 갱신 - 해당 노드와 인접한 노드를 인접리스트에서 가져와서 힙에 저장 """ 2. 정답코드 import sys import heapq in..

티스토리툴바