Doby's Lab

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 읽으면 쉽게 BFS를 떠올릴 수 있다. 하지만, 문제를 풀면서 실수도 하고, 최적화를 생각하지 못해서 많이 틀렸던 문제다. 정리를 하는 이유는 이런 실수가 있었다. 다음부터는 그러지 말자의 의미. [솔루션] 아마 사람들이 좀 많이 헷갈리지 않을까 싶은 부분은 '명령어를 어떻게 저장할 것인가? (구할 것인가?)' >> 간단하다, pair형 큐를 선언하고 한쪽에는 숫자(int), ..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이번 문제는 블로그 활동에 대해 성취감을 주는 문제였다. >> 최근 들어 블로그에 정리해둔 내용들을 직접 써먹는(?) 기회들이 많았다. 1) 우선 3개의 열을 가진 배열을 사용하여 DP를 돌려야겠다는 생각은 다음 문제들로부터 영감을 얻었다. (1. 1309번 정리 https://draw-code-boy.tistory.com/87) (2. 2249번 정리 https://draw-code-boy.tistory.co..

어떠한 배열이 있을 때 이전까지는 for문을 사용했다. check라는 배열의 모든 원소들을 -1로 초기화시키고 싶다고 하면 (check 배열의 크기는 1000) for (int i = 0; i < 1000; i++) { check[i] = -1; } 크게 귀찮음은 못 느꼈지만 한 번 memset 함수를 쓰고 나니 약간의 손 노동이었구나를 느낀다. 위 코드를 memset 함수를 사용하면 memset(check, -1, sizeof(check)); 즉, memset(초기화시키려는 배열, value, 그 배열의 사이즈);와 같은 형태로 사용하면 된다. 에 선언되어있음. [중요!] 메모리 관련 문제 때문에 -1 or 0이 아니면 memset을 쓰면 안 된다. for를 돌리거나 fill이라는 함수를 써야 함. 자..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이번 문제는 개인적으로 너무 아쉬웠다. 각 항의 관계성까지 파악하고, 이런 비슷한 문제가 있었던 걸 기억하여 비슷하게 구현해보려 했는데 구현이 되지 않아서 거의 90%까지 왔지만 결론적으로는 풀지 못 한 문제다. [기억했던 비슷한 문제] https://draw-code-boy.tistory.com/51?category=963936 [알고리즘] 백준 1149번: RGB거리 (C++), 점화식... '점화식을 어떻게 세울 것인가'가 큰 관건이었다. '큰 문제를 작은 문제로 나누자'라는 키워드는 이제 금방 떠오르고, 나눌 수 있었지만 ..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net (11055, 17216, 11722번은 다루지 않을 예정 >> 조금만 응용하면 되는 문제라 다룰 필요가 없다고 생각함.) 이 문제를 풀기 위해서는 어렵게 생각할 필요 없었다. 기존에 '가장 긴 증가하는 부분 수열 문제의 점화식에서 어떤 것을 추가해야 할까?'라는 생각으로 시작했다가 그럴 필요가 없다고 느껴졌다. 영감을 받은 문제가 있다. https://draw-code-boy.tistory.com/51?catego..

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 '가장 긴 증가하는 부분 수열(LIS)' 문제는 이분 탐색 공부할 때, 처음 존재를 알고, 그 뒤로 종종 어디선가 계속 보이길래 LIS라는 키워드가 유명한 건지 LIS라는 알고리즘이 따로 있는 건지 궁금했다. 그 뒤로 DP를 풀면서 정면으로 마주치게 되었다. LIS(Longest Incresing Subsequence)..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제에 들어가기 앞서 (1) 이번 문제는 이때까지 겪어온 '빡구현' 문제들을 애기로 만들어버리는 수준이다. 걸어야 할 조건들이 엄청 많다. 1) 처음엔 DFS로 했을 때, DFS로는 안 되겠다. BFS로 해야지. (종료 조건이 없었음) 2) BFS로 했을 때, 이 무한 루프 어떻게 처리하지? 3) 방문 체크를 해야겠구나? 그러면.. 따질 게 많은데 싹 갈아엎어야 하나? 2번을 갈아엎었다. ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 요즘 블로그 임시저장 기능을 너무 많이 사용하는 거 같아서 조금 정리 차원에서 글을 쓴다. 핑계를 덧붙이자면 임시저장 글 중에 '가장 긴 증가하는 부분 수열 (LIS)'도 있는데 그 문제 포스팅하기 전에 이거 먼저 해두면 좋을 거 같아서 먼저 포스팅한다. 우선 기본적으로 나오는 점화식은 cache[i] = cache[i - 1] + arr[i]; 다음과 같다. 하지만, 무작정 더하면 최댓값을 도출하지 못한다..