포시코딩

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 문제를 풀 때 항상 헷갈리는 문제 중 하나인 이진 탐색을 쉽게 푸는 방법에 대해 소개해보고자 한다. 위 문제를 예로 설명하겠음 문제 정리 문제를 요약하면 다음과 같다. 강의의 수 = N, 블루레이 개수 = M, 강의 길이 배열 = arr M개의 블루레이에 강의를 나눠 담을 때 블루레이 크기의 최소값 구하기 = 정답 블루레이 크기를 평균값을 통해 유추하며 줄여나가 조건에 부합하는 최소값을 되기에..

문제 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 문제 풀이 방식이 독특해 포스팅하게 되었다. 이 문제는 기본적으로 정규 분포 형태를 띄게 가운데에 제일 높은 수를, 그 이후 양쪽에 낮은 숫자들을 배치해가면 차이가 최소인 형태를 얻을 수 있는걸 이용해서 풀 수 있다. 풀이 import sys input = sys.stdin.readline for _ in range(int(input())): N = int(input()) arr = lis..

위상 정렬이란? 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘 최소힙인 heapq를 통해 위상 정렬 알고리즘을 구현할 수 있다. 시간복잡도 O(V+E) V: 노드(=Vertex) E: 간선(=Edge) 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 코드 import heapq N, M = map(int, input().split()) arr = [[] for _ in rang..

문제 https://www.acmicpc.net/problem/1233 1233번: 주사위 지민이는 주사위 던지기 게임을 좋아하여 어느 날 옆에 있는 동호를 설득하여 주사위 던지기 게임을 하자고 하였다. 총 3개의 주사위가 있다. 그리고 이 주사위는 각각 S1(2 ≤ S1 ≤ 20), S2(2 ≤ S2 www.acmicpc.net 브론즈 2의 난이도 문제 치고 푸는데 생각도 오래 하고 걸리기도 오래 걸린데다 푸는 방법도 여러 방법으로 나와서 따로 포스팅하게 되었다. 일단 들어가기 앞서 완전 탐색만 알았지 브루트 포스는 처음 들어보는 알고리즘이었는데 알고보니 둘 다 같은 말이었다. brute = 단순히, 짐승이란 뜻 force = 힘 그냥 짐승처럼 힘만 갖고 밀어붙인다는 뜻으로 0000부터 9999까지 가..

문제 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 시간 제한과 메모리 제한도 넉넉하기 때문에 파이썬에서 문자열을 아스키 코드로 변환하는 함수를 알면 쉽게 풀 수 있는 문제다. 난이도도 solved.ac 기준 브론즈 2로 낮은 편에 속한다. 내 풀이 S = input() for x in range(ord('a'), ord('z')+1): print(S.find(chr(x)), end=' ') 알파벳의 아스키 코드 변환 함수인 or..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이코테의 떡볶이 떡 만들기 문제와 동일하다. 구현 이진 탐색에 대해서는 숫자로 이루어진 배열 안에서 특정 숫자가 존재하는지 찾는거에 대해서만 배운 상태였어서 이진 탐색을 활용해 어떻게 푸는지도 감을 잡지 못했는데 파라메트릭 서치 알고리즘으로 풀면 된다는 해설을 보면서 점점 이해가 됐던 것 같다. 파라메트릭 서치로 문제를 바라보면 다음과 같다. 최적화 N..

문제 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 구현 '공유기 간의 거리'를 줄이면 설치 가능한 '공유기 대수'가 늘어나고 거리를 늘리면 설치 가능한 '공유기 대수'가 줄어든다. 반대로, 설치 가능한 '공유기 대수'가 적다면 거리가 너무 길다는 뜻이니 거리를 줄여 설치 가능 대수를 늘릴 수 있고 설치 가능 대수가 '크거나 같다면' 거리를 늘리면서 (최대거리를 구해야 하니) 최대 거리도 만..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 코드 N, r, c = map(int, input().split()) def z(n, x, y): global result if n == 2: if x == r and y == c: print(result) return result += 1 if x == r and y+1 == c: print(result) return result += 1 if x+1 == r and y == c:..

개요 재귀 호출 시 반복되는 작업에 대한 결과를 계속 반복 수행하는게 아닌 따로 저장해놓고(캐싱) 갖다 쓰는 방법을 다이나믹 프로그래밍이라 한다. 문제 https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 한 예로 위 문제에 대해 재귀 함수를 사용한다면 금방 제시되는 입/출력을 구현해낼 수 있을 것이다. 하지만 그대로 코드를 제출하면 시간 초과가 나온다. 코드 1 n = int(input()) def recursio..

문제 NxN 격자판이 주어지며, 격자판의 각 칸에는 숫자가 적혀있습니다. 격자판의 정중앙에서 출발하여, 상하좌우로 이동하며 같은 테두리 안과 그 바깥 테두리 방향으로 이동할 수 있습니다. 이때, 정중앙으로 돌아올 수 없습니다. 이동하며 밟은 칸의 숫자를 모두 더해 최소값이 되는 값을 구하세요. 입력: N (3 ≤ N ≤ 1000, N은 홀수) board : NxN 크기의 격자판을 1차원 리스트로 표현한 것으로, 길이는 N^2입니다. 각 칸에 있는 숫자는 0 이상 9 이하입니다. 출력: 격자판의 정중앙에서 상하좌우로 이동하며 밟은 칸의 숫자를 모두 더해 최소값이 되는 값을 출력합니다. 입력 예시: N = 5 board = [9, 3, 9, 9, 9, 5, 2, 7, 8, 9, 8, 1, 5, 8, 9, 6..