Algorithm

[문제] https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 끝자리가 0이 되려면 2와 5를 곱했을 경우에만 10이 나와 끝에 0이 추가된다. 따라서 소인수분해 했을 때 2와 5의 최소값을 구하면 되는 문제인데 숫자가 커질수록 5가 2보다 적게 나와 5의 개수만 구해도 되겠다는 생각이 들었다. 따라서 n이 5 이상일 동안 cnt에 5로 나눴을 때의 몫을 더한 후 출력한다. [코드] import sys if __name__ == '__main__': n = int(sys.stdin.readline()) cnt = 0 while..

[문제] https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net [풀이] 문제 조건이 큰 동전은 모두 작은 동전의 배수이기 때문에 이 문제는 그리디 알고리즘으로 풀 수 있다. 만약 800원의 가치를 만들어야 하는데, 500원 400원 100원으로 주어지는 경우는 그리디 알고리즘을 쓰면 안된다. 동전 문제에 그리디 알고리즘을 적용하는 것은 쉽다. 동전의 액면가만 보고 판단하면 되기 때문에 ..

[문제] https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net [풀이] 문제를 읽었을 때 딱 봐도 제곱 반복 수행 -> 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용 -> 동적 계획법!!! 그렇다면 이제 문제에 사용되는 규칙을 찾아야 한다. 0 1 2 3 4 5 6 7 8 1 0 1 2 3 1 5 6 7 8 2 0 1 2 3 1 2 3 4 2 3 0 1 2 3 1 2 3 0 0 4 0 1 2 3 1..

[문제] https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net [풀이] 엥? 골드 5 치고는 너무 쉬워 보이는데? 하고 풀었는데 문자열 처리 부분이 까다로웠다. 일단.. 아래 코드 부분에 pop(0)을 할 일이 있길래 popleft()를 사용하기 위해 deque를 사용하기로 했다. 입력 중 배열에 들어가 있는 수를 처리하는 부분이 조금 까다로운데, "[1, 2, 3]" 이렇게 큰 따옴표 안의 모두를 입력받는다. 그러나 처리는 정수 (1, 2, 3)만 해야 하기 때문에 대괄호를 지우고, 쉼표로 구분을 해줘야..

[문제] https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net [풀이] 문제는 쉬운데 출력 비교하는 게 어려웠음 ㅎㅎㅋ 집합이기 때문에 set 자료형을 사용하였고, set은 자동으로 중복이 없어지기 때문에 중복을 신경 쓰지 않아도 된다. add, remove, check, toggle은 x라는 파라미터가 필요하지만 all과 empty는 파라미터가 없기 때문에 입력을 operation 변수에 한 번에 받고, operation이 'all'이나 'empty'이 아닌 경우, operation..

[문제] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [코드] import sys if __name__ == '__main__': target = int(sys.stdin.readline().strip()) m = int(sys.stdin.readline()) if m: # 고장난 버튼이 있을 경우 broken = set(sys.stdin.readline().split()) else: broken = set() ans = a..

[문제] https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] 2021.08.18 - [BOJ] - [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙 [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙 [문제] https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 ..

[문제] https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net [풀이] 이전 글의 최소 힙과 같이 파이썬의 heapq 모듈을 사용하나, 해당 모듈은 최소 힙 기능만 동작하기 때문에 최대 힙으로 활용하기 위해서는 조금의 조작이 추가로 필요하다. 2021.08.28 - [BOJ] - [Python] BOJ/백준 1927번 최소 힙 [Python] BOJ/백준 1927번 최소 힙 [문제] https://www.acmicpc.net/pr..

[문제] https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] 힙(Heap)? 힙은 완전 이진트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조이다. 항상 자식은 두개밖에 없으며, leaf의 가장 왼쪽부터 값을 채운다. 힙은 크게 최소힙과 최대 힙 두 가지가 있다. 최소 힙은 가장 작은 값이 루트이고, 최대 힙은 가장 큰 값이 루트이다. 힙은 완전 이진트리이지만 코드를 구현하기 위해서는 ..