printf("Hello dev_TORY!");

문제를 풀기에 앞서 새로운 알고리즘 유형인 동적계획법 알고리즘에 대해 공부해보도록 하자. https://hongjw1938.tistory.com/m/47 알고리즘 - Dynamic Programming(동적 계획법) 1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 hongjw1938.tistory.com 이 포스팅에 자세하게 나와져 있다. 결론적으로, 어떠한 문제가 재귀 알고리즘으로 풀릴 수 있다고 했을 때, 그 문제는 동적계획법 알고리즘으로도 풀릴 수 있다. 근데 왜 굳이 재귀와 동적계획법을 구분하여 사용하며, 그 둘의 차이점은 무엇일까? 재귀 알고리즘은 말..

https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 문제를 풀기에 앞서, 병합정렬에 대해 공부해보도록 하자. https://kangworld.tistory.com/m/74 [Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도 인트로 합병 정렬 또는 병합 정렬은 $O(NlogN)$ 시간 복잡도를 갖는 정렬 알고리즘으로 분할 정복 패러다임에 기반한다. 추가로 삽입 정렬, 버블 정렬, ..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 이 문제는 재귀 알고리즘의 대표적인 문제이다. 개인적으로 재귀에 가장 취약해서 못풀었었고, 다른 사람의 풀이코드를 봐도 이해하는 것이 힘들었다. 재귀는 백트래킹, DFS 등 알고리즘에서 자주 사용되니 반드시 이해하고 넘어가야한다. 재귀는 2가지 조건을 반드시 갖추어야 정상적인 동작을 할 수 있다. 1. 종료조건을 반드시 갖출 것 2. 자기 자신을 호출하되, 함수를 반복할수록 종료조건과..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 못풀겠어서 다른 사람의 풀이법을 참고하여 해결하였음 해당 문제는 백트래킹 알고리즘의 기본 예제 문제이다. 그렇다면, 백트래킹이란 무엇일까? 백트래킹이란, 해를 찾는 도중 해가 아니어서 막히며, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 모든 경우의 수를 고려할 때 쓰이는데 흔히 다 알고 있는 트리 탐색의 경우, 그냥 해를 찾기 위해 계속 탐색만 할 뿐 막히면 되돌아가지는 않는다. 그래서 많은..

1676번 문제는 주어지는 숫자가 500이하이므로 그냥 팩토리얼을 구하여 10으로 나눠주면서 갯수를 세서 풀었었다. 하지만 원리를 이해하지 못하고 노가다로 푸니까 응용문제인 2004번을 풀지 못하였다. 그래서 더 최적화된 풀이로 1676번을 다시 진행하고자 한다. 1.언제 끝에 0이 붙나? => 10이 곱해질 때마다 0이 붙는다. N!의 일의 자리 수부터 0이 아닌 수가 나올 때까지의 0의 갯수는 N!의 10의 갯수이다. 2. 10을 소인수분해하면 2와 5로 이루어져 있다. 팩토리얼 소인수분해 시, 직관적으로 항상 2의 지수가 5의 지수보다 크다는 것을 알 수 있다. 따라서, 더 작은 갯수인 5에 초점을 맞춰 10의 갯수가 아닌 5의 갯수를 구해주면 된다. 3. 그럼 5의 갯수를 어떻게 구할까? 5가 어..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 요약) 의상과 의상의 종류를 입력받아 같은 종류의 의상을 입는 것을 제외하여 의상을 입는 경우의 수를 구하는 문제 key point) 여러 의상들과 a, b, c ...등의 여러 의상 종류를 입력받았다고 가정해보자. 식을 세운다면 다음과 같이 세울 수 있다. (a종류수 + 1) * (b종류수 + 1)..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 그럼 문제는 A, B, C 중에서 2개를 택하는 문제..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 요약) 팩토리얼 계산 결과를 10007로 나누었을 때의 나머지를 구하는 문제 key point) 부동소수점의 이해 필요 import math N, K = map(int, input().split()) if (N-K) 2702882409454365510193059084634026261333444246350031374006020919302377774213604738517973257249227304605438028756786031684718673610785400800..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 생각없이 풀면 쉽게 답이 나오는데 시간초과가 나온다. 그래서 구글링해서 풀음;; 주어진 숫자들을 나누어서 공통된 나머지가 나오는 수들을 구하는 문제 그렇다해서 반복문돌리면 시간초과나옴 ㅡㅡ 반복문을 사용하지 않고 구해야한다. 수학적으로 접근해보자. 나눠지는 수 = (몫*나누는 수) + 1 ex) 13 = 6*2 +1 이를 이용하여 만약 A, B, C 라는 수를 입력받았을 경우, 세 수의 나머지가 같다면 다음과 같..

collections 라이브러리 Counter함수는 데이터의 개수를 셀 때 유용하게 사용되는 함수이다. 원소의 갯수가 많지 않은 리스트의 경우, 내장함수인 count()를 사용하여 간단하게 구할 수 있지만 원소의 갯수가 많을 경우에는 매우 시간이 오래걸린다는 단점이 있다. collections 모듈의 Counter클래스를 사용하면 짧은 시간에 데이터의 개수를 구할 수 있다. 직접 사용해보자. from collections import Counter collections 모듈로부터 Counter을 임포트해서 사용하면 된다. 위의 사진은 문자열 'hello world'에 Counter을 사용한 결과이다. 이처럼 각 데이터에 대하여 {데이터:데이터 개수}의 딕셔너리 형태로 결과값을 반환한다. Counter클래..