분류 전체보기 (47) 썸네일형 리스트형 python 백준2748 피보나치 수 2(BOJ2748) 문제링크 : https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net for문에 별찍기가 있다면 dp에는 피보나치가 있다!@! 정말 가장 기본적인 구조인데 이 구조를 다른문제에도 적용하는게 어렵다.. 점화식을 구하고 어디까지 초기값으로 잡고 어느구간에서부터 반복문으로 돌릴지를 파악하는게 핵심인것같다 알면 뭐하나.. 잘 안되는걸ㅜㅜ import sys input = sys.stdin.readline #메모이제이션dp테이.. python 백준2775 부녀회장이 될테야(BOJ2775) 문제링크 : https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 간단한 dp문제인데 시간제한 1초에 층수 호수도 14층뿐이라 O(n^3)= 14세제곱 이어도 충분하길래 그냥 인원수 싹 다 구하고나서 결과값 출력했다. 인원수를 구하면서 한방에 리턴하는 방법으로도 할수있을것이다 내가 제출 한 코드 import sys input = sys.stdin.readline #테스트 케이스 t = int(input()) #층수 리스트 k_list = [] #호수 리스트 n_list = [] #입력 fo.. python 백준11000 강의실 배정(BOJ11000) 문제링크 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 이해하는건 쉬운데 오히려 이런 문제들이 풀기가 더 어려운것같다.. 처음엔 재귀방법으로, 그리고 2중for문 방법으로 풀었는데 전부 시간초과가 나왔다 문제를 다시 보면 건수는 200,000건인데 이걸 시간제한 1초만에 풀려면 최소 O(NlogN) 시간복잡도로 풀어야된다. 그래서 2중for문으로 풀면 당연히 시간초과.. 전에 정렬 글에서 썼듯이 연산속도는 초당 1억건 정도이기때문에 2중for문은 200000^2 = 400억이라서 .. python 백준15686 치킨 배달(BOJ15686) 문제링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 처음에 문제읽다가 이게 뭐말이래..했는데 생각보다 할만했다 한방에 통과! from itertools import combinations import sys input = sys.stdin.readline #도시사이즈n , 고를 치킨집 개수m n, m = map(int, input().split()) input_map = [] zip = [] chicken = [].. python 백준9095 1, 2, 3 더하기(BOJ9095 ) 문제링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이건 내가 알고리즘 유형에서 DP눌러서 나온 문제라서 DP로 풀었다 문제에서 점화식을 도출한다음 리스트에 초기값을 저장해둔다 그리고 반복문을 통해서 점화식을 통해 리스트 값을 불러와서 새롭게 추가하는 형태로풀었다(메모이제이션) 이렇게 하면 재귀로 호출할때와 달리 한번 계산한 값을 또 다시 계산하지 않아도 되기때문에 좋타 아직 DP문제를 많이 풀어보질못해서 메모이제이션기법 말고는 해본게 읎다.. 이거 보는 사람은 아마 풀다가 막혀서 보는사람일텐데 여기까지만 읽고 다시한번 고민해보는거 .. python 백준14502 연구소(BOJ14502) 문제링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이문제는 아이디어 떠올리는 데만 2시간이 걸린것같다..아이디어를 떠올리는게 정말 어려웠다 혹시나 아이디어만 얻기위한 사람이 있을수 있어서 내가 풀었던 아이디어만 먼저 공유한다 문제해결 아이디어 1) 연구소 지도에서 벽 3개를 세운다 2) 벽을 세운 지도로 바이러스 확산 시뮬레이션을 해본다 3) 시뮬레이션 후 빈공간 갯수를 비교해본다 4) 1~3번 과정을 모든 경우의 수 만큼 반복 아래 코드도 처음.. python 백준2667 단지번호붙이기(BOJ2667) 문제링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net dfs를 공부하면서 나왔던 예시문제와 비슷하다 상하좌우를 dx, dy로 해서 풀면 쪼금 더 짧게도 가능할것같다 #지도크기 n = int(input()) #단지 집 수가 담길 리스트 house_count = [] #입력으로 받는 지도 리스트 input_map = [] for _ in range(n): #지도에 추가 input_map.append(list(map(int, input()))).. python 백준1193 분수찾기(BOJ1193) 문제링크 : https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 구현문제는 규칙을 뽑아내면 코드로 만드는것자체는 어렵지 않은것같다 그런데 처음 문제를 읽으면 '이걸 뭐 어쩌라고?' 생각이 들긴하는데 일단 예시를 손으로 쓰면서 규칙을 찾는 연습을 해야겠다 뭐 하다보면 늘지않을까? x = int(input()) row = 1 col = 1 jump = False v = 1 multiple = 1 while True: if x == v: break if jump : v += (4 * multiple) multiple += 1 jump = False col += 1 if x 이전 1 2 3 4 5 6 다음
