Doby's Lab

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음 문제를 봤을 때는 행과 열이 둘 다 100,001인 bool 2차원 배열을 선언해서 두 노드가 주어지면 간선을 1로 바꿔주어서 각 행을 DFS를 돌리면 될 거라고 생각했다. 하지만, 이럴 경우 배열의 크기가 너무 커서 오류가 나게 된다. 여기서 알아냈던 게 vector의 2차원 동적 기능(?)이었다. 기존 1차원 vector배열에서 push_back을 이용하는 것은 늘 사용했지만 2차원에서 사용할 방법은 생각도 못 해봤다. 각 행에 push가 가능하다는 ..

https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이번 문제는 수학 카테고리에 넣고 싶었으나 그래도 문제의 베이스는 이분 탐색이라서 이 카테고리에 넣어둔다. 점프를 최대로 하려면 1칸 점프를 한 뒤, +1 점프, +1 점프로 목적지에 도달해야 최댓값이 도출될 수 있다. 하지만, 100칸이 있을 때는 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14까지 더하면 100이 넘는다. 그래서 이럴 경우에는 13번째 점프를 할 때, 100을 채우게끔 22칸을 뛰어주면 된다. 즉, 코드로 구현을 할 때는 val..

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 단순한 백트래킹 문제인 줄 알았으나 꽤 조건이 까다로운 문제다. 허나, 이 조건은 예전에 N과 M 시리즈를 풀 때도 한 번 크게 겪었던 똑같은 유형이었다. (N과 M (9) 문제: https://www.acmicpc.net/problem/15663) (N과 M (9) 포스팅: https://draw-code-boy.tistory.com/29) 이 문제에서 필요한 건 정렬과 이전 노드(같은 d..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이분 탐색이라는 문제를 알고서 풀었기 때문에 어느 타이밍에 이분 탐색이 나와야 할지 감을 잡지 못했다. 첫 번째로 떠오른 방법은 1) 입력을 받을 때, 종유석과 석순으로 나누어서 석순이면 밑에서부터 장애물이 하나씩 추가되는 것이기 때문에 1 ~ 입력값까지 +1을 해주고, 종유석이면 위에서부터 밑으로 +1을 해주었다. 2) 각 구간 별로 부숴야 할 장애물들이 저장되어있기 때문에 정렬을 하고, 맨 앞에 ..

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..