Beakjoon Online Judge

꽤 오래 생각하다가 답을 봤는데, 한 줄 읽고 뭔지 알겠는...그런 아쉬운 문제였다.이 문제를 푸는 핵심은 다익스트라를 돌리되 DIST를 아래와 같이 2차원 배열로 관리해주는 것이다.DIST\[k]\[n]: k개의 도로를 지워서 n번 정점에 도착할 때의 최소거리이후에

고민 끝에 재귀 알고리즘을 떠올렸고, 결과적으로는 맞았는데, 뭔가 테스트케이스에 이상이 있는 듯해서 질문을 올려놓았다.각설하고, 이 문제를 푸는 제대로 된 알고리즘은 아래와 같다.임의의 정점을 x에서 가장 멀리 떨어진 점 y를 찾는다.y에서 가장 멀리 떨어진 점 z를

Prim이던 Kruskal이건 최소 스패닝 트리를 구해주면 된다.난 Prim으로 풀었는데 방문 여부 체크를 하는 것을 잊어서 1회 WA를 맞았다.Kruskal 쓸걸..

DP로 풀어야 한다는 강박에서만 벗어나오면 금방 풀 수 있다.작은 가방부터 채워나간다고 생각해보자.지금 보고 있는 가방에 들어갈 수 있는 보석들의 후보를 찾은 뒤 이 중 가장 비싼 보석을 채워주면 된다.어차피 다음에 볼 가방에는 지금 후보들이 다 들어갈 수 있으므로 g

무난하게 구간 쿼리(segment tree or fenwick)을 통해 풀 수 있는 문제이다.i번 나무를 심는 단계에 이르렀다고 생각해보자.결국 절대값의 성질로 부터 i번 나무보다 앞에 위치하는 나무들에 대해서 그 거리의 합은 아래와 같다.i번 나무보다 앞에 위치하는

각 노드가 구간내에 눌린 횟수가 짝수번인 스위치의 수, 홀수번인 스위치의 수를 표현하도록하는 lazy propagation + segment tree로 풀 수 있다.별 다른 주의점은 없는데, 개인적으로 스스로에게 맘에 들었던 점은lazy를 어떻게 구간에 잘 전파할까(l

간단한 DP문제이다.비록 입력 만드는 프로그램 잘못짜서 시간을 날리긴 했지만...cache\[i]\[j]\[k]\[l]: board\[i]\[j]에 도착하는데, k번 이하의 오락실만 사용하고, 총 l개 오락실을 거치는 경우의 수점화식은 생략한다.

Treap을 쓸 수도 있을 것 같고, 뭐 여러가지 방법이 있을 수 있을 것 같은데 연습다마 겸 segment tree로 풀었다.segment tree의 최상위 루트가 0~65536의 범위를 표현하게 하고(구현 시 1 ~ 65537로 바꿔야되긴 하지만..), 각 노드는

개인적으로 보기에는 화성지도와 유사한 문제인데, 특정한 축(나는 x축을 선택했음)을 기준으로 sweeping하면서 다른 축에 대한 구간 쿼리(나는 y축)를 진행하는 방식으로 문제를 풀 수 있다.구현 자체로는 크게 어려운 점이 없지만, 알고리즘이 꽤 여러 단계의 사고를

일단 플로이드-워셜을 수행한다.DISTsrc == W(src, x) + DISTx가 만족한다면, src에서 dst로 이동할 때 가장 먼저 x부터 방문해야 한다는 이야기이다.

Bellman-Ford로 풀면 무난하게 AC를 받는 문제이다.단, 늘상 음수사이클 문제가 그러하듯이 사이클이 있을 때 뭘 출력할지를 잘 결정해주어여 한다.이 문제 같은 경우는 (1)사이클이 있고, (2)사이클을 시작점에서 갈 수 있으며, (3)사이클에서 도착점에 갈 수

대충보면 아주 간단한 DP로 풀 수 있는 최적화 문제이나, 조금 찬찬히 뜯어보면 점화식을 세우기가 조금 까다롭다.기본적으로 로봇이동이 좌/우/하 세 방향으로 가능하기 때문에 현재 문제에 미래의 문제가 의존하고, 미래의 문제가 현재의 문제에 의존한다.문제를 조금 더 유심

sweeping 문제인데, 하필 직전에 화성지도를 푼 나머지 자칫하면 segment tree를 쓸 뻔했다.안 써도 각 정점의 opening / closing을 함께 저장하고 opening count를 세는 것 만으로도 쉽게 풀 수 있다.

맛 i를 갖는 사탕의 수를 taste\[i]로 해서 taste 배열을 관리하고, 이에 대해서 각 노드가 담당 구간의 원소 수를 저장하는 segment tree를 만든 뒤 k번째 값을 찾는 쿼리를 만들어서 해결할 수 있는 문제이다.하지만, Treap을 연습할 겸 map

결과적으로 단 1개의 segment tree를 사용하여 풀 수 있는 문제이지만, (1)입력을 잘못 이해해서, (2)알고리즘을 잘 떠올리지 못해서 꽤나 고전했다.(1)의 경우는 별건 아니고, 입력이 1등 ~ N등을 한 학생의 번호로 주어지는 것을 주의해주면 된다.나의 경

처음에 떠올린 솔루션은 재귀, 이내 중복으로 계산하는 경우가 많은 것을 떠올리고 DP로 전환하였다.점화식 설계는 아래와 같다.T(root, is_ea): root번 정점을 루트로하는 서브트리에서, root번 정점이 얼리어답터인지의 여부가 is_ea일 때, 필요한 얼리어

전체 길이 - LIS 길이가 곧 답이 되는 문제이다.제대로 이해하지 못한 것 같아서 죄책감에 LIS는 O(nlgn)으로 풀어줬다.그대도 대략의 풀이 와꾸를 정리해보자면 다음과 같다.애들이 엄청 띄엄띄엄 서 있다고 가정을 하고, 이 중에서 그냥 제자리에 가만히 있어도 되

별거 없다고 생각하고 잡은 문제치고 꽤나 고전했다.일단 sweeping + segment tree를 사용해서 풀 수 있는 문제인데, segment tree 부분이 일반적으로 널리 퍼져있는 lazy propagation 구현 형태로는 커버하기 어려운 부분이 있다.swee

정점을 분리하는 min-cost-max-flow 문제이다.만약에, v에 도착하기 전에 같은 지점을 지나면 안된다는 조건이 없었다면(즉, 같은 간선만 안지나면 된다면), 풀이는 아래와 같이 매우 간단했을 것 이다.모든 간선에 용량 1을 준다.가상의 source를 만들고

뭐가 되었든 최단 거리 알고리즘을 쓰면 무난하게 풀린다(난 SPFA로 풀었음).단, 정점에 비용이 있어서 아주 조금(?) 귀찮은데, w(u, v) == v에 있는 도둑루피로 설정해주고 최단거리를 찾은 뒤, 시작점의 도둑루피 수를 더한 것을 답으로 출력하면 된다.

segment tree를 활용한 sweeping으로 쉽게 풀 수 있다.물론 좌표 압축은 해주어야 한다.압축된 y축을 index로하는 segment tree를 x축을 훑으면서 구축해나간다.이번에 보는 정점보다 y좌표가 북쪽에 위치하는 정점들의 수를 segment tree

기본적으로 분할 정복의 아이디어를 사용하며, segment tree를 보조 도구로 사용해주면 된다.\[lo, hi] 구간의 막대들에 대해서 막대\[m] (lo <= m <= hi)이 가장 낮은 높이를 가졌다고 해보자.이 때, \[lo, hi] 구간의 최대 직

segment tree를 사용하는 inversion counting 문제로 reduction될 수 있다.주어진 0행이 m\[i-2] m\[i-1] m\[i] m\[i+1] m\[i+2] ...와 같았다고 하자.주어진 1행에서 각 m\[i]에 대응되는 지점들을 d\[i]

트리-like한 그래프가 주어질 때, 사이클에 포함된 노드의 수를 세는 문제로 볼 수 있다.DFS를 진행할 때, 노드 X를 방문하고 노드 Y를 방문하려는데 이미 Y가 방문된 상태라고 해보자.만약, 노드 Y가 아직 DFS가 완료되지 않은 지점이라면 노드 Y~X사이의 모든

lazy propagation을 사용하는 segment tree 문제이다.사실 알고리즘이 어렵다기 보다는 구현하다가 재귀의 늪에 빠지는 경우가 더 많다.또 헤매이는 경우를 방지하기 위해 몇 가지 메모를 남긴다면,생각보다 훨씬 더 게으르게 하자update할 때는 prop

전형적인 min-cost-max-flow 문제이다.source에서 person_i로 간선을 연결하는데, (source, person_i)의 capacity는 person_i가 구매를 희망하는 수량이다.bookstore_j에서 sink로 간선을 연결하는데, (bookst

전형적인 min-cost-max-flow 문제이다.source에서 employee_i로 간선을 연결하는데, (source, employee_i)의capacity는 1cost는 0work_j에서 sink로 간선을 연결하는데, (work_j, sink)의capacity는

전형적인 min-cost-max-flow 문제이다.단, 최대 비용을 구해야하므로, 비용만 음수로 처리한 후 출력시 절댓값으로 출력했다.source에서 employee_i로 간선을 연결하는데, (source, employee_i)의capacity는 1cost는 0work

F\_(n), F\_(n-1)을 F\_(n-1), F\_(n_2)로 표현하는 행렬을 구하고,행렬의 거듭제곱을 분할정복으로 구해준다.

별 탈 없이 lazy propagation을 사용하는 segment tree를 사용해서 풀 수 있는 문제다.개인적으로는 화성탐사가 훨씬 어려운데 왜 똑같이 플레3인지 모르겠다.어찌되었건...구간합을 구하는 lazt propagation과 다른 점은 xor을 사용하므로서

그야말로 닉값한다라는 표현이 걸맞을 정도로 매우까다로운 문제였다.우선, 좌표압축은 당연히 해야하므로 이후 기술에서 좌표는 이미 압축되어 있다고 가정하도록 하겠다.(사실 여기서도 깨달음이 있었는데, 단순하게 map을 쓰는 좌표압축은 매우 속도가 느리다는 점을 배웠다)기본

아주 straight-forward하게 KMP를 묻는 문제인데, 역시나 난관은 KMP를 잘 기억하고 있냐는 것이다.연습이 왕도겠지만, 팁을 적어놓자면 아래와 같다.일단 table이 있다고 가정하고 haystack/needle을 찾는 코드를 짠다.table을 구하는 방법

17070이랑 동일한 문제이다.내공냠냠

간단한 DP문제이다.문제를 잘 읽어보면 결국 이 게임 진행 중에 파이프의 가능한 모양은 -, |, \\, 총 3가지가 전부이다.(반대 방향 대각선 나올 수 없음)따라서, 아래와 같이 cache를 설정하고 점화식을 세워서 풀어주면 된다.cache\[i]\[j]\[k]:

Brute-force로 풀어줄 수 있는데, 사실 계산 복잡도 상으로는 안풀릴 사이즈이지만 엄청나게 많이 프루닝이 된다.S\[i]\[i]를 보면 A\[i]의 부호를 알 수 있으므로 매 단계마다 부호에 따라서 A\[i]를 골라보고 S에 위배되지 않는지 확인한다.위배된다면,

문제를 보자마자 풀이는 바로 떠오른다.아래와 같이 재귀 함수를 떠올리면 풀이가 끝난다.Solve(current_level, current_r, current_g, current_b): 현재 current_level을 색칠해야하고, 남아있는 색이 current\_{r|g

처음에는 DP로 풀었고, 다른 풀이가 또 있나를 찾아보다가 투 포인터 풀이로도 풀어보았다(둘 다 무난하게 AC는 받는다).DP풀이 같은 경우에는 아래와 같이 캐시/점화식을 정의하였다.CACHE\[i]\[s]: i번째 수까지 사용해서 s를 만들 수 있는 경우의 수CACH

\[1 ~ N \* N] 범위의 자연수가 있다고 할 때 주어진 행렬에서 나보다 작거나 같은 수의 갯수가 K개인 수를 찾는 문제로 접근해준다.찾아진 수가 행렬에 존재하지 않는 수일 수 있으므로 탐색은 lower_bound로 진행해준다.행렬에 존재하는 수를 기준으로 나보다

DP 솔루션의 점화식을 발견하기 직전까지 갔지만, 근처에서 배회하다가 결국에는 답을 보고 풀었다.캐시는 아래와 같이 정의한다.CACHE\[bldg]\[left]\[right]: \[bldg, N] 높이를 갖는 빌딩들을 왼편에서 left개가 보이고 오른편에서 right개

inversion counting 문제인가? 고민하며 시간을 날렸는데, 결과적으로는 inversion counting 문제가 아니다.버블 소트의 i에 의해서 돌아가는 한번의 루프를 1회전이라고 불러보자.각 회전에서 각 원소들은 주변 숫자와의 대소 관계에 따라 오른쪽으로

예제 3번에 대해서 M개 놀이기구가 사람을 태울 수 있는 시간을 테이블로 표현해보자.1번 놀이기구: 0 1 2 3 4 5 ...2번 놀이기구: 0 2 4 6 8 10 ...3번 놀이기구: 0 3 6 9 12 15 ...4번 놀이기구: 0 4 8 12

N 이상의 소수 테이블을 에라토스테네스의 체를 사용해서 구해놓고, 투 포인터를 진행하여 합을 만족하는 경우의 수를 헤아린다.

가운데 값까지를 저장하고 있는 max heap과 그 이후의 값을 저장하고 있는 min heap을 사용해서 풀어주면 된다.

간단한 라인스위핑 문제이다.모든 선분을 opening / closing 두 개의 점으로 나누어 저장한 뒤 정렬하고, 스위핑을 진행한다.누적된 opening의 수가 최대가 되는 지점을 찾으면 된다.단, 이때 끝점 겹침 조건을 만족시켜주기 위해서 동일 위치에 대해서는 닫히

결국 이분 그래프라 함은 모든 정점 X에 대하여 모든 인접 정점 Y들이 서로 다른 집합에 들어갈 수 있음이 보장되어야 하는 것을 의미한다.잘 생각해보면 2색을 가지고 인접한 노드끼리는 다른 색을 가지도록 그래프를 색칠하는 것과 동일하다.DFS를 진행하면서 색을 칠하는데

풀이를 잘 떠올리지 못해서 답을 보고 풀었다.답을 본 직후에도 "무슨 소리지?" 고민했던 것을 보면 오히려 빨리 답을 본 것이 다행인가 싶다.이 문제는 DP로 접근해서 풀 수 있는데, DP 풀이를 기술하기에 앞서서 아래의 lemma 하나를 짚고 넘어가도록 하자.주어진

큰 특이 사항이 없는 라인 스위핑 문제이다.각 건물의 좌우 경계를 opening / closing edge로 나누어 저장하고 x 방향으로 스위핑한다.조금 까다로운 점은 각 위치에서 가장 높은 edge를 구하기 위한 자료구조를 선정하는 것이 있다.나의 경우는 <높이

Recursive DP로 풀 수 있는 문제였다.머릿속에 DP 풀이는 떠오르는데, Iterative DP로 풀기에는 순서를 지정하기 애매할 때 Recursive DP를 고려하는 습관을 들이도록 하자.CACHE 정의는 아래와 같이 했다.CACHE\[i]\[j]: i행 j열

'한번에 얼마까지 보내볼 수 있겠어?'는 어려운 질문이지만, '한 번에 X만큼 보낼 수 있어?'는 쉬운 질문이다.X 미만의 용량을 갖는 간선을 지워주고 출발지에서 목적지까지 도달 가능한지 BFS(또는 DFS)를 돌려주면 된다.X의 범위는 1 ~ 1억까지이고 보낼 수 있

완전순열(교란 순열이라고도 불리는...) 문제이다.결론부터 이야기하면 N개 원소에 대한 완전순열의 수 점화식은 아래와 같다.CACHE\[N] = (N - 1) \* (CACHE\[N-1] + CACHE\[N - 2])점화식 유도는 아래와 같다.수열이 아래와 같이 주어졌

언뜻보면 DP문제지만, 실상은 1939번 중량제한과 매우 비슷한 이분탐색 문제이다."최대값 최소값 차이가 최소가 되는 경우를 구해봐"는 어렵지만 "최대값 최소값 차이를 X가 되게 할 수 있어?"는 쉽다.X를 찾는 과정을 upper bound 찾기로 진행해주면 된다.X가

일단 문제를 보고 2시간 동안 별다른 아이디어가 떠오르지 않아서 답을 보고 풀었다.답을 보고 풀어낸 것은 차치하더라도 코너 케이스를 찾는 것에 계속 실패해서 꽤나 고전했다.문제를 풀기 위한 캐시의 정의는 아래와 같다.CACHE\[k]\[i]\[j]: k번 열까지 A\[

조금 헤메이기는 했는데, 그래도 결과적으로는 잘 풀어냈다.DP로 접근하여 풀 수 있는 문제로 우선 아래와 같이 CACHE를 정의해준다.CACHE\[t]\[k]: t 이하의 수들만을 사용하여 원소의 수가 k개인 집합을 만드는 경우의 수주어진 수열에 존재하는 t의 수를 C

그냥 곧이 곧대로 풀어주면 된다.flood fill로 각 대륙을 찾아주고, 각 대륙 별로 해당 대륙에 속하는 좌표들을 잘 저장해둔다.존재할 수 있는 모든 대룩 쌍에 대해서 최단거리를 구해본다.이 때, 대륙 A, B 사이의 최단 거리는 A에 속하는 좌표 ~ B에 속하는

답을 보지 않고 풀어냈는데, 풀고나서 답을 찾아보니 내가 푼 방법보다 훨씬 깔끔한 방법이 있었다.물론, 두 가지 방법 모두 시간 복잡도 측면에서 큰 차이는 없다.훨씬 깔끔한 방법이 내 풀이를 어느정도 포괄하는 측면이 있기에 훨씬 깔끔한 방법을 기준으로 설명하고, 내 풀

아주 아주 기본적인 기하 문제이다.다각형을 이루는 각 정점을 P\[0], P\[1], ..., P\[N-1]이라고하면 이 다각형의 면적은 아래와 같다.S = 0.5 \* ABS(P\[0]->P\[1] X O->P\[0] + P\[1]->P\[2] X O->P\[1] .

모든 학생보다 무조건 작은 가상의 0번 학생이 있다고 생각하자.입력을 그래프로 표현하였을 때, 이러한 0번 학생은 다른 모든 학생들의 predecessor가 될 것이다.0번 학생을 시작정점으로 위상정렬해준다.

피보나치 수열의 점화식을 행렬로 표현하면 아래와 같다.\[\[1, 1], \[1, 0]] ^ n \* \[F1, F0] = \[Fn+1, Fn]\[\[1, 1], \[1, 0]] ^ n을 분할정복으로 구해주면 풀 수 있다.

만만하게 봤다가 은근히 고전했다.일단 문제를 푸는 큰 틀은 아래와 같다.people\[1] ~ people\[n]까지의 사람들이 줄을 서 있을 때, 서로 볼 수 있는 쌍의 수를 알고 있다고하자.people\[n+1]이 새로 추가될 때 새로 생겨나는 쌍의 수를 구하여 더

하루가 지날 때마다 빙판을 녹여주고, 한 백조에서 BFS를 수행해서 다른 백조로 가는 경로가 있는가를 살펴주면 된다.단, 매번 빙판을 녹일 때마다 BFS를 새로 수행한다면 비효율적이므로 BFS 수행 시 빙판이라서 진행하지 못했던 정점들을 별도로 저장해두고, 다음 BFS

일단 문제 해설에 앞서서 중요한 사실을 미리 밝히면, 이 문제의 답 범위는 64bit integer를 아득히 초과한다.답을 계산하기 위한 BigInteger 클래스는 미리 만들어야 함에 주의하자.아래 설명에서는 BigInteger는 이미 구현했다고 가정하고, 코어가 되

은근히 고민을 많이하게 만든 문제였는데, 답은 의외로 간단한 DP로 풀어줄 수 있다.문제를 곰곰히 생각해보면, 서로 다른 키를 갖는 N명이 있을 때 이들을 지그재그 형태로 배치하는 경우의 수를 헤아리는 것과 같다.이러한 지그재그 배치는 아래와 같이 두 종류가 있을 수

별거 없이 Trie를 잘 써서 풀어주면 된다.

문제 자체는 크게 어렵지 않지만 좌표계가 6각형인 관계로 꽤나 애를 먹었다.우상향하는 방향을 하나의 행으로 잡고, 총 29x29 크기의 배열로 생각하고 풀어주면 된다.DP를 위한 캐시정의는 아래와 같다.CACHE\[turn]\[row]\[col]: turn번의 이동에

BFS 아이디어를 잘 응용하면 쉽게 풀어 줄 수 있다.BFS의 장점은 간선에 가중치가 없는 그래프라면 곧 방문순서가 경로의 길이가 된다는 점이다.다시 말하면, 간선에 가중치가 없으므로 BFS 순서에 따라 정점을 방문하다가 최초로 목적지 정점을 탐색하게 되는 순간이 곧

평이한 구현문제로 백트래킹을 잘 써주면 된다.구현이 빡세보이면 일찌감치 OOP를 도입하자는 교훈을 얻었다.

DP의 고전 of 고전 카탈란 수 문제이다.별다른 풀이는 없지만, 기억 열화를 막고자 점화식을 떠올리는 방법을 아래와 같이 적어 놓는다.편의상 N이 6이었다고 할 때, 아래 경우의 수를 헤아리면 중복/빠짐 없이 모든 경우를 헤아리게 된다.( ) \_ \_ \_ \_(

(1)DP로 풀어야 한다는 것, (2)CACHE 정의를 어떻게 세워야 한다는 것, (3)점화식을 어떻게 세워줘야 한다는 것 모두를 어렵지 않게 떠올릴 수 있었다.하지만, Iterative bottom-up DP를 고집하는 바람에 시간초과를 2번이나 맞았다.때때로, It

초반에 DP 문제겠거니 생각해보다가 DP 문제가 아님을 깨닫는데까지 시간이 조금 걸렸다.결과적으로 문제는 스위핑의 아이디어를 활용해서 풀었다.주어진 입력을 통해 풀이를 살펴보면 아래와 같다.1 2 3 1 2 입력에 대해 아래와 같이 PSUM을 함께 구해서 테이블로 표현

간단한 DP를 2번 돌려서 풀 수 있는 문제이다.INCR\[i]: NUMBER\[i]에서 끝나는 최장 부분 증가 수열DECR\[i]: NUMBER\[i]에서 시작하는 최장 부분 감소 수열자명하게 답은 max(INCR\[i] + DECR\[i] - 1)이 된다.

매우 간단한 DP 문제이나, 테스트케이스 수가 주어지지 않아 "이게 정말 TLE 안나고 풀릴까?"를 고민하게 만드는 문제이다.간단한 DP로 풀어주면 TLE 안나고 정답이 나온다.CACHE 정의는 아래와 같이 한다.CACHE\[i]\[j]: 파일 i ~ j를 합칠 때 최

입력의 크기가 매우 작아서 단순한 알고리즘으로도 풀린다.우선, 입력에 별도로 부모 자식 관계가 주어지지는 않으므로 입력을 그래프로 간주하여 받은 뒤 루트를 1번 노드로하는 BFS 트리를 생성해준다.이 때 각 노드의 깊이를 함께 구해주도록 하자.만약, a와 b의 LCA를

그닥 어려운 문제는 아니었지만, 여러 개념들을 복기해내야해서 나름대로 애를 먹었다.배울게 많아 좋은 문제라는 생각이 들어 조금은 공을 들여 기록을 남겨본다.참고로, 이 문제는 Euler's phi 함수를 사용하면 매우 쉽게 풀 수 있다.다만, 함수를 사용해서 풀다보면

외적의 부호를 사용해주자

문제가 영어인 관계로 굳이 다시 한 번 문제를 적어본다.이 문제는 임의의 수열이 N개 입력될 때, 각 수열을 Binary Tree로 구성한다면, 트리의 모양이 몇 가지가 나올 수 있는지를 묻는 문제이다.Full binary tree를 생각한다면, 우리는 각 노드의 위치

마치 입력이 그리드인 것 처럼 주어져서 조금 혼란스러웠으나, 고려할 가치가 있는 정점이 어디인가에 집중하면 쉽게 풀어줄 수 있다.아래와 같은 노테이션을 활용하도록하자.(Xs, Ys): 시작점(Xe, Ye): 도착점(X11, Y11): 1번 텔레포트 중 한 쪽 입구(X1

문제를 보고 2-30분 가량 감을 못 잡아서 문제 분류를 보았다.문제 분류는 다이나믹 프로그래밍으로 되어 있는데, 더욱이 감을 잡기가 어려워서...결국엔 답을 보았다.결론적으로는 재귀를 활용하는 Top-down DP 문제였는데, 골3인데도 헤매인 것 보면 이 부분에 대

딱봐도 내가 잘하지 못하는 유형(DP + 백트래킹)의 문제임을 알 수 있어서 순간 쫄았었다.하지만, 마침 14238번 출근 기록 문제를 푼 직후라서 그런지 나름대로 빠른 시간 내에 풀 수 있었다.출근 기록 문제에서와 유사하게(사실 그렇게 비슷하지는 않지만) Top do

Top-down DP 문제로, 역시나 내가 가장 취약한 부분답게 꽤 고전했다.Top-down DP 풀이를 바로 기술하는 것은 취약점 개선에 아무런 도움이 되지 않으므로, 최종 답안까지 가는 아이디어를 하나하나 차근차근 기술해보도록 하겠다.문제를 잘 관찰해보면 아래와 같

13392번 문제인 방법을 출력하지 않는 숫자 맞추기 문제에 백트래킹만 추가해주면 되는 문제이다.상세한 풀이는 13392번 문제의 풀이를 참고하도록 하자.그래도, 아무것도 안 적어놓기는 멋쩍으니 아래와 같이 풀이를 적어 놓는다.Top-down DP를 활용하면 되고, 아

입력의 크기가 작으므로 간단한 백트래킹을 통해 풀어줄 수 있다.row major order로 각 위치에 대해서 배치할 수 있는 경우의 수를 한 번씩 시도해주면 된다.한 편, 가로로 연결한 칸을 1로, 세로로 연결한 칸을 0으로하여 비트마스킹으로도 풀어줄 수 있는데, 입

구슬들의 위치가 동일한 경우를 2번 탐색하는 것은 바보 같은 짓 이다. 따라서, 구슬들의 위치를 status로 하여 BFS를 수행해주면 되는 문제로 아이디어 자체는 매우 간단하다. 구현이 짜증나는데, 구현이 귀찮을 것이 예상되는 경우(빡구현...) 미리미리 OOP를

DFS를 활용해서 그래프에서 사이클에 포함된 정점들을 검출한 뒤 해당 정점의 dist를 0로 초기화하여 Dijkstra를 통해 풀어주었다.무방향 그래프에서 DFS를 통한 사이클 검출에 은근히 애를 먹었는데, 인점한 정점이 부모 였을 경우는 사이클로 치치 않아야 하는 것

처음에 DP + Floyd로 해결할 수 있을 것이라고 착각했다가 꽤 오랜 시간을 허비했다.문제를 잘못 이해했을 뿐 나름 나쁘지 않은 접근이었기 때문에, 제대로 된 풀이를 기술한 뒤에 DP + Floyd 풀이와, 왜 안되는지를 적어보고자 한다.제대로 된 풀이를 기술하면,

그림을 그려보면 어렵지 않게 풀 수 있다.임의의 체스판이 주어졌을 때 각 원소가 몇 번씩 더해지는지를 그림으로 표현해보면 아래와 같다.황색 영역 : 1번 더해짐청색 영역 : 2번 더해짐적색 영역 : 3번 더해짐아무런 변경을 하지 않은 상태에서 B의 합을 B_init이라

크게 어렵지 않게 풀었는데, 풀이까지 이르게 된 사고의 흐름이 나름 기억해둘만해서 조금은 자세히 기록한다.아래는 풀이와는 무관한 사고의 흐름이다.처음에 문제를 보고 1차원 DP로 풀 수 있겠거니 생각했다(CACHE\[i]: i에 도착하는 데 걸리는 최소 시간과 같이).

요약하면 뒤 부터 풀었고, 스택을 활용해서 풀었다.요상하게도(?) 데이터 구간에 대해 무언가를 쿼리할 때 서로 다른 키 값을 사용해야하는 경우에 스택, 스위핑, 구간트리를 활용하면 문제가 쉽게 풀리는 경향이 있다.이 문제는 골3따리 답게 스택정도를 활용해주면 쉽게 풀린

두 점 a, b를 양 끝으로하는 선분 l_ab와 c, d를 양 끝으로 하는 선분 l_cd가 교점을 갖는다와 동치는 아래와 같다.벡터 a->b와 벡터 a->c의 외적, 벡터 a->b와 벡터 a->d의 외적의 부호가 서로 다르다.벡터 c->d와 벡터 c->a의 외적, 벡터

덜 formal하지만, 보다 느낌오게 문제를 설명하면 아래와 같다.1~N번 집을 순서대로 원형으로 배치한 뒤, 색칠 할 때 이웃한 집끼리 다른 색으로 칠하는 최소 비용은?DP로 풀어줄 수 있는데, 첫 집 / 끝 집 처리가 은근히 귀찮다.우선, 첫 집 / 끝 집을 무시하

Bounded Knapsack 문제를 log-step DP를 통해 0-1 Knapsack으로 풀어주는 아이디어를 활용하면 된다.아래는 문제를 풀었던 사고의 흐름을 날 것 그대로 정리한 것이다.각 쿼리를 O(n)으로 곧이 곧대로 구해주면 당연히 TLE가 난다.따라서, D

비트마스킹과 포함배제를 함께 사용해주면 쉽게 풀 수 있다.문제를 요약하면 곧 주어지는 소수 배열의 배수들의 갯수를 구하는 것이다.i번째 소수의 배수 집합을 S_i과 같이 표현한다고 하면, 멱집합은 비트마스킹을 통해 표현해줄 수 있다.멱 집합 = n(1 <= n &

주어진 문제를 그래프로 표현하자.u -> v 간선은 건물 u가 건물 v보다 먼저 지어져야 함을 의미한다.w(u, v)는 건물 u의 건설 시간으로 하자.편의를 위해 아래를 가정하자.0번 건물이 존재한다고 하고,모든 건물들(1 ~ N번)은 0번 건물보다 나중에 지어져야 하

임의의 벡터 매칭에 대해서 그 벡터들의 합을 식으로 정리해보면 항상 아래의 모양이 될 것이다.편의상 점의 갯수가 20개였다고 가정했다.(p\[0] + p\[1] + ... + p\[9]) - (p\[10] + p\[11] + ... + p\[19])즉, N/2개의 더해

Problme link: https://www.acmicpc.net/problem/1509DP를 활용해서 쉽게 풀어줄 수 있다.정확히는 (1)임의의 부분문자열이 회문인지를 위한 DP, (2)특정 위치까지의 문자열의 파티션 수를 헤아리기 위한 DP, 이렇게 총

Problme link: https://www.acmicpc.net/problem/1562결론부터 기술하면, 각 숫자의 사용여부를 비트마스킹을 활용하여 나타내는 DP 문제이다.비트마스킹을 써야한다는 것도, CACHE 정의까지도 스스로 생각이 닿았는데 점화식을

Problem link: https://www.acmicpc.net/problem/1647Prim이든, Kruskal이든 적당히 자신있는 것을 골라 MST를 구한 뒤 가장 비싼 edge 하나를 지워주면 답이된다.엄밀하게 증명은...좀 어려운것 같다.

Problme link: https://www.acmicpc.net/problem/1799별 볼일 없는 Backtracking 문제지만, 무식하게 풀면 TLE가 나고, 주의 깊지 못하면 WA가 날 수 있다.시간복잡도는 아래 테크닉으로 줄인다.대각 체크 배열 활

Problme link: https://www.acmicpc.net/problem/1806같은 위치에서 출발하는 투 포인터를 써준다.

Problme link: https://www.acmicpc.net/problem/2098고전적인 문제이니만큼 DP를 잘 활용해서 풀어주면 무난하게 풀린다.단, 한 가지가 가물가물해서 조금 시간을 버렸는데 아래 사실을 유념하도록 하자.어느 도시에서 시작하는 순

Problme link: https://www.acmicpc.net/problem/2143각 배열의 모든 부분합들을 미리 구하여 저장해놓는다.이렇게 구해진 두 개의 부분합 배열을 각각 CAND_A, CAND_B라고 하자.두 부분합 배열을 정렬한 뒤에 서로 다른

Problme link: https://www.acmicpc.net/problem/2162문제가 어렵다기 보다는 자료구조를 여러개 써줘야한다.CCW를 활용한 선분 교차여부 판단을 위해서 벡터, 라인 자료구조를 사용하였고,그루핑을 위해 서로소 집합을 사용하였다.

Problem link: https://www.acmicpc.net/problem/2467노말한 투 포인터 문제로, 서로 반대 방향에서 출발하는 투 포인터 알고리즘을 사용해주자.

Problme link: https://www.acmicpc.net/problem/2239별 볼일 없는 백 트래킹 문제였다.포인트 냠냠

Problme link: https://www.acmicpc.net/problem/2342그닥 어렵지 않게 풀 수 있는 DP 문제이다.아래와 같이 CACHE를 정의하였다.CACHE\[i]\[l]\[r] = i번째 입력까지 밟고, 오른발이 r, 왼발이 l에 있을

Problem link: https://www.acmicpc.net/problem/2473정렬된 배열에서 서로 다른 3개의 원소 a, b, c를 뽑아 a + b + c = 0이 되도록하는 경우를 헤아리는 문제와 비슷하다.a <= b <= c가 되도록

Problme link: https://www.acmicpc.net/problem/2623간단한 위상정렬 문제로 볼 수 있다.각 가수를 그래프의 정점으로, 인접한 두 순서를 간선으로 표현한다면 입력은 그래프로 표현될 수 있다.그래프의 순서를 유지하는 위상정렬

Problme link: https://www.acmicpc.net/problem/2887문제를 보는 순간 바로 MST문제로 분류할 수 있었다.하지만, 입력이 사실상 fully connected graph이므로 Prim이건, Kruskal이건 바로는 사용하지

Problme link: https://www.acmicpc.net/problem/9252전형적인 DP문제이고, DP 완료 후 백트래킹 정도가 추가된 문제이다.아래와 같이 CACHE를 정의하자.CACHE\[i]\[j]: A\[0...i], B\[0...j]까지

Problem link: https://www.acmicpc.net/problem/9328빡 구현 문제이다.아래의 순서로 풀어주면 된다.더 이상 새로운 열쇠도 발견하지 못하고, 문서도 발견하지 못할 때까지 \- 있는 열쇠로 열 수 있는 모든 문을 열어버린다(

Problem link: https://www.acmicpc.net/problem/10775이진 트리(i.e. std::set)을 활용해서 풀어주었다.쉽게 풀고나서 혹시나 하는 마음에 문제 분류를 보니 Disjoint Set을 활용해서도 풀어줄 수 있는 모양이

Problme link: https://www.acmicpc.net/problem/10942문제 설명이 조금 부족한데, 숫자 하나를 문자 하나로 취급해야 한다.여튼 노말하게 DP를 써주면 풀리는 문제이다.아래와 같이 CACHE를 정의하자.CACHE\[s]\[e

Problme link: https://www.acmicpc.net/problem/11049그닥 어려울 것 없는 DP 문제로 쉽게 쉽게 풀어줄 수 있다.아래와 같이 CACHE를 정의하자.CACHE\[s]\[e]: Matrix\[s]부터 Matrix\[e]까지

Problme link: https://www.acmicpc.net/problem/12015사람마다 푸는 방법은 여러가지가 있을텐데, 나는 그중에 가장 무지성으로 풀 수 있는(물론 복잡도는 다른 알고리즘에 뒤지지 않는다) lower_bound 풀이를 사용했다.

Problme link: https://www.acmicpc.net/problem/12850Adjacent Matrix로 입력을 나타내고 이를 M이라고 하자.이때, M\[i]\[j]는 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다고 하자.이렇게하면,

Problme link: https://www.acmicpc.net/problem/12852포인트 냠냠을 위한 BFS 문제이다.숫자가 작아지면 작아지지 커질 수는 없다는 사실로부터 범위 내의 양수들만 접근하리라는 것을 알 수 있다.

Problme link: https://www.acmicpc.net/problem/14003별로 특별할 것 없이 lower_bound를 사용해서 풀어주면 LIS의 길이까지는 무리 없이 구해줄 수 있다.여기서 실제 LIS를 재구성해내는데 조금 어려움을 겪었는데,

Problme link: https://www.acmicpc.net/problem/14939행 단위로 각 행에 있는 전구를 누를지 말지 결정한다고 해보자.i번쨰 행의 j번째 열에 위치하는 전구를 고려할 때, 사실 얘를 누를지 말지는 i-1행 j열의 전구가 결정