매일 조금씩

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식..

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 간선 정보가 명시적으로 주어지며, 다익스트라 알고리즘으로 풀 수 있는 문제이다. 1. 다음 노드와 다음 노드로 이동 시의 가중치 값을 저장할 Edge 클래스를 구현한다. public static class Edge { int to; int weight; public Edge(int to, int weight){ this.to = to; this.weight..

문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 오랜만에 다익스트라 알고리즘 문제를 풀어 보았다. 나는 아래와 같이 풀었다. 1. 간선에 대한 정보가 명시적으로 주어지지 않기 때문에 직접 만든다. 배열을 순회하면서 상하좌우를 체크하여 접근 가능한 좌표라면 현재 배열 좌표에 인접한 좌표라고 볼 수 있다. 이때 인접한 좌표의 배열 값이 해당 좌표를 가기 위한 가중치 값이 된다. for(int i = 0; i < N; i..

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 밑이 같은 두 거듭제곱의 곱은 밑은 그대로 쓰고 지수만 더해준다는 지수법칙을 활용한다. 예를 들어 2의 10제곱은 2^10 = 2^5 * 2^5 로 분할 할 수 있다. 그러면 2를 10번 곱하는게 아닌 2를 5번 곱한 값을 가져와서 제곱을 하면 된다. 2^5 또한 아래와 같이 분할 할 수 있다. 2^5 = 2^2 * 2^2 * 2 이렇게 지수의 거듭제곱을 절반 씩 분할 하면서 제곱 계산의 수를 현저히..

문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 단순한 재귀 용법으로 해당 문제를 푸는 것은 불가능하다. n이 무려 1,000,000,000,000,000,000이다. 두 가지 내용을 이해하면 문제를 풀 수 있다. 1. 피보나치 수를 행렬의 곱을 통해 구할 수 있다. 2. 제곱을 구할 때, 지수를 반으로 나누어 곱하는 방식으로 재귀횟수를 줄일 수 있다. 아래 문제 참고 2021.11.18 - [Problem Solving/BOJ] - [BOJ 1629] 곱셈 (Java) [BOJ 1629] 곱셈 (Java) 문..

문제 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거..

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 이분 그래프 개념을 알아야 풀 수 있다. 그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 이런 문제 유형은 처음이라, 쉽사리 해결 방법이 생각나지 않았다. 질문 게시판 힌트를 보고 풀었다. 일단 기본 뼈대는 BFS로 구현한다. 이후 벽 한개를 어떻게 파괴할 것인가? 이 문제에 맞닥뜨린다. 벽을 최대 한 개 파괴할 수 있지만 반드시 파괴해야 하는 것은 아니다. 이 문제의 핵심은 방문 체크에 있다. 보통 좌표의 방문체크를 2차배열로 구현하지만, 해당 문..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 풀이 전형적인 BFS 문제. 이동 가능한 좌표를 정의하고 시작한다. 아래 dir을 순회하면서 현재 x좌표에 첫 번째 원소, y좌표에 두 번째 원소를 더하여 다음 좌표를 계산한다. public sta..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 배열이 3차원일 뿐 풀이는 아래와 동일하다. 2021.11.19 - [Problem Solving/BOJ] - [BOJ 7576] 토마토 (Java) [BOJ 7576] 토마토 (Java) 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의..