Debug.Log

백준 11725번 - 트리의 부모 찾기https://www.acmicpc.net/problem/11725 문제루트 없는 트리가 주어진다.이 때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 접근parent 배열을 만들어 입력된 정점 중 부모노드를 찾아 바로 기록해준다.부모노드는 parent 배열에 기록된 적이 있는 노드가 부모노드가 된다.입력의 순서때문에 두 정점이 모두 부모가 없는 경우가 있는데 이 때, 스택을 활용하여 따로 빼두..

백준 14568번 - 2017 연세대학교 프로그래밍 경시대회https://www.acmicpc.net/problem/14568 문제2015, 2016년에 이어 2017년에도 연세대학교 교내 프로그래밍 경시대회가 열린다.택희, 영훈이, 남규는 열심히 문제를 만들었고, 이에 대한 보상으로 과사로부터 사탕 N개를 받았다.N개의 사탕을 적절히 나눠 가지기 위해 토론한 결과, 아래와 같은 방식으로 사탕을 나누기로 결정하였다.남는 사탕은 없어야 한다.남규는 영훈이보다 2개 이상 많은 사탕을 가져야 한다.셋 중 사탕을 0개 받는 사람은 없어야 한다.택희가 받는 사탕의 수는 홀수개가 되어서는 안 된다.이제 사탕을 적절히 나누어 집에 돌아가던 중, 택희는 위와 같은 규칙을 만족하도록 세 명에게 사탕을 나누어 주는 방법의..

최소 신장 트리 (Minimum Spanning Tree) 최소신장트리?신장트리란, 사이클을 형성하지 않고 그래프의 모든 정점(V)이 간선(E)으로 연결되어 있는 것최소신장트리란 최소한의 비용으로 신장트리를 형성하는 것 Kruskal's Algorithm모든 정점을 독립적인 집합으로 만든다.모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.시간 복잡도는 ​ Python Codeparent = {} rank = {} ​ # 정점을 독립적인 집합으로 만든다. def make_set(v): parent[v] = v rank[v] = 0 ​ # 해당 정점의 최상위 정점을 찾는다. def find(v):..

백준 2580번 - 스도쿠 문제스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다.이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.나머지 빈 칸을 채우는 방식은 다음과 같다.각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 입력아홉 줄에 걸쳐 한 줄에 9..

백준 9663번 - N Queen 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력8예제 출력92 접근1행(Row), 1열(Column) 위치에 퀸을 하나 놓는다.다음 행에서 가능한 가장 왼쪽에 퀸을 놓는다.N번째 열에 퀸을 놓지 못한다면 백트래킹마지막 행에서 퀸을 하나 놓으면 하나의 정답을 구한 것이다.모든 경우의 수를 조사하고 가능한 정답의 경우의 수를 구한다. 유망성 (Promising)백트래킹 문제에서 현재의 경우의 수가 가능한 경우의..

백준 10844번 - 쉬운 계단 수문제45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.(0으로 시작하는 수는 없다.) 입력첫째 줄에 N이 주어진다.N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력2예제 출력17 접근Dynamic Programming으로 접근한다.첫 째 자리수에 올 수 있는 숫자는 1~9이다.만약 첫 째 자리수가 1이라면, 둘 째자리수는 0 또는 2가 올 수 있다.만약 첫 째 자리 수가 9..

백준 2156번 - 포도주 시식문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을..

백준 1912번 - 연속합문제n개의 정수로 이루어진 임의의 수열이 주어진다.우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.단, 숫자는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자.여기서 정답은 12+21인 33이 정답이 된다. 입력첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력첫째 줄에 답을 출력한다. 예제 입력10 10 -4 3 1 5 6 -35 12 21 -1 예제 출력33 접근Dynamic Programming으로 접근한다.첫 ..

백준 2293 - 동전1문제n가지 종류의 동전이 있다.각각의 동전이 나타내는 가치는 다르다.이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 예제 입력3 10 1 2 5 예제 출력10 접근Dynamic Programming으로 접근한다.첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 찾는다.첫 번째~두 번째 동전만 사용하였을 때, 각k 값 마다 가능한 경우의 수를 찾는다.이 때, 첫 번째 동전만 ..

최장 공통 부분 수열(Longest Common Subsequence)두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.diff 명령은 LCS 문제를 해결하는 데 기반을 둔다. diff utility다음과 같이 두 항목이 있다고 하자.a b c d f g h j q za b c d e f g i j k r x y z 여기서 공통이 되는 가장 긴 부분은 다음과 같다.a b c d f g j z 두개 항목을 비교하여 추가(+)되거나 삭제(-)된 부분을 다음과 같이 나타낸다.e h i q k r x y + - + - + + + + LCS 함수의 정의두 수열은 다음과 같이 정의.​, ​. Python CodeA =..