Gemstone's Devlog

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제를 처음 풀었을 때 냅색(Knapsack) 알고리즘에 대해서 몰랐었기 때문에 일반적인 dp로 해결하려고 했었다. https://velog.io/@uoayop/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 냅색 알고리즘 골라골라 velog.io 이 분이 잘 설명해둔 것 같아..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 교양시간에 수업은 안듣고 solved.ac Class4 문제들을 뒤적거리다가 재밌어 보여서 풀어봤던 문제였다. 구현 문제이기도 했고 문제가 복잡한 것 같아 효율성 따지지 않고 무지성으로 풀었는데, 역시 python3로 제출하니 시간초과가 났고, pypy3로 제출하니 겨우 통과하였다. 무지성 파이썬 코드 import sys input = sys.stdin.readline r, c, t = map(..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 이 문제는 다익스트라 최단 경로 알고리즘의 가장 기본적인 문제이다. 코드는 이것이 코딩 테스트다 책의 챕터 9를 참고하여 작성하였고 통과하였다. 파이썬 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) import heapq # 정점의 개수 n, 간선의 개수 m n, m = map(in..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이 문제는 에라토스테네스의 체 + 투 포인터 문제이다! 전에 풀었던 문제들의 알고리즘 두 개를 섞어 놓은 문제라 신기했다. 급하게 풀어서 코드가 깔끔하지는 않지만 통과하였기 때문에 일단 코드를 올려보겠다. 파이썬 풀이 import math n = int(input()) arr = [False, False] + [True for i in range(n-1)] for i in range(2, int(math.sqrt(n)+1)): if arr[i]: for k in range(i + i, n+1, i): arr[k] =..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 이 문제는 브루트포스 알고리즘으로 접근해야 하는 문제이다. 파이썬 모듈 안에 내장되어있는 조합 라이브러리를 사용했다. 파이썬 풀이 from itertools import permutations import sys # 주어진 값 입력 n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) # permutation 저장(per: ..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 이 문제는 먼저 에라토스테네스의 체를 이용하여 범위 내의 숫자 중 소수를 먼저 판별해야 한다. 그러면 에라토스테네스의 체를 파이썬 코드로 구현하는 방법부터 꼭 암기해두자! https://wikidocs.net/21638 2. 소수 구하기 - 에라토스테네스의 체 # 소수 : 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수이다. # 코딩 소수인지 검사하는 함수(isPr..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 규칙성을 이용하는 DP 문제이다. 우선 그림을 한 번 그려보자. N에 따라서 0과 1이 어떻게 되는지 보자. 이 규칙성을 가지고 DP를 사용하여 구현하면 풀이는 다음과 같다. t = int(input()) for _ in range(t): cnt_0 = [1, 0] cnt_1 = [0, 1] n = int(input()) if n > 1: for i in range(n - 1): cnt_0.append(cnt_1[-1]) cnt_1.append(cnt_0[-2] + cnt_1[-1]..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 이 문제는 DP로 접근해야하는 문제이다. 이중 for문을 돌다가 같은 문자를 만나게 되면 그전까지의 공통 부분 문자열 길이 +1을 dp에 저장한다. 파이썬 코드 ans = 0 s1, s2 = input(), input() dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] for i in range(1, len(s1) + 1): for j ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이 문제는 전형적인 투포인터 알고리즘으로 접근해야하는 문제이다. 우선 투포인터 알고리즘 개념을 다시 정리해보자. 투포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어 있는 두 리스트의 합집하에도 사용됨. 병합정렬(merge sort)의 conquer 영역의 기초가 되기도 함 예제 문제 - 특정한 합을 가지는..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 이 문제는 분할정복으로 접근해야 하는 문제이다. 풀이 방법은 다음과 같다. 1. 모두 0이나 1로 되어있지 않은 경우(조건이 만족하지 않은 경우) 4개로 쪼개서 다시 푸는 방식이다. 조건이 만족하지 않는 경우 괄호 "("를 넣고, 4개로 쪼개고 나서 각 처리를 다 하고 나면, 다시 괄호 ")"를 넣는다. 2. 4개로 쪼개는 것은 재귀함수를 호출하여 풀고, 전달 인자로 그 사분면의 가장..