개발하는 고라니

17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net [DFS + 동적 프로그래밍] 동적 프로그래밍을 사용하지 않고 DFS만 가지고도 충분히 해결할 수 있는 문제이다. 하지만 메모제이션을 사용하지 않으면 N x M의 각 좌표에서 다른 정점을 타고 탈출할 수 있는지 여부를 확인하기 위해 다른 정점에서 방문했었던 정점을 똑같이 방문하고, 방문하고... 이러한 반복적인 방문을 해결하기 위해, 특정 정점에서 탈출할 수 있다면 탈출할 수 있다고 체크를 한다면, 그 정점을 다시 방문했을 때 '아 여기서는 탈출할..

1501번: 영어 읽기 첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 www.acmicpc.net [문자열 + 해싱] 나는 주어진 단어들을 소인수 분해하듯 알파벳 별로 나누어 배열에 저장하였다. 해싱이라고 하기도 뭐하지만.. 입력으로 주어지는 단어는 알파벳 대소문자로만 이루어져있기 때문에 뜻밖의 변수는 없을 것이다. a의 아스키코드는 97이고, A의 아스키코드는 65이다. 따라서 단어를 받으면 맨 앞, 맨 뒤 글자를 제외한 중간 문자열을 char로 변환해 'a'를 빼주었다. 그러면 0~25가 나올 수도 있고, 음수가 나올 수도 있는데 음수가 ..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net [DFS] 문제의 주어진 입력을 토대로 N x N 크기의 단방향 인접 행렬을 만들었다. 그리고 마지막 줄에서 제거할 노드의 번호를 입력 받는데, 이 때 제거할 노드를 방문 했다고 처리한다. 이제 DFS를 수행할 차례인데, 만약 root 노드와 제거할 노드가 동일하다면 DFS를 수행해서는 안된다. 따라서 root노드와 제거할 노드가 다르다면 DFS를 수행한다. 이때 DFS는 다음과 같은 로직을 갖는다. static void DFS(int x){ visit[x..

17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [BFS] 백준의 숨바꼭질 문제 시리즈 중 거의 마지막 문제. 이전의 문제들과는 더욱 꼬아져있다. 수빈이가 움직이는 것은 동일하지만, 이번엔 동생이 움직인다. 그것도 가속도가 붙어서 움직인다. 일반적인 BFS는 한번 방문한 정점에 대하여 다시는 방문하지 않는다. 예를 들어 수빈이가 15를 2초만에 도착했다고 하자. 동생이 15를 4초만에 도착했다고 했을 때 일반적인 BFS라면 수빈이는 동생을 금방 만날 수 있음에도 불구하고 저..

코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr [Floyd-Warshall] 플로이드 와샬 알고리즘을 수행해서, i번 사람이 j번 사람에게 직접/간접적으로 도달할 수 있는지 체크한 다음, i번 사람이 자기 자신을 제외한 모든 사람에게 도달할 수 있으면 순위를 확실히 알 수 있다. 문제에서 주어진 조건은 간선이 단방향이라는 것을 알려준다. 따라서 주어진 입력을 적절히 이용하여 직접적인 A와 B의 관계를 boolean[ ][ ]에 표현하고 플로이드 와샬을 수행하면, A가 C에게 도달 할 수 있는지 여부를 알 수 있다. 표를 보며 이해하면 더 쉽게 와닿을 수 있을 것이다. 주어진 입력으로 boolean[][] 배열을 지..

코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr [Dijkstra] 1번 정점에서 모든 정점까지의 최단 거리를 구해 dist[ ]에 저장 후, 1번 정점부터 n번 정점까지 dist[i]를 돌면서 dist[i]가 max인 곳의 정점 개수를 카운팅 한다. # Code import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; class Solution { static class Edge{ int tg, d; public Edge(int target, i..

14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net [최소 스패닝 트리(Minimum Spanning Tree, MST), 크루스칼] 남초와 여초만을 이어주는 경로만 존재한다고 생각하면 쉽다. 문제에서 2번째 줄에 M W W W M 이런 식으로 주어지는데, 이를 boolean[ ]에 저장을 한다. 예를 들어 1번 째 학교가 M(남초) 이면 true, 2번 째 학교가 W(여초)이면 false 이런 식으로. 그럼 간선 정보가 주어질 때 선별적으로 간선을 저장할 수 있다. for..