겜돌이의 개발일지

문제 백준 4485 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 처음에 오른쪽, 아래쪽으로만 이동 가능한 줄 알고, 'DP로 쉽게 풀리겠네'라고 잘못 생각했다. 상하좌우 이동이 모두 가능하기 때문에 다익스트라로 해결해야 한다. struct 타입을 새로 정의하고 우선순위 큐에 넣으면 비교가 불가하기 때문에 에러가 발생한다. 오퍼레이터를 정의해줘서, 오름차순으로 PQ에 들어가게 해 주었다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 16235 나무 재테크 C++ 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 가장 싫어하는 부류인 빡구현 문제입니다,,, 주어진 조건대로 차근차근 구현하였습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6..

문제 백준 14002 가장 긴 증가하는 부분 수열 4 C++ 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 LIS 구하기의 경우 DP로 해결하면 O(N^2)의 시간복잡도를 가집니다. N = 1000이므로 DP로도 해결가능해 DP로 풀었습니다. N이 더 커진다면 이분 탐색을 활용해야 합니다. 최장 증가 부분 수열의 경로도 출력해줘야하는데, 부모를 설정하면 경로를 쉽게 표시할 수 있습니다. 소스 코드 1 2 3 4 5 6 7 ..

문제 백준 1963 소수 경로 C++ 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 1. 에라토스테네스의 체를 사용하여 1 ~ 9999까지 소수 판정을 한다. 1-1. 999 이하의 수는 비밀번호로 허용되지 않으므로 소수가 아니라고 설정한다. 2. bfs로 루프를 돌면서 해당 숫자에서 한 자리만 바꾼 수가 소수인 경우만 Queue에 push 해준다. 3. cnt를 따로 체크해주면서, 변환이 가능하면 cnt를 출력하고 불가능하면 Impossible을 출력한다. 한 자리만 다른 수 만드는 로직을 string을 통해..

문제 백준 5052 전화번호 목록 C++ 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 트라이나 정렬을 이용합니다 1) 정렬로 풀이 1. 문자열을 모두 입력 받은 후 오름차순 정렬합니다. -> 문자열 순서가 작은 것이 앞으로 오고, 순서가 같다면 string 길이가 더 작은 것이 앞으로 옵니다. 2. i번째 문자열이 i+1문자열의 앞과 똑같다면 일관성이 없으므로 루프를 중단하고 NO를 출력합니다. 3. N-1번째 문자열까지 똑같지 않다면 일관성이 있으므로 YES를 출력합니다. 소..

문제 백준 13913 숨바꼭질 4 C++ 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질에서 경로를 저장하는 배열 vector만 추가해주면 될 줄 알았더니 메모리 초과가 떴습니다. 곰곰히 생각해보니 방문하는 모든 지점을 각각의 queue에 저장하는 것이 문제였습니다. 따라서 가장 처음 해당 지점을 방문할 때, 어디서 방문했는지 저장하는 배열을 선언하여 최단 경로만을 저장하는 방식으로 해결하였습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

문제 백준 1715 카드 정렬하기 C++ 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 최소로 비교하는 방법은 작은 값부터 합치는 것이다. 방법은 다음과 같다. 1. 오름차순으로 queue를 정리한다. 2. 최소값 두 개를 꺼내고 합친 값을 queue에 다시 푸쉬 3. queue 사이즈가 1이라면 출력 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ..

문제 백준 2096 내려가기 C++ 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 Max, Min 값 등을 배열로 정리했으면 더 깔끔한 코드가 나왔을 것 같다. 메모리 초과에 유의하여 10만 크기의 배열을 선언하지않고, 전 단계 값만 저장하면서 갱신해준다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include using namesp..

문제 프로그래머스 42898 등굣길 C++ 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 해당 좌표가 웅덩이인지 저장하는 water배열을 선언하고, 웅덩이 좌표를 넣어줍니다. 그 이후에는 일반적인 길찾기 처럼 DP를 이용하되, 웅덩이일 경우에는 경로를 계산하지 않고 넘어갑니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #includ..

문제 프로그래머스 43105 정수 삼각형 C++ 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 지금까지의 경로의 합 중 최댓값을 저장해놓은 배열을 DP라고 선언합니다. DP는 다음과 같은 규칙을 따릅니다. 1. 줄의 첫 칸 일 경우 : 자신의 DP값 = 전 줄의 첫 칸의 DP값 + 자신의 값 2. 줄의 마지막 칸 일 경우 : 자신의 DP값 = 전 줄의 마지막 칸(j-1)의 DP값 + 자신의 값 3. 그 외의 경우 : 자신의 DP값 = 전 줄의 j-1, j번째 DP값 충 더 큰 값 + 자신의 값 삼각형의 값은 0이상이므로 마지막 줄인 경우에만 최댓값을 갱신해주면 됩니다. 소스 코..