Doby's Lab

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]; 다음과 같다. 하지만, 무작정 더하면 최댓값을 도출하지 못한다..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 저번에는 안 풀리던 문제였는데 오랜만에 시도해보니 풀렸다. 저번 코드는 잘 기억나진 않지만 이번에 한 거보다 더 복잡했던 거 같은데 기억이 안 난다. 여러 가지 경우를 계속 생각했었던 거 같다. 기억나는 건 이런 경우? 하지만, 구현한 코드에서는 상관없다! 주사위를 굴렸을 때 나오는 모든 경우(1 ~ 6)를 다 따지기 때문이다! 이번 문제는 '응용력'..

[문자열 더하기] string strSum(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); while (a.length() > b.length()) { b += '0'; } while (a.length() < b.length()) { a += '0'; } int alone; int carry = 0; string result; for (int i = 0; i < a.length(); i++) { alone = ((a[i] - '0') + (b[i] - '0') + carry) % 10; result += to_string(alone); carry = ((a[i] - '0') + (b[i] - '0') + car..

https://www.acmicpc.net/problem/2139 2139번: 나는 너가 살아온 날을 알고 있다 우리는 일상생활에서 휴가 일수를 계산하는 것 처럼 두 날짜 사이의 기간을 계산해야 하는 경우가 많다. 이때, 계산을 하는 가장 간단한 방법은 적당한 날짜를 잡은 뒤 계산할 날짜가 될 때까지 www.acmicpc.net 문제 제목에 끌려서 들어갔다가 오랜만에 윤년 문제였다. 윤년이 무슨 소리인지는 알겠으나 문제를 또 보고 구현하려니 헷갈리고 그냥 윤년 조건은 통째로 외워버려야겠다. ((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0) [전체 코드] #include using namespace std; int month[13] = { 0, 31, 28, 31,..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이번 문제는 문자열을 통으로 받아서 수와 연산자들을 분리하고, 또 받은 수에 앞이 0이 붙어있을 경우 앞에 0을 제거해주는 작업을 한 뒤 그리디하게 괄호를 붙여주면(논리 작업) 풀리는 문제다. (구현 어려울까봐 미루던 문제) 우선 입력을 받고 문자열을 다음과 같은 포인트에서 수로 변환하는 작업을 거친다. 1. 연산자가 나올 때 2. 끝날 때 수를 받고서 예를 들어, "00085"인 경우 앞에..