분류 전체보기 (107) 썸네일형 리스트형 BFS(너비 우선 탐색): 백준 7576 파이썬 토마토 문제: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이: 이 문제의 조건들을 잘 살펴보면 BFS를 사용해서 풀어야 하는 문제임을 알 수 있다. 토마토를 익힐 수 있는 최소일 수 주변의 토마토를 익힘 간선의 가중치는 모두 1 입력받은 토마토 정보 중 익어있는 토마토의 좌표를 큐에 저장하고, bfs를 사용해 주변의 토마토들을 익혀 나가면 된다. 주변의 토마토가 익었다면 토마토 배열에 +1을 해주어 그래프에 익힌 일 수가 저장되.. 그리디: 백준 11399 파이썬 문제: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이: 이 문제는 단순히 돈을 인출하는데 걸린 시간 P가 저장되어있는 배열을 정렬하고, 누적합을 구하면 되는 문제이다. for문을 두 번 사용해서도 풀 수 있지만, 시간 복잡도를 줄이기 위해 for문을 한 번만 쓰는 방법을 생각하다가 다이나믹 프로그래밍 기법(동적 계획법)을 떠올렸다. 이 문제는 다이나믹 프로그래밍의 조건인 1. 큰 문제를 작은 문제로 나눌 수 있는가, 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰.. DP(다이나믹 프로그래밍): 백준 11727 파이썬 문제: https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이: 이 문제는 11726번 문제 '2 x n 타일링'에서 타일 하나를 더 추가한 문제이다. 2021.09.12 - [Python 코딩테스트] - DP(다이나믹 프로그래밍): 백준 11726 파이썬 DP(다이나믹 프로그래밍): 백준 11726 파이썬 문제: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를.. DP(다이나믹 프로그래밍): 백준 1463 파이썬 문제: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이: 이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다. 예를 들어 n=6일 때, 함수가 호출되는 과정을 보면 다음과 같을 것이다. 확인해보면, 마찬가지로 f(2)와 같은 함수들이 동일하게 여러 번 호출되는 것을 알 수 있다. 이 문제에서 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다. 이제 문제에서 요구하는 내용을 점화식으로 표현해보자. 점화식 끝에 1을 더해주는 이유.. 다이나믹 프로그래밍(동적 계획법) 다이나믹 프로그래밍: 중복되는 연산을 줄이자 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법이다. 다이나믹 프로그래밍(Dynamic Programming) 기법은 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 살펴보자. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치수열은 다음과 같은 형태로 끝없이 이어진다. 수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게.. 토익스피킹 파트별 템플릿 활용법 Part 2 Describe a picture Level 6 두 가지 유형별 템플릿 암기 인물의 동작 묘사 표현 암기 (p.72~73 참고) Level 6를 목표로 한다면 두 가지 유형별 템플릿을 확실하게 암기해야 한다. 두 가지 유형에는 사람이 중심이 되는 인물 중심 유형, 그리고 사물과 배경 중심 유형이 있다. 이 두 유형의 답변을 어떻게 만들어가야 하는지 확실하게 알아두어야 한다. 사물과 배경보다는 인물 중심히 훨씬 출제 비율이 높기 때문에 고득점을 위해서는 사람의 동작 묘사 표현을 확실하게 암기해 두어야 한다. Level 7+ 도전 레벨 7+ 고득점 표현 학습 (p.62~65) Level 7을 목표로 한다면 교재 후반부의 도전 레벨7 고득점 표현을 확실하게 익혀 둘 필요가 있다. 여기엔 세 가지가.. 이진 탐색(이분 탐색): 백준 2110 파이썬 문제: https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이: 이 문제는 처음에 이해하기가 다소 어려웠다. 문제에서 집 좌표의 범위가 (0 ≤ x ≤ 1,000,000,000)와 같아서 이진 탐색을 사용해야 하겠다는 생각은 들었지만, 찾아야 하는 수 target을 어떤 것으로 할지 떠오르지 않았다. 구글링을 해서 힌트를 얻어 문제를 풀 수 있었다. 이 문제는 이진 탐색의 방법을 응용해서 해결하.. 이진 탐색(이분 탐색): 백준 2805 파이썬 문제: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답: import sys n, m = map(int, sys.stdin.readline().split()) wood = list(map(int, sys.stdin.readline().split())) # 이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(wood) result = 0 # 이진 탐색 수행 while(start m.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 14 다음
