알고리즘
-
BOJ) 트리 (1068 번)알고리즘/백준 2021. 1. 29. 17:08
트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리의 정보가 주어지고 특정 노드를 제거할 때, 리프노드가 몇 개 인지 찾는 문제다. 먼저, 트리의 각 노드는 하나의 부모를 가지고 있기 때문에 find-union을 사용해야겠다고 생각했다. 이전 find-union과 다른 점은 이미 부모에 대한 정보가 주어졌기 때문에, find할 때 더 상위 부모로 값을 최신화하지 않았다는 것이다. (최신화를 하게되면 루트 노드로 이어지기 때문에, 특정 노드를 제거했을 때, 자식노드를 제거할 수 없음) 다음으로..
-
BOJ) 트리의 지름 (1167 번)알고리즘/백준 2021. 1. 29. 16:56
트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 이전에 포스팅했던 트리의 지름과 조금 다르게 풀었다. 먼저, 트리기 때문에 어떤 지점에서 시작해도 특정 지점까지 모두 도달할 수 있다는 특징이 있다. 이 말인 즉, 가장 멀리있는 한 특정 지점을 찾을 수 있다는 말이 된다. 위의 조건에 따라, 1에서 가장 먼 vertex를 찾아주었다. 이후, 해당 vertex에서 가장 먼 거리에 있는 지점을 찾으며 최댓값을 갱신해주었다. (만약, 1 -> 찾은 지점이 가장 먼 거리라면, 찾은 지점 -> 1..
-
BOJ) 최솟값 찾기 (11003 번)알고리즘/백준 2021. 1. 29. 16:36
최솟값 찾기 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우를 이용하는 문제로, N개의 수와 윈도의 크기 L이 주어진다. D(i) = A(i-L+1) ~A(i) 중의 최솟값이라고 할 때, D에 저장되는 값을 출력하는 문제다. 즉, 자신의 위치에서 L칸 앞선 칸들 중 최솟값을 찾는 문제다. 처음에는 우선순위 큐로 시도하다가, 시간초과가 떴다. 아무래도 최악의 경우에는 O(N)이 추가돼서 그런 것 같다. (while을 통해 인덱스 범위를 검증하는 과정) 그래서 Deq..
-
BOJ) 전깃줄 (2565 번)알고리즘/백준 2021. 1. 26. 19:18
전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net A와 B 두 전봇대가 주어지고, 두 전봇대를 잇는 전기줄의 정보가 주어진다. 이 때, 전깃줄이 교차하는 경우를 없애기 위해 전깃줄을 제거해야 하는데, 가장 최소한의 전깃줄을 제거해서 교차하는 경우가 되게 만드는 문제다. 교차하는 가장 최소한의 전깃줄을 제거한다는 것은 전체 전깃줄에서 가장 올바르게 연결된 전깃줄 수를 빼주는 것과 성립한다. 전체 전깃줄 (n) - 가장 많이 올바르게 연결된 전깃줄 = 불필요하게 교차된 전깃줄의 최소값 여기서 가장 많이 올바르게 연..
-
BOJ) 달려라 홍준 (1306 번)알고리즘/백준 2021. 1. 26. 19:11
달려라 홍준 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 슬라이딩 윈도를 공부하기 위해 푼 문제였다. 슬라이딩 윈도는 주로 두 개의 네트워크 호스트간의 패킷의 흐름을 제어하기 위한 방법으로 사용된다. 고정된 크기의 윈도우가 전체 범위에서 움직이는 방식이다. 배열로 된 예시를 통해 이해하는게 더 수월했다. 위와 같은 배열에서 3의 크기로 전체를 탐색하는 경우 사용한다고 생각하면 편하다. 여러 블로그를 찾아봤는데, 슬라이딩 윈도의 핵심은 이전 값에 대해 중복되는 부분을 재사용한다는 것이..
-
BOJ) 암호코드 (2011 번)알고리즘/백준 2021. 1. 26. 18:54
암호코드 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제의 조건이 많이 주어지지 않아서, 예외 케이스를 많이 찾아야했다. 우선, 문제를 살펴보면 문자를 숫자로 암호화하는데, A=1, Z=26으로 암호화를 한다. 이 암호화된 숫자로부터 나올 수 있는 암호의 경우의 수를 구하는 문제다. 암호를 만들 수 없는 경우는 0을 출력한다는 조건도 있다. 먼저, 입력받을 때 부터 예외 케이스를 검증해주었다. 0으로 시작하는 경우, 연속으로 0이 들어오는 경우, 입력한 문자열이 빈 문자열인 경우, 숫자가 아닌 문자열이 들어오는 경우를 먼..
-
BOJ) 생물학자 (3116 번)알고리즘/백준 2021. 1. 21. 19:12
생물학자 3116번: 생물학자 첫째 줄에 박테리아의 수 N(1 ≤ N ≤ 5,000)이 주어진다.다음 N개의 줄에는 세 개의 정수 X, Y, D (-1,000,000 ≤ X,Y ≤ 1,000,000), (1 ≤ D ≤ 8) 가 주어진다. X와 Y는 박테리아의 시작 좌표이며, D는 방향이 www.acmicpc.net 수학 문제라고 느껴졌다. 박테리아의 위치가 주어지고, 방향이 주어진다. 아래의 방향에 따라서, 매 초 일정하게 이동을 할 때, 박테리아 여러 마리가 같은 칸에 제일 많이 있을 때가 언제인지, 그리고 그 때 몇 마리가 같은 칸에 있었는지 구하는 문제였다. 또한, X값은 왼쪽에서 오른쪽으로 갈 수록 증가하며, Y값은 위로 갈수록 증가한다는 조건이 있다. 즉, 1번은 매초 X값이 -1씩, Y값이 +..