목록Algorithm/백준 BOJ (44)
다희의 코딩 성장일기
[백준] 1138. 한 줄로 서기 (자바 JAVA)
[ 문제 ] [백준] 1138. 한 줄로 서기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net # 접근 방법 및 풀이 구현 문제다. 아이디어를 떠올렸다면 쉽게 풀었을 수도 있지만, 약간 생각하는데 시간이 걸렸다. 먼저, 문제에서 입력으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇명 있는지 주어진다. 예제대로 N = 4일 때, 2 1 1 0 으로 입력을 받아 arr[] 배열에 담아준다...
[백준] 11725. 트리의 부모 찾기 (자바 JAVA)
[ 문제 ] [백준] 11725. 트리의 부모 찾기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net # 접근 방법 및 풀이 트리구조를 떠올리며 BFS로 풀었다. DFS로도 가능. 노드의 부모를 찾는 문제다. 트리라고하니 이진트리라고 한정지었는데 틀렸다. 문제에 이진트리라는 조건도 없고 그냥 연결된 노드 정보만 있다. 다만, 루트노드가 1이기 때문에 루트노드부터 연결된 노드를 탐색하며 부모노드를 찾을 수 있다. 현재 노드가 어디 노드로부터 왔는지 찾으면 된다. 예제 1번에 "1..
[백준] 5639. 이진 검색 트리 (자바 JAVA)
[ 문제 ] [백준] 5639. 이진 검색 트리 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net # 접근 방법 및 풀이 트리문제다. 문제의 조건에 맞는 이진트리를 구현하고, 후위순회를 재귀함수로 만들어 값을 프린트하면 된다. 이진트리를 구현하기 위해 Node 클래스를 만들어 "현재 노드의 값, 왼쪽 노드, 오른쪽노드" 변수 세개를 만들어 주었다. 문제의 입력에 첫번째로 입력되는 값이 root이므로 먼..
[백준] 1074. Z (자바 JAVA)
[ 문제 ] [백준] 1074. Z (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net # 접근 방법 및 풀이 분할정복 재귀 문제다. 앞서 다뤘던 "쿼드트리, 색종이 만들기" 문제처럼 그냥 재귀 돌리면 시간초과난다. 이유는 N의 범위가 최대 15이므로 2^15 사이즈의 map을 다 잘게잘게 잘라서 r, c를 하나씩 확인한다면 시간초과난다. 여기서 중요한건, R, C가 "1, 2, 3, 4" 사분면 중에서 어..
[백준] 2630. 색종이 만들기 (자바 JAVA)
[ 문제 ] [백준] 2630. 색종이 만들기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net # 접근 방법 및 풀이 백준 "1992 쿼드트리"와 똑같은 문제라고 볼 수 있다. 요구하는 답이 다를 뿐. 쿼드 트리는 분할정복+재귀로 풀었다면, 이 문제는 그냥 재귀로 풀었다. 이 문제가 / 2 씩해서 종이를 나누어 가면, 백준 1780 종이를 / 3 으로 나누어갈 뿐 코드는 똑같다. 백준 ..
[백준] 1780. 종이의 개수 (자바 JAVA)
[ 문제 ] [백준] 1780. 종이의 개수 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net # 접근 방법 및 풀이 재귀문제 중에 정말 좋은 문제라고 생각한다. 그리고 실버2는 아닌거같음.. 실버1~골드5? 이전에 백준1992 쿼드트리를 풀고나면 접근방법은 쉽다. https://ilmiodiario.tistory.com/137 문제 그대로 재귀 짜면 된다. 그러나 주의할 점이 좀 있다. 조건 1에 "만..