알고리즘
-
BOJ) 트리의 부모 찾기 (11725, JAVA)알고리즘/백준 2020. 8. 25. 17:58
트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 처음에는 1차원 배열로 문제를 풀려고 하다가, 연결 관계에서 부모 관계를 파악하기 힘들다는 문제를 발견했다. 그래서 BFS로 풀어야겠다는 마음을 먹었다. 우선 map을 저장해줘야 하는데, 배열을 사용할 수 없다. (최악의 경우 100,000 by 100,000가 된다) 그래서, ArrayList 배열에 map의 관계를 저장했다. (레코드 조회만 필요하기 때문에 ArrayList가 더 적절하다고 판단했다.) 맵이 저장된 다음에는 Queue를 통해 부모를 짝지어주었다. root인 1부터 시작하면서 1과 연결..
-
BOJ) 욕심쟁이 판다(1937, JAVA)알고리즘/백준 2020. 8. 25. 17:54
욕심쟁이 판다 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 메모이제이션을 활용한 dp문제다. 생각보다 너무 어려웠다. 알고리즘을 조금 쉬었다가 메모이제이션을 적용시켜서 dp를 활용하려니까 감이 잡히지 않았다. 그래서 다른 사람들의 풀이를 보면서 이해했다. 먼저, out of index를 방지해줄 inInArea 메소드와 움직일 수 있는 조건인지 확인하는 canMove 메소드를 만들었다. 이후, dfs 메소드인 findBamboo를 통해 문제의 조건에 따라 움직이며 최대 날을 구했다. 해당 위..
-
BOJ) 팰린드롬? (10942, JAVA)알고리즘/백준 2020. 8. 25. 17:49
팰린드롬? 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 효율적이지 않은 코드지만, 왠만한 팰린드롬 문제는 다 통과될 수 있도록 코드를 작성했다. 검사할 글자의 개수가 홀수일 때는 중앙점을 기준으로 좌 우로 -1, +1을 각각 해주면서 비교해주면 된다.짝수인 경우에는 중앙이 left가 되고, 중앙+1을 right로 비교해주면 된다.따라서, 위의 조건에 따라 짝수인 경우에는 left를 mid로 설정해주는 것을 예외처리 해줘서, left와 right가 같은지 확인할 수 있도록 했다. 코드 import java.io.BufferedReader; i..
-
BOJ) ACM 호텔(10250, JAVA)알고리즘/백준 2020. 8. 24. 17:00
풀이 1년 전에 못풀어던 문제였다. (문제를 풀기 시작하고 알았다.) 호텔의 층수, 한 층마다 방의 개수, 손님의 순번이 순차적으로 주어진다. 호텔에 머무는 손님들은 왜인지 모르겠지만, 가장 적게 걷는 것을 선호한다고 한다.그래서 각 층의 1호방 -> 각 층의 2호방 순으로 순차적으로 배정된다.(101, 201, 301 ... 102, 202호 이런 식으로 방이 배정됨) 풀고나니까 생각보다 간단했다. 우선 배정될 층의 높이는 n % h를 통해 구해줬다. n층에서 몇번째 위치하는지 구한것이다. 주의해야할 점은 n % h == 0인 경우에는, 가장 꼭대기 층에 배정해줘야 한다는 점이다. (배정 층의 순서를 생각해보면, 1층 -> 2층 -> 3층 ... h층인데, h % h => 0이기 때문) 다음으로는 해당..
-
BOJ) 동물원 (1309, JAVA)알고리즘/백준 2020. 8. 24. 16:44
풀이 코드 라인을 보면 아주 간단한 문제라고 여겨지겠지만, 점화식을 도출하는 것이 어려웠다. 더 사실대로 말하자면, 혼자 도출하지 못했고 다른 풀이에서 점화식을 얻어왔다고 표현하는게 더 맞는 것 같다. 처음에는 Combination과 같은 경우를 찾는 식을 활용하는 방향으로 접근했다.하지만 어떤 식도 부합하는 것이 없었고, n=1 ~ n=4까지 직접 경우의 수를 찾아봤다. n=1 => 3n=2 => 7n=3 => 17n=4 => 41 위와 같이 경우의 수가 나왔다.위에서 유추할 수 있는 것은, dp[n] = dp[n-1]*2 + dp[n-2] 라는 식이다.n-1의 경우의 수 *2 + n-2의 경우의 수가 되는데, 왜 이 식이 성립하는지는 아직 명확하지 않다.n이 1씩 증가할 때마다, 2칸이 생기기 때문에..
-
BOJ) 바이러스 (2606, JAVA)알고리즘/백준 2020. 8. 24. 16:39
풀이 전형적인 find - union 문제라고 할 수 있겠다. n 대의 컴퓨터가 연결되어 있고, 연결 관계가 주어진다. (그래프) 연결된 컴퓨터들 중 하나만 바이러스 걸려도 연결된 컴퓨터 모두 바이러스가 걸린다. 1번 컴퓨터가 바이러스 걸렸을 때, 몇 대의 컴퓨터가 추가적으로 바이러스 걸리는지 구하는 문제다. 풀이는 간단했다. 우선 parents 배열, find, union 메소드를 만들어 줬다. 그리고 입력을 받으면서 따로 graph에 저장하지 않고, 바로 find -union을 해줬다. 이후, 2번 ~ n번까지 컴퓨터를 돌면서 parent를 찾아 1번의 parent와 같다면 답에 더해줬다. (union할 때, 더 큰수의 parent를 작은 수로 설정해서 아마 1번의 parents는 언제나 1일것이다...
-
BOJ) 이항 계수 2알고리즘/백준 2020. 8. 8. 15:49
이항 계수 2 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr 을 구하는 문제다. nCr = n-1Cr-1 + n-1Cr 이라는 공식을 저번에 이어서, 다시 한번 머리에 남기기 위해 포스팅 한다. r이 0일 때와, n일 때 1로 설정하고, 나머지 r에 대해서 위의 공식을 적용하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public sta..
-
BOJ) 이동하기알고리즘/백준 2020. 8. 2. 00:01
이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 풀이 미로에 같힌 준규가 각 방에 놓여있는 사탕을 주워먹으면서 갈 때, 먹을 수 있는 사탕의 최대 갯수를 구하는 문제다. 이 문제는 언젠가 풀었던 것 같다. 아마 프로그래머스 문제 중 하나이지 않을까 싶다. 아무튼, dp를 이용해서 문제를 풀었다. 맵의 처음부터 x축을 순회하면서 좌측과 상단 중 사탕이 더 많은 갯수를 더해가면서 마지막 위치에 도달하게 설정했다. 이후, n, m의 dp값을 출력해서 답을 쉽게 구할 수 있었다. 코드 im..