개발하는 사막여우

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를 발견하면..

https://www.acmicpc.net/problem/10812 10812번: 바구니 순서 바꾸기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 소스코드 풀이 리스트의 슬라이싱 기능을 활용하면 금방 풀 수 있는 문제입니다. 저는 범위 값 안에 있는 리스트를 mid를 기준으로 두개로 나눴고, 순서를 바꿔서 '+' 해줬습니다 여기서 주의할 점은 리스트의 인덱스는 0부터 시작한다는 점입니다 ! 그래서 숫자 1을 사용하기 위해선 '리스트[0]'를 해줘야 합니당 ㅎㅎ

https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 소스코드 풀이 단어를 앞으로 읽었을 때와 거꾸로 읽었을 때가 똑같은 경우를 찾는 일반적인 팰린드롬 문제입니다. 하지만 여기서 주의해야 할 점은 input으로 받는 입력 값입니다. 저 같은 경우에는 sys 모듈을 import 하여 입력 값을 받는데 'sys.stdin.readline()' 구문은 자동으로 줄바꿈('\n')이 추가되는 성질이 있습니다. (일반 input()과는 다름) 그렇기에 뒤에 strip() 함수를 사용하여 공백을 제거해줘야 합니다. ..