Baekjoon 22

[Baekjoon] 움직이는 미로 탈출(python)

https://www.acmicpc.net/problem/16954 문제 접근 BFS를 이용하여 시작점부터 도착점까지 이동할 수 있는지 판별하는 문제이다. 일반적인 BFS 문제와 다른점은 4방향 탐색이 아닌 현재위치를 포함하여 9방향 탐색을 하는 것이고 탐색을 하는 중간에 배열의 상태가 바뀐다는 것이다. 풀이 과정 9방향 BFS를 구현해주면 된다. 일반적으로 BFS를 구현하면 아래처럼 구현할 것이다. def bfs(x, y): while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if ( nx = 8 or ny = 8 or chess[nx][ny] == "#" or visited[n..

Baekjoon 2022.10.18

[Baekjoon] 로고(python)

https://www.acmicpc.net/problem/3108 문제 접근 이 문제를 풀기 위한 아이디어는 사각형끼리 교점이 있으면 같은 그룹으로 묶을 수 있고 같은 그룹이면 연필을 올리는 연산인 PU를 하지 않고도 한번에 그릴 수 있다는 것이었다. 또 시작 위치는 원점이고 방향은 위쪽을 보고 있으므로 사각형 그룹이 원점에서 바로 그릴 수 있으면 PU 명령을 할 필요가 없으나 그렇지 않은 경우는 반드시 PU 명령을 해야한다. 하지만 사각형을 그룹핑하기 위한 방법이 떠오르지 않아 풀이를 참조하여 Union-Find(합집합 찾기)를 이용하면 된다는 것을 알았다. 즉 Union-Find를 통해 사각형을 그룹핑하고 그룹의 갯수를 구하면 PU 명령을 실행해야할 횟수를 알 수 있다. 풀이 과정 이 문제의 풀이 코..

Baekjoon 2022.10.17

[Baekjoon] 파일 합치기(python)

https://www.acmicpc.net/problem/11066 문제 접근 DP 문제이다. i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면서 문제를 해결했다. 풀이 과정 앞서 말한 것처럼 i~j까지의 파일을 합치는데 드는 최소 비용을 dp배열에 저장하면 된다. 예를 들어, 0~2까지의 파일을 합치는 데 드는 최소 비용은 [0, 1~2]와 [0~1, 2] 중 작은 값이 될 것이다. 0~3까지의 파일을 합치는 경우는 [0, 1~3], [0~1, 2~3], [0~2, 3] 중 작은 값이다. 이렇게 최소 비용이 드는 임시 파일의 케이스를 찾고 실제 파일을 합치는데 드는 비용을 더해주면 파일을 합칠 때 드는 최소 비용을 구할 수 있다. 1. 임시 파일의 크기 조합을 구한다 for j in r..

Baekjoon 2022.10.17

[Baekjoon] 배열에서 이동(python)

https://www.acmicpc.net/problem/1981 문제 접근 풀이 방법이 떠오르지 않아 문제의 알고리즘 힌트와 질문 검색을 통해 문제를 해결하였다. 이 문제는 이분탐색 + BFS로 해결할 수 있다. 최댓값과 최솟값의 차이를 이분탐색을 통해 찾고 BFS를 통해 그 값이 가능한지 탐색하면 된다. 풀이 과정 이분 탐색을 통해 가능한 값을 찾는 것이 핵심! while left end: continue if bfs(start, end): return True return False 마지막으로 BFS를 통해 (0, 0)에서 (n-1, n-1)까지 도달할 수 있는지 검사하면 된다. def bfs(start, end): dx = [-1, 0, 0, 1] dy = [0, -1, 1, 0] visited ..

Baekjoon 2022.10.09

[Baekjoon] 로봇 청소기(python)

https://www.acmicpc.net/problem/4991 문제 접근 이 문제는 BFS + 순열을 이용한 문제였다. 더러운 칸의 갯수가 10개를 넘지 않기 때문에 최대 10! 만큼만 연산하면 되었기 때문이다. 그래서 탐색할 더러운 칸의 순서를 permutations 연산을 통해 순열을 구하고 BFS를 통해 하나씩 탐색하면서 지나치는 칸의 갯수를 세어주었다. 하지만 BFS를 통해 매번 칸의 갯수를 연산하는 방식은 시간초과를 해결할 수 없었고, 메모이제이션(Memoization)을 통해 각 더러운 칸 사이를 탐색할 때 지나치는 칸의 갯수를 저장하여 매번 연산하지 않도록 수정했다. 오답 코드 import sys from itertools import permutations from collections..

Baekjoon 2022.10.09

[Baekjoon] 앱(python)

https://www.acmicpc.net/problem/7579 문제 접근 최근에 풀었던 평범한 배낭과 똑같은 문제이다. 평범한 배낭에서 N개의 물품을 합해서 K만큼의 무게를 확보했던 것과 매칭하면 이 문제에서는 N개의 앱을 합해서 M만큼의 메모리를 확보해야 하는 것이다. 단, 이 문제에서는 앱을 비활성화했을 경우의 비용을 최소화하도록 해야 한다. 그렇다면 앱들을 비활성화했을 경우의 비용별 최대 메모리 바이트 수를 dp 배열에 저장하여 문제를 풀도록 하면 된다. 풀이 과정 dp 점화식은 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i])이다. 테스트 케이스를 기준으로 모든 앱들을 비활성화할 경우 총 비용은 15이다. dp[N][Cost] ..

Baekjoon 2022.10.05

[Baekjoon] 미네랄(python)

https://www.acmicpc.net/problem/2933 문제 접근 시뮬레이션 + BFS로 구현하는 문제이다. 전체적으로 문제풀이 과정은 문제에서 제시하는대로 따라서 구현하면 된다. 문제의 핵심 로직은 미네랄 클러스터가 막대기를 던질 때 미네랄이 파괴되면서 클러스터가 분리되는지 확인하는 것이다. 미네랄 클러스터는 동서남북으로 인접한 경우만 클러스터로 인정되므로 가장 밑줄의 미네랄들을 BFS나 DFS로 인접한 4방향을 탐색하고 탐색이 종료된 후에 아직 탐색되지 않은 미네랄이 존재하는 경우는 막대기에 의해 분리된 클러스터로 간주하면 된다. 풀이 과정 문제 풀이 과정은 미네랄 파괴 -> 클러스터 체크 -> 분리된 클러스터 낙하를 구현하면 된다. 1. 미네랄 파괴 for i, height in enum..

Baekjoon 2022.10.02

[Baekjoon] 행렬 제곱(python)

https://www.acmicpc.net/problem/10830 문제 접근 N x N 행렬의 곱셈을 구하는 코드는 보통 아래처럼 구현할 것이다. for i in range(N): for j in range(N): for k in range(N): matrix[i][j] += a[i][k] * b[k][j] 시간 복잡도는 O(N^3)이고 N x N 행렬의 B 제곱을 구하는 것이니 O(BN^3)이 될 것이다. 당연히 시간 초과가 날 것이다... 그렇다면 어떻게 효율적으로 행렬의 제곱을 할 수 있을까? 행렬 제곱은 N x N x N... x N처럼 순서대로 처리할 필요는 없다. N x N x N = N x N^2 N x N x N x N x N = N^2 x N^3 와 같이 전체 제곱 수를 반으로 분할하여..

Baekjoon 2022.09.28

[Baekjoon] 백조의 호수(python)

https://www.acmicpc.net/problem/3197 문제 접근 아주 단순한 구현문제인 줄 알았다. 그래서 백조끼리 만날 수 있는지 검사하는 함수와 물의 가장자리에 붙어있는 얼음을 녹이는 함수 두 개만 짜면 되는 줄 알았다. 문제에 테스트케이스가 모두 정답이 되어 제출해봤는데 역시는 역시인가.. 처음 문제를 풀었던 방식은 이렇다. 1) 백조끼리 만날 수 있는지 BFS를 통해 검사 2) lake 배열을 매번 체크하면서 물의 가장자리에 있는 얼음을 녹임 def is_can_meet_swan(): visited = [[False] * C for _ in range(R)] start_x, start_y = swans[0] end_x, end_y = swans[1] q = deque() q.appen..

Baekjoon 2022.09.25