개발하는 고라니

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

12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [문자열 + BFS] 이 문제는 정공법으로 풀면 안된다. s -> t를 가는게 아닌, t -> s를 가는 것을 생각해야 한다. 전자로 풀면 메모리 초과가 날 수 있다. 따라서 t -> s로 가는 방법으로 풀어보자. 1. 문자열의 끝이 'A'이면 맨 끝 문자 삭제 2. 문자열의 끝이 'B'이면 맨 끝 문자 삭제 후 뒤집기 나는 Set을 이용해 방문을 표시했엇으나, 굳이 필요하지 않음을 느꼈다. 따라서 반복문의 종료 조건은 문자열..

4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net [문자열 + Map] 우선 문제의 입력은 마지막이 특별한 조건이 없으므로 입력받은 값이 Null 또는 공백일 때 입력을 종료한다. 나는 BufferedReader를 썻지만, Scanner를 사용한다면 hasNextLine()을 사용할 수 있을지도 모르겠다. Map을 이용해서 나무 이름으로 Key를, 그 나무 이름이 나오는 횟수를 Value로 설정하고 값을 계속 업데이트하자. 그러면 해당 나무가 몇 번 이름 불렸는지 알게되는데, 문제에서는 이름 순으로 ..