본문 바로가기

Algorithm706

[DP/동적계획법] 백준 1003 피보나치 함수 - Python [ Contents ] 1. 문제 (링크 참조) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 2. 문제 풀이 fibo[n] = fibo[n-1] + fibo[n-2] 피보나치 수열에서 0과 1이 리턴되는 횟수를 구하는 문제입니다. 피보나치 수열은 이전 결과와 그 이전 결과의 합으로 구성됩니다. 따라서 몇 번째 피보나치 수이든, 2이상이면 반드시 0과 1을 1번 이상 호출해야 합니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1... 2022. 2. 13.
[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programming, 동적계획법) 동적계획법(Dynamic programming, DP): 작은 문제들에 대한 결과를 배열(리스트)에 저장하고, 이를 이용해서 입력 크기가 더 큰 문제를 점진적으로 해결하는 방법 동적계획법은 이전 문제들의 답을 메모해두는 알고리즘입니다. 메모해두면, 동일한 문제가 나왔을 때 바로 답을 찾아서 쓸 수 있습니다. 다시 계산할 필요가 없기 때문에, 이전 문제의 해가 필요할 때 많은 시간을 절약할 수 있습니다. fibo(0) = 0 fibo(1) = 1 fibo(2) = fibo(1) + fibo(0) fibo(3) = fibo(2) + fibo(1) ... fibo(n) = fibo(n-1) + fibo(n-2) 다이.. 2022. 2. 12.
[자료구조/해시] 백준 1620 나는야 포켓몬 마스터 이다솜 - Python [ Contents ] 1. 문제 (링크 참조) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 2. 문제 풀이 포켓몬 이름을 순서대로 입력받습니다. 입력받은 순서대로 번호를 부여하며(1,2,3...) 숫자 또는 포켓몬 이름으로 질문합니다. 숫자가 입력으로 들어오면 해당 포켓몬 이름을, 이름이면 번호를 출력해야 합니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Co.. 2022. 2. 12.
[구현/비트마스킹] 백준 11723 집합 - Python [ Contents ] 1. 문제 (링크 참조) 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 2. 문제 풀이 집합 연산을 하는 문제입니다. 문제 유형은 비트마스킹으로, 비트 연산을 통해 집합 연산을 구현합니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적절한 출력만 하면 됩니다. 특별한 알고리즘이나 프로그래밍적 기법 없이,.. 2022. 2. 11.
[자료구조/해시] 백준 15829 Hashing - Python [ Contents ] 1. 문제 (링크 참조) 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 2. 문제 풀이 주어진 해시함수에 따라 해시값을 구하는 문제입니다. 알파벳(a_i)은 a~z까지 1~26으로 나타내고, i번째 글자는 31의 i제곱을 곱해줍니다. M은 1234567891이며, M으로 나눈 나머지가 해시값이 됩니다. 나머지 연산자는 결합법칙이 성립하므로, 각 문자의 해시값이 너무 커지지 않도록 미리미리 M으로 나머지를 구해주는 게 좋습니다. 3. 코드 L = int(input()) #문자길이 str.. 2022. 2. 11.
[Brute Force] 백준 18111 마인크래프트 - Python [ Contents ] 1. 문제 (링크 참조) https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 2. 문제 풀이 1) 블록 제거: 2초, 블록 +1 2) 블록 추가: 1초, 블록 - 1 주어진 블록의 개수로 최대한 빠르게 평평하게 만드는 문제입니다. 동일한 시간이 걸릴 경우, 더 높은 경우를 출력해야 합니다. 2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [Algori.. 2022. 2. 11.
[구현/수학] 백준 2869 달팽이는 올라가고 싶다 - Python [ Contents ] 1. 문제 (링크 참조) 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 2. 문제 풀이 아침에 A만큼 올라가고, 밤에 B만큼 내려가는 달팽이가 있습니다. 높이 V미터까지 올라가는 데 며칠이 걸리는지 구하는 문제입니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적절한 출력만 하면 됩니다. 특별한 알고리즘이나 프로그래밍적 기법.. 2022. 2. 11.
[구현/수학] 백준 2108 통계학 - Python [ Contents ] 1. 문제 (링크 참조) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 2. 문제 풀이 N개의 수열의 '산술평균', '중앙값', '최빈값', '범위'를 구하는 문제입니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적절한 출력만 하면 됩니다. 특별한 알고리즘이나 프로그래밍적 기법 .. 2022. 2. 10.
[정렬/탐색] 백준 2805 나무 자르기 - Python [ Contents ] 1. 문제 (링크 참조) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 2. 문제 풀이 N개의 나무를 동일한 높이로 잘라서 최소 M 크기의 나무토막을 구하는 문제입니다. 이 때, 나무 높이를 최대로 해서 낭비되는 나무를 줄여야 합니다. 나무 높이를 h로 자를 때, h보다 작은 나무들은 잘라지지 않습니다. 2022.02.10 - [Algorithm] - [정렬/탐색] 백준 1654 랜선 자르기 - Python [정렬/탐색] 백준 1654 랜선 자르.. 2022. 2. 10.

티스토리툴바