📚 문제 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 🔍 아이디어 만약 현재 노드가 유사 중위 순회의 끝이라면 유사 순위를 종료한다는 부분을 잘못 이해해서 여러 번 틀렸던 문제였습니다. 이 구문은 현재 노드가 중위 순회가 끝났다면 다시 올라가지 않아도 된다는 것을 의미합니다. 즉 왼쪽으로 가는 경우는 반드시 루트로 다시 올라와야 하지만 오른쪽의 경우는 중위순회가 끝난 상태라면 다시 올라오지 않아도 됩니다. (중위 순회 : 왼쪽 자식 -> ..
📚 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 🔍 아이디어 mst를 활용하여 풀이하였습니다. *(다른 분들과 풀이가 달라 맞는 풀이인지 확신이 들지 않습니다. 참고 부탁드립니다) 가장 힘이 드는경우는 가장 많은 경사로(같은 길이 나오지 않기때문)를 이용하는 경우라고 생각하였습니다 따라서 먼저 경사로를 이용하는 경우의 모든 경로를 연결합니다. 이때 연결된 경사로의 개수의 제곱이 점수가 됩니다. 가장 ..
📚 문제 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🔍 아이디어 bfs로 해결하였습니다. 한 타임에는 불이 퍼지는 경우와 내가 이동하는 경우를 모두 생각해야했습니다. 또한 이번 타임에 불이 옮겨지는곳에는 자신이 이동하면 안된다는 조건이있습니다. 저의 경우 불이 옮겨 붙어지는 경우를 모두 계산한 후에 이동하지 않고 이동할 수 있는 모든 경우를 이동한 후에, 불이 이동하도록 하였습니다. 이렇게 한 후 다음턴에 자신의 위치가 불로 변한 경우 해당 칸은 이전에 갈 수 없던 칸이었는데 이동한것으로 하여 무시하는 방식으로 진행..
📚 문제 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 🔍 아이디어 사각형을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 묶은 후에 해당 영역이 모두 같은 색으로 칠해져있다면 숫자를 입력하고 칠해져 있지 않다면 다시 한분 4등분 분할하여 한영역이 모두 같은 색이 될때까지 진행하며 영역의 값을 구해나간다. 예제 입력 8 11110000 11110000 00011100 00011100 11110000 11110000 11110011 11110011 예제 출력 ((110(0101))(0010)1..
📚 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 🔍 아이디어 1. 재귀적 풀이는 숫자 3개를 고르는 과정이 조합과 같기 때문에 해당 방식을 이용하였습니다. 2. 반복문 풀이는 숫자 3개를 고르는 과정을 3중 포문을 이용해서 arr에서 i, j, k숫자를 뽑는 경우에 대해서 목푯값과 비교하여 문제를 해결할 수 있습니다. 📝 풀이 1. 재귀적 import java.io.BufferedReader; impor..
✨ HINT 숫자를 아예 4,7로 구성해 보는 방식 숫자를 4,7로 구성한 후에 a와 b사이에 속하는지 확인하는 방식 📚 문제 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔍 아이디어 범위가 1~1,000,000,000이기 때문에 모든 수에 대해서 4,7로 이루어져 있는지 판단하는 것이 시간이 너무 오래 걸릴 것이라 생각하였습니다. 다른 방법은 아예 숫자 자체를 4,7로 이루어지게 한 후에 min, max사이에 해당 값이 있는지를 판단하는 것이 낫다고 생각하여 해당 방식을 이용하였습니다. Int형의 범위..
📚 문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🔍 아이디어 https://mathbang.net/101#gsc.tab=0 두 원의 위치관계, 내접, 외접 위치관계 또 나오네요. 이번에는 두 원의 위치관계에요. 위치관계 마지막이니까 정신 바짝 차리고 따라오세요. 원과 직선의 위치관계, 원의 할선과 접선, 접점에서 했던 것처럼 두 원이 어떤 관 mathbang.net 내접과 외접에 관한 문제입니다. 각 점을 기준으로 r 떨어진 거리에 사람이 있는경우는 원을 그려서 해당 해당 호 안에 사람이 있어야 한다는 소리로 인식했습니다. 따라서 두 원의 내접과, 외접..
📚 문제 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 🔍 아이디어 단순한 위상정렬 문제입니다. 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 과거에 다른 블로그에 작성한 글입니다. 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬..
📚 문제 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 🔍 아이디어 오랜만에 풀어본 위상정렬 문제였습니다. https://lahezy.tistory.com/40 (제가 과거에 작성한 위상정렬 관련 글입니다) 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬 알고리즘의 일종으로, 순서가 있는 작업을 차례대로 수행해야 하는 경우 사용할 수 있는 알고리즘이다. 방향 그래프로의 모든 그래프를 방향을 거스르지 않도록 순서 la..
📚 문제 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 🔍 아이디어 처음에는 a, b를 비교해서 lcs 문자열을 구하고 c와 비교하는 형식으로 구했더니 틀렸다. 해당 방법은 최대 값을 기준으로 하기 때문에 abc 모두에 대해서 최댓값으로 확신할 수 없다. 예를 들어(반례) a: abcdeqfpk b: qfpkabcde c: qpk 와 같은 경우 a,b에 대해서 bcdef이지만 abc전체에 대해서는 qpk이다. 따라서 abc에 대해서 항상 최장 공통 문자열이 아닌 것이다. 따라서 abc모두에 대해서 3차원 배열로 계산해야 ..
