Algorithm/Baekjoon

🗂️ 문제링크: https://www.acmicpc.net/problem/1699 💡 접근법제곱 수는 1, 4, 9, 16 … 등이 있다.항의 최소 개수를 구하기 위해서는 제곱 수를 이용해야 한다. 한 가지 예시로 12의 경우, dp[12] = min(dp[1] + dp[11], dp[4] + d[8], dp[9] + dp[3])이다.즉, 제곱 수를 기준으로 모든 경우의 수를 계산해서 최소가 되는 값을 저장해야 한다. 😎 내 코드import sysimport mathN = int(sys.stdin.readline())dp = [100000] * (N+1)dp[0] = 0dp[1] = 1for i in range(1, N+1): for j in range(1, int(math.sqrt(i))+1..

🗂️ 문제링크: https://www.acmicpc.net/problem/11727 💡 접근법N=1일 때, 2x1 직사각형을 채우는 방법의 수는 2x1 크기의 타일 하나로 채우는 방법 1가지이다.N=2일 때, 2x2 직사각형을 채우는 방법의 수는 2x1 크기의 타일 2개를 이어붙이는 방법, 1x2 크기의 타일 2개를 이어붙이는 방법, 2x2 크기의 타일 하나로 채우는 방법, 총 3가지이다. N=3일 때, 2x3 직사각형을 채우는 방법은 다음과 같다.2x2 직사각형에 2x1 직사각형을 이어붙인다.2x1 직사각형에 1x2 크기의 타일 2개를 이어붙이거나, 2x2 크기의 타일 1개를 이어붙인다.이때, 2x1 크기의 타일 2개를 이어붙이는 경우의 수는 1번에 포함되기 때문에 카운트하지 않는다.이를 점화식으로..

🗂️ 문제링크: https://www.acmicpc.net/problem/2468 💡 접근법BFS 알고리즘을 통해 기준 높이보다 지역의 높이가 높아 물에 잠기지 않는 영역의 개수를 구한다. 이를 구하기 위해선 BFS 알고리즘을 통해 인접한 지역(상하좌우)을 탐색할 때 방문하지 않았던 위치(not visited[nx][ny])이면서 기준 높이보다 해당 지역의 높이가 높아야 한다(maps[nx][ny] > h). 지도에서 최대 지역의 높이를 찾아 최대 높이만큼 반복하여 안전한 영역의 최대 개수를 구한다. 😎 내 코드import sysfrom collections import dequeN = int(sys.stdin.readline())maps = []max_height = 0for _ in range(..

🗂️ 문제링크: https://www.acmicpc.net/problem/7562 💡 접근법나이트가 이동할 수 있는 범위를 dx와 dy로 생성한다.이후 맵의 크기에 맞게 False로 maps를 초기화하고, deque를 통해 큐를 생성한다. 초기 시작 위치값인 a와 b를 입력받고, maps[a][b]=0으로 초기화한다.while()문을 통해 큐의 맨 왼쪽 값을 pop하면서 나이트가 이동할 수 있는 범위를 모두 탐색한다. 이때 맵을 벗어나지 않으면서 방문한 적 없는 위치일 경우 큐에 현재 위치를 추가하고 maps에 현재 값을 업데이트한다. 이때 업데이트되는 값은 처음부터 지금까지 이동한 횟수를 나타낸다. 만약 종료 위치에 도달했을 경우 큐를 비워 while문을 빠져나온다.최종적으로 이동하려는 위치에 해당..

🗂️ 문제링크: https://www.acmicpc.net/problem/1966 💡 접근법제일 왼쪽의 값을 쉽게 꺼내기 위해 deque를 사용한다. 문서가 몇 번째로 인쇄되는지 횟수를 세기 위해 인덱스를 저장해야 한다. 이를 위해 queue에 튜플 형식으로 (인덱스, 중요도)를 저장한다.while()문을 통해 큐에서 왼쪽에 위치한 값을 하나씩 꺼내고, 만약 그 다음 값들 중 현재 값보다 중요도가 높은 문서가 있다면 다시 큐에 현재 값을 삽입한다. 이때 인쇄가 될 경우 카운트 횟수를 증가시켜야 한다. 따라서 큐에서 현재 값을 꺼낼 때 카운트를 1 증가시키고, 만약 현재 값보다 중요도가 큰 문서를 발견하여 현재 값을 다시 큐에 삽입하게 되면 카운트를 1 감소시킨다. target에 궁금한 문서를 저장해 ..

🗂️ 문제링크: https://www.acmicpc.net/problem/2667 💡 접근법DFS를 사용하여 연결된 집의 개수를 구한다. 이때 dx와 dy 리스트를 통해 현재 위치에서 상하좌우로 이동할 수 있게 하고, 이동한 좌표가 1) 지도 밖을 벗어나지 않는지, 2) 집이 존재하는지, 3) 방문한 적이 없는지를 확인한다. 모든 조건을 만족할 경우 재귀로 DFS를 수행하고, 수행한 횟수를 cnt로 계산한다.해당 값이 단지에 속하는 집의 개수가 된다. 😎 내 코드import sysN = int(sys.stdin.readline())house_num = []visited = [[False] * N for _ in range(N)]maps = []for _ in range(N): maps.appe..

🗂️ 문제링크: https://www.acmicpc.net/problem/1325 💡 접근법BFS/DFS를 사용하여 각 정점에서 이동할 수 있는 정점들의 최대 개수를 구하는 문제이다."A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다." 즉, 방향이 있는 그래프를 만들어 B → A 단방향 그래프를 정의해야 한다. 또한 시간복잡도 제한때문에 Python3가 아닌 PyPy3로 제출해야 성공할 수 있다. 😎 내 코드import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): a, b = map(int, sys..

🗂️ 문제링크: https://www.acmicpc.net/problem/1753 💡 접근법가중치가 자연수인 방향 그래프이므로 최단 경로를 구하기 위해 다익스트라를 사용해야 한다. 또한 거리가 가장 작은 노드를 자동으로 선택하기 위해 우선순위 큐(heapq)를 사용한다. distance의 요소는 모두 INF로 초기화되어 있다. 만약 if distance[now_node]  조건을 만족할 경우 now_node는 이미 방문된 노드이므로 방문 처리를 위한 visited 리스트가 따로 필요하지 않다.또한 해당 조건을 만족할 경우 이미 dist는 distance[now_node]보다 큰 값이기 때문에 dist 값으로는 now_node와 연결된 다른 노드의 최단 거리를 구할 수 없다. 따라서 continue를 ..