Hanbit the Developer

https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어 www.acmicpc.net > 접근 심판들의 거리가 '특정 값' 이상일 때 배치해야한다고 강제하고, 이 특정 값을 이분탐색으로 찾는다. 이분탐색의 범위를 0~N으로 두고, 이 범위 내에서 적절한 값을 찾아내야한다. 이를 위해선, start = mid + 1 또는 end = mid - 1를 언제 수행해야할지를 결정해야한다. 조금 추상적으로 생각해보면, mid값(=특정 값)이 너무 클 경우에는 심판을 ..

https://www.acmicpc.net/problem/6597 6597번: 트리 복구 창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다. 아래는 www.acmicpc.net > 접근 위 사진에서 preorder의 첫번째 문자열인 D를 통해, inorder에서 D가 루트 노드이며, ABC, EFG가 각각 left, right라는 것을 알 수 있다. 다음에는 두번째 문자열인 B로, ABC에서 B가 루트라는 것을 알 수 있다. 이러한 로직이 구조적으로 반복될 수 있다. 이를 기반으로 간단한 재귀 함수 하나를 짜면 다음과 같이 나온다. void f(int start, int end)..

https://www.acmicpc.net/problem/2487 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net > 접근 1, 3, 5를 보면, 1 - 3 - 5를 계속해서 반복한다. 2는 계속해서 2이며, 4, 6은 4 - 6을 반복한다. 이 사이클을 나열해보면 1, 2, 3이며, 이것은 6이라는 궤적으로 이어지는데 이 때 최소공배수(Least common multiple)가 쓰이는 것을 알 수 있다. 그럼 저 사이클의 길이만 세주면 된다. 사이클의 길이는 입력값(3, 2, 5, 6, 1, 4)..

https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net > 접근 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다. 위 서술은 신장트리를 명시해주고 있다. 따라서 그래프를 탐색할 때 이전에 방문한 노드를 저장하고, 탐색 시 이전 노드를 블락해줌으로써 트리 탐색을 진행할 수 있다. 이제, 입력값을 트리라고 생각해보자. 초기에 f(1)을 넣으면 결과값이 나오는 방향으로 재귀함수를 구성한다. f(1)에서 해야하는..

https://www.acmicpc.net/problem/14942 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net > 접근 각 노드에서 1까지 얼마나 걸리는지를 일일히 측정하면 N이 100000이므로 TLE에 걸린다. 따라서 '희소테이블'을 통해 1까지의 빠른 접근을 구현한다. > 풀이 우선 그래프를 마치 '무빙워크'처럼, 1로 향하게 되는 방향그래프로 만들어준다. 이를 위해서 1에서부터 시작하는 BFS를 한번 해준다. 이 때 이동 경로는 '무빙워크'의 반대방향일 것이다. 따라서 지나오면서 이용한..

https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net > 접근 아래와 같이 시간을 계속해서 누적시키면서 가장 시간이 적은 것들을 replace하는 방식으로 고민해보았다. 이 때 카운터에서 최소값을 계속해서 찾아야하므로 우선순위큐를 써야한다. 시간 중요하므로 time, id, index 순으로 tuple을 배치한다. 나는 입력값을 받으면서 같이 처리하는 식으로 설계하였는데, 방식은 대강 다음과 같다. toInsert라는..

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net > 풀이 가장 최근의 파이프가 끝나는 지점과 방향을 기준으로 다음 탐색을 진행하는 DFS를 기반으로 코드를 작성하면 된다. 다만, 시간초과를 고려하여 DP를 이용한다. 짠 코드는 top-bottom 형식이며, DP는 다음과 같이 구성된다. DP[x][y][dir] 즉, DFS 함수의 파라메터를 그대로 사용한 것이다. #include #define ROW 0 #define ..

https://www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 이 글은 Segment Tree의 Lazy Propagation을 배경으로 작성하였다. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-2 [Python] Laz..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net > 풀이 문제에 나와있는 설명을 그대로 구현하면 된다. 단, 주의할 점이 있는데, 얼음을 1씩 줄이는 작업을 할 때, 줄이는 조건을 체크하는 로직과 얼음을 줄이는 로직이 서로 영향을 주면 안 된다. 얼음이 '동시에' 녹아야 하기 때문이다. 나는 이것을 위해 toDecrease라는 좌표를 담는 vector에 줄이게 될 좌표들을 담은 뒤에 따로 처리하였다. #include usin..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net > 풀이 큰 틀은 최대 6개까지 있는 연산을 브루트포스 돌려서 최소값을 얻어오는 식이다. 예를 들어 연산이 3개가 있다고 하면, 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1와 같은 시퀸스의 모든 집합에 대해서 연산을 수행한다. 그 다음으로는 '배열 돌리기'를 구현만 하면 된다. 단, 백트래킹을 이용하므로 반시계방향 회전도 구현해야..