🥇 Problem Solving

[Python] BOJ / 2294번 / 동전 2

2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 📝 풀이 입력이 다음과 같이 주어졌을 때 3 15 1 5 12 각각의 가치를 만드는데 필요한 동전의 최소 개수는 아래와 같다. 0: 0 (0) 1: 1 (1) 2: 1, 1 (2) 3: 1, 1, 1 (3) 4: 1, 1, 1, 1 (4) 5: 5 (1) 6: 1, 5 (2) 7: 1, 1, 5 (3) 8: 1, 1, 1, 5 (4) 9: 1, 1, 1, 1, 5 (5) 10: 5, 5 (2) 11: 1, 5, 5 (3) 12: 1..

[Python] BOJ / 3109번 / 빵집

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 📝 풀이 그래프 탐색을 통해 가스관과 빵집을 연결하는 파이프라인의 최댓값을 구하는 문제 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 함. 각 칸은 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선으로 연결할 수 있음 (-1, 1), (0, 1), (1, 1) 연결하는 파이프라인은 서로 겹칠 수 없음 visited 배열을 통해 구현 x축이 (c - 1)열에 도착했다는 것은 파이프라인이 성공적으로 연결되었다는 뜻 💻 소스 코드 impo..

[Python] BOJ / 12738번 / 가장 긴 증가하는 부분 수열 3

12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 📝 풀이 LIS 알고리즘 사용 DP 배열을 사용하여 구현할 경우 시간초과가 발생하므로 이분 탐색 알고리즘으로 구현 다만 배열을 정렬하면 안 됨 배열을 따로 생성한 뒤 해당 배열에 오름차순으로 값을 순서대로 추가하여주는 식으로 구현 문제에서 물어보는 건 '가장 긴 증가하는 수열의 길이'이므로 수열의 값과 순서는 상관 없으며 우리는 result 배열의 가장 끝 요소(수열에서 현재까지 찾은 가장 큰 수)만 비교해가며 값을 추가해주면 된다...

[Python] BOJ / 2230번 / 수 고르기

2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 📝 풀이 투 포인터 알고리즘 사용 입력받은 배열 오름차순 정렬 포인터 left = 0, right = 1로 초기화 두 수를 골랐을 때 같은 수일 수 있음 while left < n and right < n 알고리즘 수행 만약 두 포인터가 가리키는 인덱스의 값의 차가 m일 경우 그대로 출력 후 종료(차이가 m 이상이면서 가장 작은 차이는 m이므로) 두 값의 차가 m보다 클 경우 현재까지 구한 최소 차이와 비교하여 더 작을 경우 갱신 더 작은 차..