본문 바로가기

Algorithm705

[자료구조/해시] 백준 20232 Archivist - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 20232번: Archivist The only line of input contains a single integer $y$ ($1995 \le y \le 2019$), denoting the year. You don't need to process year numbers less than $1995$ or greater than $2019$, or incorrect year formats. It is guaranteed that you will be given a number bet www.acmicpc.net 2. 문제 풀이 1995년부터 2019년까지의 대회 수상자의 이름이 문제에 주어집니다. 년도가 입력되면, 해당 연도의 수상자를 출력합니다. 3... 2022. 7. 31.
[구현/수학] 백준 5928 Contest Timing - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 5928번: Contest Timing Bessie the cow is getting bored of the milk production industry, and wants to switch to an exciting new career in computing. To improve her coding skills, she decides to compete in the on-line USACO competitions. Since she notes that the contest starts on www.acmicpc.net 2. 문제 풀이 대회는 11일 11시 11분에 시작합니다. 입력된 대회 종료시간을 통해, Bessie가 응시한 시간을 구해야 합니다. 3... 2022. 7. 30.
[구현/수학] 백준 24723 녹색거탑 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 24723번: 녹색거탑 Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외 www.acmicpc.net 2. 문제 풀이 다음과 같은 녹색 거탑이 있습니다. 높이가 N인 녹색 거탑의 꼭대기에서 바닥으로 내려오는 경우의 수를 구해야 합니다. 쉽게 생각해보면, 1층이 높아질 때마다 양쪽으로 내려올 수 있는 2가지 경로가 생깁니다. 즉, 2배씩 경우의 수가 늘어납니다. 3. 코드 # 입력 N = int(input()) print(2**N) 2022. 7. 29.
[구현/수학] 백준 15921 수찬은 마린보이야!! - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15921번: 수찬은 마린보이야!! 기댓값 E(X)의 정의는 ‘각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값’이다. 다시 말해, 어떤 수 x가 수열에 등장할 확률 P(x) = (x의 등장 횟수) / www.acmicpc.net 2. 문제 풀이 '평균 / 기댓값'을 구하는 문제입니다. 평균: x / 총 개수 기댓값: x * x가 일어날 확률 평균과 기댓값은 사실 같은 '용어'입니다. 의미의 차이가 있을 뿐이죠. '1 / 총 개수 = x가 일어날 확률' 입니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N = int(input()) if N == 0: print("d.. 2022. 7. 28.
[분할정복/DP] 백준 15624 피보나치 수 7 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 풀이 짧은 시간 제한(1초) 내에 피보나치 수를 구해야 합니다. 2022.05.14 - [Algorithm] - [분할정복/DQ] 백준 11444 피보나치 수 6 - 파이썬(Python) 이를 위해서는 분할정복 또는 DP를 이용해야 합니다. 여기서는 피보나치 6에서 사용했던 분할 정복을 이용했습니다. 해당 방식에 대한 설명과 코드는 위 링크에 기재되어 있습니다. 3. 코드 # 입력 N = int(input()) matrix = [[1, 1], [1, 0]] # 행렬 곱셈 def mul_matrix(mat.. 2022. 7. 27.
[구현/수학] 백준 15700 타일 채우기 4 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15700번: 타일 채우기 4 첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 1,000,000,000) www.acmicpc.net 2. 문제 풀이 N*M 크기의 벽에 2*1 또는 1*2 크기의 타일을 최대한 많이 배치하는 문제입니다. 예를 들어, 4 * 3 크기의 벽은 아래와 같이 채울 수 있습니다. 먼저 1 * 2 타일을 채우는 경우, (세로 길이 // 2) * 가로길이 = (3//2) * 4 = 4개를 배치할 수 있습니다. 2 * 1 타일은 (세로 길이 % 2) * (가로 길이 // 2) = (3%2) * (4//2) = 2개를 배치할 수 있습니다. 먼저 2 * 1 타일을 채우는 경우, (가로 길이 // 2) * 세로길이 = (4//2) * 3.. 2022. 7. 26.
[수학/백트래킹] 백준 6603 로또 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 2. 문제 풀이 로또의 경우의 수를 오름차순으로 출력하는 문제입니다. 2022.03.20 - [Algorithm] - [Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 [Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 DFS 탐색 중 가능성이 없는 방향은 가지 않는 '백트래킹' 기법에 대해서 알아보겠습니다. [ Contents ] 1.. 2022. 7. 25.
[구현/수학] 백준 24883 자동완성 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 24883번: 자동완성 D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외부 개발자들을 지원 www.acmicpc.net 2. 문제 풀이 N 또는 n이 입력되면 "Naver D2"가 출력되고, 그 외에는 "Naver Whale"이 출력되는 프로그램을 만들어야 합니다. 3. 코드 # 입력 s = input() # 자동완성 print("Naver D2" if s == 'n' or s == 'N' else "Naver Whale") 2022. 7. 24.
[동적계획법/DP] 백준 1309 동물원 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2. 문제 풀이 2 * N 칸인 동물원에 사자가 배치될 수 있는 모든 경우의 수를 구하는 문제입니다. 사자는 '가로와 세로'로 붙어있을 수 없습니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programming, 동적계획법) 동적계획법(Dynamic programming, DP): 작은 문제들에 대한 결과를 배열(리스트)에 저장하고, 이.. 2022. 7. 23.

티스토리툴바