2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 첫번째 시도) N번째 큰 수를 단순히 최대힙을 만들어 구하려고 했다. 1 ≤ N ≤ 1500 라는 N의 범위값과 12MB라는 메모리 공간 제한 때문에 메모리 제한이 나왔다. from sys import stdin from heapq import heappush, heappop input = stdin.readline n = int(input()) arr = [] tmp_arr = [] for _ in range(n): tmp_arr = list(map(int,..

9251번: LCSLCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.www.acmicpc.net문제풀이두 문자열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴것의 길이를 찾는 문제이다. 수열은 사용자의 입력을 받으므로 될 수 있는 경우의 수는 무한에 가깝다. 따라서 이 문제는 DP로 푸는것이 적절하다.먼저 문자열 두개를 입력받아 한 글자씩 쪼개며 각각의 list에 저장한다. 그 다음  indexError을 피하기 위해 0번째 index에 값으로 0을 넣어주고 그 다음 dp배열을 2차원배열로 선언하며 길이를..

11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net문제풀이N N은 자연수)의 조건을 보고 시간복잡도상 2중 for문을 사용할 수 있는 것을 알았다. 경우의 수가 너무 많기에  DP로 푸는 문제임을 직관적으로 알 수 있었고 인덱스가 증가함에 따라 값이 증가해서 부분수열의 길이가 늘어나야한다면 현재까지의 부분수열의 길이와 이전 상황들에 대한 부분수열의 길이를 비교해서 더 큰 값을 현재까지의 부분수열의 길이로 정할 수 있다.따라서 점화식은 아래와..

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제풀이 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 전형적인 DP문제이다. 먼저 DP배열을 2차원 배열로 초기화해서 선언하고 그 안을 점화식으로 채워넣는 방식의 논리를 사용했다. 1. K가 1일때는 수 하나로 N을 표시해야하므로 경우의 수는 반드시 1개이다. 2. N이 1일때는 K-1개의 0과 1개의 1이 필요하므로 경우의 수는 K의 증가율과 같이 증가한다. 3. 여기서 예시를 직접 쓰다가 점화식을 찾았다. 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] 개념적으로 생각했을때 당연하게도 다음수까지의 경우의 수를 구하려면 이전 수까지..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제풀이 경우의 수 문제이며 메모리 제한과 시간 제한을 따져봤을 때 DP를 사용해서 풀어야함을 알 수 있었다. k원을 만들기 위해 1

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제풀이 n의 범위는 1 = 3: dp[2] = dp[1] + 1 for i in range(3, n): dp[i] = dp[i - 1] + dp[i - 2] print(dp[-1] % div) solve()

과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2579" data-og-url="https://www.acmicpc.net/problem/2579" data-og-image="https://scrap.kakaocdn.net/dn/cFezLf/hyU2tSZnOh/waRUJkQXiM6NkDnkZcjGOK/img.png?width=2834&height=1480&face=0_0_2834_1480,https://scrap.kakaocdn.net/dn/bVfUC0/hyU2tSZnLT/XIkAt4sQ9OkLY7yFBGRwvK..

17298번: 오큰수첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.www.acmicpc.net문제풀이스택을 이용해서 풀었다. N의 최대값이 1,000,000이기 때문에 O(N^2)으로는 절대 풀 수 없었기에 배열을 순회하는 것은 불가능하다고 생각했다. 그래서 오큰수 배열인 NGE배열을 [-1]로 N의 크기만큼 초기화 시켜놓은 후, 어차피 NGE배열의 크기와 입력받은 배열의 크기가 같기때문에 값의 비교를 통해 값과 인덱스를 스택에 저장시켜 NGE배열에 넣어주는 과정을 거쳤다.1. N과 arr을 입력받고 NGE배열을 -1로 N의 크기만큼 초기화시키고 stack을 빈 리스트로..

3190번: 뱀'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임www.acmicpc.net문제풀이이 문제는 근본적으로 뱀이 움직일때마다 움직인 뱀의 머리를 큐에 저장하고 뱀의 꼬리를 큐에서 pop하는 문제이다.자세하게는 맵에 놓인 사과를 먹으면 꼬리를 pop하지 않고 사과를 먹지 못하면 pop한다. 그러다가 뱀이 자기자신의 몸과 닿거나 맵을 나가는경우 종료시킨다.이 문제를 풀면서 유의해야했던 점은 뱀의 방향설정과 사과가 먹혔다면 먹힌 사과를 삭제해야하는 부분이었다.맵에서 사과를 삭제해야하는 개념은 문제의 예제에서 확인할 수 없어 스스로 검증해야한다.1. 먼저 입..

5430번: AC각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.www.acmicpc.net문제선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.배..