https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 풀이 위 문제는 다음과 같은 연산을 반복한다. 입력받은 숫자 -> 홀수 개수 카운트 숫자를 짜름 -> 짜른 각각의 숫자를 모두 더한 숫자 -> 홀수 개수 카운트한 다음 이전 카운트에 더함 숫자의 홀수 개수를 카운트한 다음 이전 카운트에 더하는 로직이 반복되므로, 재귀호출 또는 반복문을 사용해야 한다. 또한 만들 수 있는 모든 경우의 수를 구해 그중 최솟값과 최댓값을 구해야 한다. 즉, 재귀호출을 ..

3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 입력으로 보드의 크기, 사과의 위치, 뱀의 방향 변환 정보를 받아 static 변수에 저장한다. static int size; //보드 크기 static boolean[][] apples; //사과가 있는 칸은 true, 없으면 false static HashMap directChange; //뱀의 방향 변환 정보 public static void main(String[] args) throws IOException { BufferedReader br = new ..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 Node 클래스를 생성하고, 클래스 내에 int value, Node left, Node right 인스턴스 변수를 생성하여 각각 노드 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장한다. static class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } } static 변수로 루트 노드 Node root을 생성한다. static ..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 Node 클래스를 생성하고, 클래스 내에 String value, Node left, Node right 인스턴스 변수를 생성하여 각각 노드 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장한다. static class Node { String value; Node left; Node right; public Node(String value, Node left, Node right) { this.value = value; this.left = le..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그래프를 그려서 해결할 수 있다. 인접 리스트로 그래프의 정보를 저장하고, 루트 노드에서부터 DFS또는 BFS로 탐색을 시작하여 아직 방문하지 않은 노드를 찾을 때마다 부모 노드 저장 배열(parent)에 부모 노드 번호를 저장하면 된다. 코드 import java.io.*; import java.util.*; public class Main { static int[] parent; //부모 노드 저장 배열 public static void main(S..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 1 - 크루스칼(Union & Find 활용) 최소 스패닝 트리를 구하는 알고리즘은 두 가지가 있다. 1. 크루스칼 (Union & Find 활용) 2. 프림 (PriorityQueue 활용) 크루스칼 알고리즘의 매커니즘 -> 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 주어진 그래프의 모든 간선에 대해서, 간선의 연결비용을 낮은 순으로 오름 차순 정렬한다. 정렬된 간선 순서대로..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 시작 위치에서 도착 위치까지 가는 최소 시간을 구한다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 최단 경로를 구하는 문제지만, 특정 정점을 지나는 최단 경로의 길이를 구해야 한다. 1번 정점 -> N번 정점의 최단 경로를 구해야 하는데, 두 정점 v1, v2를 거치는 최단 경로를 구해야 한다. 즉 위 조건을 만족하는 1번 정점 -> N번 정점의 최단 경로는 두가지가 있다. 1. 1 -> v1 -> v2 -> N 2. 1 -> v2 -> v1 -> N 그렇다면 각 정점부터 정점까지의 최단 경로를 구해서, 모든..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 그래프 최단 경로를 구하는 다익스트라 알고리즘을 사용하여 푸는 문제다. 인접리스트, PriorityQueue, 각 정점까지의 최단 경로를 저장하는 dis 배열을 사용하여 풀었으며 자세한 풀이는 이전에 풀었던 문제와 같기 때문에 설명은 생략하겠다. [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] http..

10816번: 숫자 카드 2첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,www.acmicpc.net 풀이Map을 사용하면 간단하게 풀 수 있지만, 이분 탐색으로도 풀 수 있다.다만 이 문제는 배열에 들어가있는 숫자의 개수를 구해야 하는데, 기본적인 이분 탐색 코드는 숫자의 위치(인덱스)만을 구할 뿐, 배열에 중복된 숫자가 있을 경우 숫자의 개수를 구하지는 못한다.그렇기 때문에 기본적인 이분 탐색 코드를 변형해서 중복된 숫자의 왼쪽 끝 위치(lower bound)와 오른쪽 끝 위치(upper bound)를 구해 중복된 숫자의 개수를 ..

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 재귀함수를 이용한 분할정복으로 문제를 풀 수 있다. n, b, arr 배열 값을 입력받은 다음 divideAndConquer() 재귀함수를 호출하여 arr의 b제곱(result 배열)을 구한다. 주의할 점 B의 범위는 1 ≤ B ≤ 100,000,000,000 이기 때문에 int로 값을 받으면 NumberFormatException이 발생한다. 그래서 Long.parseLong을 사용하여 long으로 값을 받아야 한다. A^B의 각 원소를 1,000으로 나눈 나머지를 출력..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 재귀함수를 이용한 분할정복을 사용하여 문제를 풀 수 있다. main 함수에서 전체 종이의 한 변의 길이 N과 색종이의 위치 정보를 입력받고 divideAndConquer() 재귀 함수를 호출하여 (0, 0)부터 색종이 배열 탐색을 시작한다. divideAndConquer() 함수 내에서 인자로 받은 시작위치부터 색종이 배열을 탐색하다가, 시작 위치의 색과 다른 색을 발견하면 위 그림과 같이 색종이를 4등분하여 새로운 탐색을 시작해..