겜돌이의 개발일지

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 map을 이용해서 풀었다. 개수가 50만개라서 시간초과를 걱정하고 풀었는데, 아슬아슬했던 것 같다. 이분 탐색을 쓰면 더 효율적으로 풀 수 있는듯? map 자체도 이분 탐색이긴 하다만 upper_bound와 lower_bound를 쓰면 더 빠르게 풀 수 있다고 함. 소스 코드 map으로 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

문제 백준 1092 배 C++ 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 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 #include #include using namespace std; int main() ..

문제 백준 11058 크리보드 C++ 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 풀이 DP 문제인데 점화식을 떠올리기가 어려웠다. 처음에 방문체크를 해주는 BFS로 풀려고 했지만... 경우가 많아도 너무 많아서 포기 dp[i]의 최댓값은 다음 중 하나이다. 1. dp[i-1] + 1 2. Ctrl + A, Ctrl + C의 2단계를 거쳐 복사, Ctrl + V로 한 번 붙..

문제 백준 12094 A와 B C++ 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 처음에 S에서 A, B를 붙여주는 BFS로 접근했다가, 길이가 1000 까지기 때문에 메모리 초과가 났습니다. 역으로 T 문자열의 뒤에서부터 접근하여, S와 똑같이 만들어 줄 수 있는지 검사합니다. 소스 코드 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 #include #include #inclu..

문제 백준 17142 연구소 3 C++ 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 빡구현류의 브루트 포스 + BFS + 시뮬레이션 문제입니다. 1. 바이러스를 M개 만큼 선택한다. (조합 이용) 2. 바이러스를 확산하고 최소 시간을 갱신한다. 소스 코드 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 5..

문제 백준준 1600 말이 되고픈 원숭이 C++ 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 방문을 [y][x][말 이동 사용 횟수]로 체크합니다. bfs를 돌면서, 각각의 지점에서 말 / 원숭이로 이동할 수 있는 지점을 queue에 push합니다. 소스 코드 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 4..

문제 백준 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을 통해..