네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이과정 BFS를 사용한 이유 처음엔, dfs로 풀고 시간 초과가 났다. 생각해보니 이 문제는 가다가 해당 노드에 더 작은 비용으로 갈 수 있는 경우, 굳이 더 갈 필요가 없어서 버리기 때문에 bfs가 유리하다. dfs를 사용할 경우, 초반에 전체 탐색을 하기 때문에 시간 초과가 나는 것 같다. Priority Queue를 사용한 이유 bfs임에도 priority..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이과정 최단거리 구하기는 보통 bfs, 도착지점까지 경로를 구한다면 dfs를 주로 사용하는 것 같다. 이 문제는 최단거리를 구하는 문제로 bfs를 사용하여 풀었다. 최단거리만큼만 모든 경로를 탐색하기 때문에 최악의 경우(모든 경로 끝까지 전체탐색)을 막을 수 있다. 처음에는 boolean visited[N][M][2]로 3차원배열을 사용해서 visited..

1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. 풀이과정 문제를 처음 봤을 때, BFS를 떠올렸다가 1~3칸 전진과 1(90도)~2(180도)번 전진 처리가 복잡해 DFS로 풀었다. 그런데, 풀고나서 보니 DFS보다 BFS를 썼을 때 더 빠르게 구현할 수 있을 것 같아 BFS로 다시 풀어보았다. 결과적으로 BFS가 메모리, 시간 측면에서 더 효율적이다. 아래 그림은 두 코드에서 사용한 방향 전환할 때, 걸리는 시간을 구하는 방법이다. 동서..

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] q = deque() graph = [] for i in range(m): graph.append(list(..

1. Brute force 브루트 포스는 "완전 탐색 알고리즘"이다. 모든 경우를 다 살펴보고 결과를 도출하기 때문에 100% 정확도를 가진다. 모든 경우를 본다는 것은 해가 존재할 것이라 예상되는 영역 전체를 살펴보는 것으로 기본적인 방법은 아래와 같다. 1) 선형 구조 : 순차 탐색 탐색(Searching) 1. 탐색이란? 탐색은 '데이터를 찾는 방법'을 말한다. 여기서는 '어떻게 찾을까'와 '효율적인 탐색을 위해 어떤 방식으로 데이터를 저장할까'를 고민해야 한다. 정렬과 탐색은 정수를 기준으로 한 yerinpy73.tistory.com 2) 비선형 구조 : 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 그래프(Graph) 1. 그래프 그래프는 정점과 간선으로 구성되어 있다. 그래프는 방향성이 ..

1. 그래프 그래프는 정점과 간선으로 구성되어 있다. 그래프는 방향성이 없는 '무방향 그래프'와 방향성이 있는 '방향그래프'로 나눠볼 수 있다. '각각 정점에서 다른 모든 정점을 연결한 그래프'를 '완전 그래프'라고 하며 아래 두 그래프가 이에 해당한다. 2. 그래프 구현방법 1) 인접 행렬(adjacent matrix) 기반 그래프 2차원 배열을 이용한다. 2) 인접 리스트(adjacent list) 기반 그래프 연결 리스트를 활용하여 그래프를 표현한다. 3. 그래프의 탐색 1. 깊이 우선 탐색 (DFS : Depth First Search) 자신과 연결된 노드들 중 내용이 전달 안 된 하나를 먼저 선택해서 그 사람과 연결된 노드들에게 내용을 다 전달하면, 다음 하나를 또 선택한다. 백트래킹이라고도 하..