Doby's Lab

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 이번 문제는 어떤 특이한 응용력 혹은 논리력이라기보다 수를 잘못 읽어서 발생한 문제에 대해 포스팅한다. 문제는 크게 어렵지 않다. BFS를 돌려서 기존 value에 2를 곱한 것과 value의 뒷자리에 1을 붙여주고, 큐를 돌려서 찾는 값(findValue)이 나오면 종료시켜서 얼마나 걸렸는지 출력하면 되는 문제다. 오류는 10^9를 10억이 아닌 1억으로 봐서 생긴 문제였다. 뒷자리에 1을 넣을 때 value에 10을 곱하고, 1을 더해주기 때문에 1억이 넘으면 안 되기 때문에 조건에 1천만을 안 넘는 value를 다음..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS 문제인 것을 떠나서 이건 monotonic stack으로 풀리지 않을까 싶어서 시도해봤지만 반례가 있었다. [monotonic stack 시도] #include #include #include using namespace std; int n; int arr[1001] = { 0, }; int cache[100..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아무 생각 없이 풀었다가 TLE가 나왔다. [첫 시도] 각 행에서 누적합을 temp에 저장해 두고 명령을 내리면 합을 구하게끔 했지만 이마저도 TLE가 나온다. >> TLE가 나온 이유는? 각 행의 누적합을 구해놓는다 한들 m이 가지는 최댓값이 100,000 표의 크기로 주어질 수 있는 최댓값이 1024로 1~1024행까지 구하는 명령이 100,000번 ..

https://www.acmicpc.net/problem/5073 5073번: 삼각형과 세 변 각 입력에 맞는 결과 (Equilateral, Isosceles, Scalene, Invalid) 를 출력하시오. www.acmicpc.net 평소에 많이 보던 문제인데 나중에 한 번 어려운 응용문제에서 나올 거 같은 느낌이 들어서 간단하게 정리해두려 한다. 이 문제의 포인트는 조건의 위치다. 한 번 if 필터링 거치고 나서 이번엔 무엇을 우선순위 조건으로 두고 조건식을 달아두어야 하는지 파악해야 하는 게 포인트다. #include using namespace std; int main() { int a, b, c; while (1) { cin >> a >> b >> c; if (!a && !b && !c) br..

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++), 점화식... '점화식을 어떻게 세울 것인가'가 큰 관건이었다. '큰 문제를 작은 문제로 나누자'라는 키워드는 이제 금방 떠오르고, 나눌 수 있었지만 ..