Debug.Log

하노이 타워 문제너무 유명한 문제이기 때문에 문제는 생략.재귀를 이용할 수 있는지를 알아보는 문제. #include ​ void Move(int id, char from, char to) { printf("[원판%d] %c -> %c\n",id, from, to); } ​ //from에 꽂혀있는 num개의 원판을 by를 거쳐서 to로 이동. void SolveHanoi(int num, char from, char by, char to) { if (num == 1) { Move(1, from, to); return; } ​ SolveHanoi(num - 1, from, to, by); Move(num, from, to); SolveHanoi(num - 1, by, from, to); } ​ int main..

백준 1922번 - 네트워크 연결https://www.acmicpc.net/problem/1922 문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다.하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다.그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다.(a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다.이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한..

백준 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개 받는 사람은 없어야 한다.택희가 받는 사탕의 수는 홀수개가 되어서는 안 된다.이제 사탕을 적절히 나누어 집에 돌아가던 중, 택희는 위와 같은 규칙을 만족하도록 세 명에게 사탕을 나누어 주는 방법의..

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

최장 공통 부분 수열(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 =..

연쇄행렬 최소곱셈 알고리즘 (Matrix Chan Multiplication)연쇄행렬 최소곱셈은 동적 프로그래밍(Dynamic Programming)을 활용하여 연산을 최적화 시키는 것행렬은 결합법칙이 성립한다.(AB)C = A(BC) 그러나 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.예를들어,A : 10x30 행렬B : 30x5 행렬C : 5x60 행렬일 경우(AB)C는 (10x30x5) + (10x5x60) = 1,500 + 3,000 = 4,500번의 연산으로 구할 수 있지만A(BC)는 (30x5x60) + (10x30x60) = 9,000 + 18,000 = 27,000번의 연산을 해야 구할 수 있다. 즉, 연쇄행렬 최소곱셈은 곱하는 순서에 따라 연산의 순서가 달라지는데, 이를 최적화 하는..

제곱 계산제곱 계산은 ​의 형식을 형태이다.본 포스팅에서는 b가 자연수인 경우 제곱 계산을 다루므로 ​으로 표기하겠다.파이썬에서 제곱 계산은 pow(a, n) 함수를 사용하거나, a**n 연산을 사용하면 된다.이제 power함수를 구현해보자. 1. n번 곱하기def power(a, n): ret = 1 for i in range(n): ret *= a return ret print(power(5, 5)) print(power(5, 21))1에다가 a를 n번 곱한다.시간복잡도는 O(N) 2. ​의 power 함수def power(a, n): ret = 1 while n > 0: if n % 2 != 0: ret *= a a *= a n //= 2 return ret print(power(5, 5)) pri..

최대공약수, 최소공배수 알고리즘 유클리드 호제법으로 최대공약수 구하기최대공약수를 구하는 함수를 ​라고 하자.​ 이라면, ​ 임이 성립.​ 이 이라면, ​ 임이 성립한다.def gcd(a, b): mod = a%b while mod > 0: a = b b = mod mod = a%b return b 최소공배수최소공배수는 a과 b의 곱에 최대공약수를 나누어 준 것과 같다.def lcm(a, b): return a*b//gcd(a,b) 최대공약수 (GCD : Greatest Common Divisor)최소공배수 (LCM : Least Common Multiple)

Infix를 Postfix로 바꾸기 중위 표기법(Infix) 우리가 흔히 아는 산술식이다.2 + 3 * 4 혹은 2 + 5 * ( 3 + 4 ) 등과 같이 괄호나 우선순위에 의해 풀어가는 방식.인간이 계산하기에 친숙한 표기법이다. 후위 표기법(Postfix)반면 컴퓨터는 중위표기법으로 계산을 하는 건 매우 어려운 문제이기 때문에 이를 보완하기 위해 후위 표기법으로 바꿔준다.2 3 4 * + 혹은 2 5 3 4 + * + 등으로 표기한다.연산자가 나오면 그 이전의 숫자 2개와 연산을 하는 방식이다.2 3 4 * +는 2 12 +으로, 그리고 14 순으로 계산한다. Infix를 Postfix로중위 표기법을 후위 표기법으로 바꾸기 위해서는 스택을 이용한다.infix를 순서대로 읽는다.읽은 값이 여는 괄호 '(..