코딩 검색 결과
271 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 2178번: 미로 탐색 (Python)

접근 문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다. 예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸을 탐색하게 되는데, 이 칸들에 지금 칸 숫자에 1을 더한 2를 입력해준다. 이 다음 탐색에서는 주변 칸들에 3을 입력하는 식으로 진행하게 되면 마지막 칸에 최단거리를 표시하게 된다. 코드 import sys def bfs(x, y): global cnt dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] q = [[x, y]] visited[x][y] = 1 while q: now = q.pop(0) for i in range(4): nx = now[0] + dx[i] ny = now[..

2021. 4. 11. 17:20
코딩/백준 (Python)

백준 2667번: 단지번호붙이기 (Python)

접근 DFS 혹은 BFS 알고리즘을 이용하여 한 단지로 묶일 수 있는 집을 탐색하여 단지를 지정해준다. 알고리즘 기본 코드 참고 : 2021.04.11 - [코딩/백준 (Python)] - 백준 1260번: DFS와 BFS (Python) 백준 1260번: DFS와 BFS (Python) 접근 DFS는 깊이 우선 탐색, BFS는 너비 위주 탐색이다. DFS는 첫번째 이웃으로 이동하고나서, 해당 이웃을 기준삼아 다시 또 첫번째 이웃으로 이동하고 동일하게 계속 진행하여 더이상 연결이 되 ca.ramel.be 아래 코드에서는 DFS 알고리즘을 이용하여 풀었다. 코드 import sys n = int(sys.stdin.readline()) array = [list(map(int, sys.stdin.readlin..

2021. 4. 11. 11:24
코딩/백준 (Python)

백준 1260번: DFS와 BFS (Python)

접근 DFS는 깊이 우선 탐색, BFS는 너비 위주 탐색이다. DFS는 첫번째 이웃으로 이동하고나서, 해당 이웃을 기준삼아 다시 또 첫번째 이웃으로 이동하고 동일하게 계속 진행하여 더이상 연결이 되지 않을 때까지 진행하고 돌아와 두번째 이웃으로 진행한다. BFS는 첫번째 기점에서 연결된 모든 이웃을 탐색한 후에, 첫번째 이웃에서 같은 작업을 반복한다. 코드 import sys n, m, start = map(int, sys.stdin.readline().split()) lines = [[0 for _ in range(n + 1)] for __ in range(n + 1)] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) lines[a][..

2021. 4. 11. 01:13
코딩/백준 (Python)

백준 7579번: 앱 (Python)

접근 메모리가 아닌 코스트를 기준으로 하는 냅색 문제이다. 길이가 sum(cost) + 1 인 리스트 n + 1 개를 가진 dp를 만들어 다음과 같이 채워나간다. dp[i][j] = i 번째까지의 앱과 j의 코스트를 가지고 확보 할 수 있는 최대 메모리 값 cost[i] > j 일 경우 cost 부족으로 i 번째 앱 비활성화 불가능 그렇지 않을 경우 dp[i - 1][j] 와 dp[i - 1][j - cost[i]] + memory[i] 값 중 최대값 (j 코스트로 확보할 수 있는 최대 메모리) 순환하면서 최초로 목표 메모리를 넘는 j 값을 저장해준다. 이 과정의 일부를 표로 표시하면 다음과 같이 순환하게 된다. cost 0 1 2 3 4 5 6 7 memory 0 0 0 0 0 0 0 0 0 30 3 ..

2021. 4. 11. 00:39
코딩/백준 (Python)

백준 2293번: 동전 1 (Python)

접근 dp[m] 에 m 원을 만드는 동전의 조합수를 저장하여 문제를 풀 수 있다. 입출력 예시를 보면, 첫 동전으로 1원이 주어진다. 1원만 가지고 1원부터 10원까지 만들 수 있는 경우의 수는 1개이다. 여기에 2원을 추가하여, 1개 이상의 2원을 이용하여 동전을 구성한다고 생각해보자. 이 때는 1원, 2원을 자유롭게 사용하여 m - 2원을 만든 후 2원을 추가해주면 2원을 1개 이상 사용한 동전 경우의 수를 구할 수 있다. 이러한 방법을 통하여 t 원짜리 동전이 추가될 때 dp[j] += dp[j - i] 점화식을 이용하여 코드를 구성해주면 된다. dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] i = 1 (1) 1 경우 1 1 + 1 경우 1 1 + 1 + 1 경우 1 1..

2021. 4. 10. 12:18
코딩/백준 (Python)

백준 2629번: 양팔저울 (Python)

접근 양팔 저울이 잴 수 있는 무게는 양팔에 올라간 추의 무게의 차이라는 것을 알 수 있다. 예를 들어 무게가 각각 1, 4, 9g인 추가 있다면 첫번째 1g 추를 왼쪽에 올릴 수도 있고, 오른쪽에 올릴 수도 있고, 올리지 않을 수도 있다. 그리고 두번째, 세번째 추 또한 동일하게 3가지 경우의 수를 가진다. 이 모든 경우에 대해 좌우 차이를 구하면 답을 구할 수 있을 것이다. 하지만 이렇게 풀면 당연히 시간이 초과될 것이다. 중복을 줄일 수 있는 방법은 추 무게의 좌우 차이가 중요하다는 것을 생각해보면 된다. 왼쪽이 100g이고 오른쪽이 200g이어도, 왼쪽이 450g이고 오른쪽이 550g이어도 100g의 무게를 측정하는 것은 동일하다. 그리고 그 무게를 구성하는 추의 종류가 어떻게 바뀌더라도 좌우 차..

2021. 4. 8. 22:36
반응형