개발하는 사막여우

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 소스코드 풀이 다른 분들 풀이를 보면 팩토리얼을 사용해서 푸신 분들도 있으신 거 같은데 전 DP로 풀었습니다 ! solved.ac 기준 실버 5 문제인데, 생각보다는 규칙을 찾는데 조금 시간이 걸렸던 거 같아요 ! 먼저 문제를 풀기 위해 기억해야 할 몇가지가 있습니다. 1. 서쪽 사이트와 동쪽 사이트의 개수가 같으면 설치할 수 있는 다리는 1개이다. 2. 서쪽에 1개, 동쪽에 n개가 있으면 다리는..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 소스코드 풀이 이전에 블로그에 포스팅 했던 '가장 긴 증가하는 부분 수열' 문제와 접근법은 동일합니다 ! 한번 참고해보시면 좋을 거 같아요 그에 반대인 가장 긴 감소하는 부분 수열같은 경우에는 접근법은 똑같이 가져가되, a[::-1] -> 수열을 거꾸로 뒤집에서 연산을 진행하였습니다 ! https://hyul-mode.ti..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 소스코드 풀이 다이나믹 프로그래밍 DP로 푸는 문제입니다 ! 주어진 수열에 대해 증가하는 부분 수열을 작성하고, 부분 수열의 길이가 가장 긴 것들을 적어보면 다음과 같습니다. 이 때, 수열 중 첫 숫자인 10은 만들 수 있는 수열이 자기 자신 밖에 없기 때문에 길이가 1이 되고, 변수 length에는 1이 저장됩니다. ..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 소스코드 풀이 동적 계획법 DP로 푸는 문제입니다. 먼저 0층에 거주하는 사람, i호에는 i명이 살고 있습니다. 즉, 0층에는 1호: 1명, 2호: 2명, 3호: 3명 ... 이런 식으로 사람이 살고 있습니다. 1층부터는 바로 아래층의 1호부터, 입력으로 주어지는 n호까지의 합의 사람이 해당 층 n호에 살고 있습니다. 3층, 4호에 사는 사람까지 나타내면 위와 같이 나타낼 수 있습니다. 이러한 방식으로 코드로 구현하는데, 각 층의 해당 ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 소스코드 풀이 다이나믹 프로그래밍 알고리즘에 분류되어 있는 피보나치 문제입니다 ! 보통 DP 문제는 점화식으로 되어있고, for문을 쓰거나 DFS를 활용하여 풀 수 있습니다 ! 저는 보통 for문으로 접근하는 게 조금 더 간편한 거 같습니당 먼저 2차원 배열을 만들어 주셔야 합니다. 이때 배열 안에 0과 1을 넣어줄 공간이 필요한데, 이는 안쪽 배열 생성과정에서 for문으로 두개의 공간을 만들어주시면 됩니다 ! 입력 값이 0이나 1이 들어오는 경우는 저희가 알 수 있기에 if문으로 따로 출력 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 소스코드 런타임 에러 뜬 코드(IndexError) 풀이 다이나믹 프로그래밍이라고 불리는 동적 계획법을 활용하여 풀 수 있는 문제입니다 ! dy라는 리스트에는 입력 받은 n을 1로 만들기 위한 최소 연산 횟수가 저장됩니다. (n+1)로 설정해준 이유는 리스트의 인덱스는 0부터 시작하기 때문에 1로 시작점을 잡기 위해서 입니다 dy[i] = dy[i-1] + 1 만약 다른 조건 없이 n을 1로 만드는 최소 연산 횟수를 구한다고 하면, dy[1] = 0 (1을 1로 만들기 위한 연산횟수는 0회) dy[2] = 1 ..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 소스코드 pypy3 python3 풀이 정답률은 낮지만 그렇게 어렵지 않은 문제입니다. 크레인으로 가장 무거운 무게부터 옮겨보고, 옮기지 못하면 시간을 출력해주면 됩니다 ! 맞게 했다고 생각했는데 python으로 코드를 제출해보니 계속해서 시간초과가 나왔고, 구글링을 해보니 pypy3로 제출하신 분들이 많아서 해보니 정상적으로 정답이 나오는 것을 확인할 수 있었습니다 ! pytho..

https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 소스코드 풀이 정답 비율이 50%가 안넘는 게 이상하긴 한데 어렵지 않은 문제입니다 ! 입력 받은 값에서 최대값을 찾아주고, 그 최대값으로 입력 값들을 하나씩 나눠준 뒤, 100을 곱해주면 되는 문제입니다 ! 저는 두가지 방법으로 풀어봤는데, 코드 길이는 첫번째가 더 짧고 편한데 시간은 2번째 코드가 더 짧게 나오더라구요 ! 파이썬이 익숙하신 분들은 첫번째 방법으로 하셔도 좋을 거 같아요 ㅎㅎ

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 소스코드 풀이 문제의 핵심은 '-'를 만나기 전의 수들을 총합에 더해줘야 하며, '-'를 만난 이후의 수들을 총합에서 빼줘야 한다는 점입니다. 파이썬에는 split()이라는 함수가 있습니다. split()함수를 사용하여, '-'를 기준으로 입력 값을 나눕니다. 나눈 값이 또다시 연산으로 되어 있을 수 있기 때문에 그 값을 '+'를 기준으로 다시 한번 나눠줍니다. 나눠 준 후에는 그 값들을 모..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 소스코드 풀이 그리디 알고리즘 분류를 보다가 제목이 재밌어서 한번 풀어봤슴당 ! 처음엔 스택을 사용할 생각을 하지 않았고, 알파벳이 나오는 순서에 따라 PPAP를 치환해주는 식의 방법으로 문제를 해결하려고 했습니다. 근데 생각보다 시간 초과가 계속 떠서 구글링을 해보니, 다들 스택으로 푸셨더라구요 ! 처음 생각해봤던 방법은 계속해서 연구해볼 생각입니당 ! 제가 생각하는 문제의 핵심은 PPAP가 P와 동일하다는 것입니다 ! 처음엔 PPAP를 발견하면..