google

#dp

bfs나 dfs로 관리해준다면 visited의 존재가 없기 때문에 8^50번의 탐색이 필요하다. 따라서 dp를 이용해 중복연산을 제거해보자.

dp[i][j] =  현재 i,j에 말이 있을 확률이라고 가정해보자.

그렇다면, 처음 위치 dp[x][y]는 1이 될 것이다. 매 이동횟수 k를 진행하면서 갈 수 있는 경우의수는 8가지 이기 때문에

dp[next_knight_move][] += dp[x][y] * 0.125될 것이다. 이 과정을 위치에 벗어나지 않는한 계속 해주자.

dp보단 브루트포스에 가깝다... 시간복잡도 O(n^4)

http://boj.kr/2056b85ab8084889bb78272196e1aa7e

#greedy

탑승 정거장 기준으로 정렬을 해보자.

#tsp #graph

대각선으로 BFS을 하여 adjust matrix를 만들 수 있다.

그런 다음, 접근을 못하는 정점이 있으면 불가능한 걸 알 수 있다.

그 다음 tsp를 활용 해 최단 거리를 구할 수 있다.

난이도에 비해 어렵게 풀었는데 n의 범위가 작아서 10!으로 permutation을 만들면 brute force으로도 풀리는 듯 하다.

http://boj.kr/de559f4525be4718827567bbee09fa6e

#dsu

평범한 dsu 문제

adjust matrix를 순회하면서 i,j가 1인 경우,  parent를 find 했을 때, parent가 다르다면 union을 해준 다음, +=1 해주면 된다. 

그것이 최소의 간선으로 전체를 순회할 수 있는 방법 중 하나이다.

http://boj.kr/12f580657a204a99b1f4254ba858d488

#sort, #hash

정렬한 다음,  dictonary와 같은 hash set으로 처음 등장한 index를 관리해주면 된다.

풀고 난 다음 태그를 봤는데 이분탐색이 있어 이방법도 있겠구나 싶었다.

#greedy #prefix_sum

관찰 해보았을 때, 우체국은 사람이 있는 장소에 설치하는게 가장 최적일 것이다.

그리고 Greedy하게 푸는 방법을 생각해보았을 때 현재 index기준 사람이 전체 사람의 50%가 넘어가는 시점에 설치해야 한다. (이 과정이 증명하기 힘들지만, 가장 최적의 방법이다.) 이 과정을 누적합을 이용해서 구현해주자.

추가로 input으로 들어오는 우체국의 위치가 정렬이 되어 있지 않은듯하다. sort를 해주어야 함.

이 방법외에도 여러가지 풀이방법이 존재하는 듯하다.

http://boj.kr/78fd261e3b61497f89d693b9e9aad08d

#graph

트리의 지름을 구하는 문제와 유사하다.

다만, 모든 정점이 하나의 트리로 구성되어 있지 않기 때문에 bfs로 탐색 할 수 있는 트리들의 지름의 합을 구해주어야 한다.

트리의 지름을 구하는 방법은 임의의 정점 w를 잡고 가장 길이가 먼 x를 잡은 다음, x에서 가장 먼 정점 y를 잡는다면, x->w->y는 트리의 지름이 된다.

http://boj.kr/78fa6d73579a4dcc9792406988784b71

#dsu

union을 했을 때, 그 그룹 내에 모든 power의 곱의 합을 쿼리로 출력하는 문제

union할 때 power라는 새로운 리스트를 만들어 parent를 관리함과 동시에 power을 update해주자.

쿼리가 들어오면 매 쿼리마다 그 그룹을 union하고, power을 출력해주면 되는 문제.

http://boj.kr/962d0551399341fca76e608c7a277f89

#math

2^n개가 홀수개 있다는 거는, 해당 비트위치의 연산을 xor 했을때 1인 경우를 의미할 것이다.

그리고 최대 1개를 지운 다는 것은 전체 xor 한 값에 한번 더 해당 값을 xor연산 한것과 동치 일 것이다.

그렇게 해준 다음, 위 2 case의 최댓값을 출력시켜주자.

http://boj.kr/7d731722fa97414b9890186647ef5154

#bruteforce, #implementation

N이 매우 작기 때문에 매번 i or x한 값을 리스트에 넣은 다음, MEX를 구해주면 된다.

MEX를 구하는 방법은 여러가지 있겠지만 나는  i or x한값을  정렬했을때, 인덱스와 값이 다른 시점을 mex로 구현하였다.

XOR만 나오면 항상 정수론적인 생각을 먼저하게 된다...

http://boj.kr/9f0e9984f6f74a5bbc55140f7392a69e

#greedy #math

모든 자리에 퀸을 넣는 것이 가장 최적의 경우이다.

그렇다면 가로방향의 공격 쌍수, 세로방향의 공격 쌍 수 대각선 방향의 공격쌍수 이렇게 3가지로 나누어서 생각을 해보았을때, 점화식을 도출할 수 있다.

문제에비해 난이도가 저평가된것 같다..

#graph #scc

저번주에 푼다고 하고 못푼 문제다.

SCC으로 묶을수 있는 간선들은 모두 동치가 될 수 있다고 설명할 수 있다.

그렇기에 SCC단위를 정점으로 간소화 한다음, 이 정점 집합들을 하나의 SCC로 만들어야 하는 문제로 바꿀 수 있는데,

그렇다면 각 node의 indegree와 outdegree가 모두 1이상이 되어야 하기 때문에 max(indegree == 0, outdegree == 0)인 수를 찾으면 된다. 

SCC 구현 코드를 코사라주 알고리즘을 사용했는데, 아무래도 똑같은 그래프를 2개 만들다 보니 MLE가 자주 발생한다. 그렇기 때문에 비교적 느린 python3이나, 타잔 알고리즘으로 SCC를 구현해야 한다.

타잔알고리즘과 SCC를 정점으로 치환하는 방법을 배운 문제

http://boj.kr/08a130f1a4aa46f999147858eb0167d5

#greedy #stack

일단 m번 무조건 지워야 하기 때문에 최대 자릿수는 n-m자리일 것이다.

그렇다면 무조건 앞에 수를 가장 큰 수로 두어야 할 것이고, 스택에 하나씩 넣으면서 앞에 자리수가 뒤에자리수보다 작다면 계속 그 작업을 수행해주어야 할 것이다.

추가 반례로 모두 다 같은자리인경우 m번 연산을 안할경우가 있는데, 이 점을 따로 예외 처리해주자.

http://boj.kr/8dad6cb94d1f463d88f272ee0b64b3fe

#dfs #greedy

연산 내용이 주어진 트리의 부분 그래프의 가중치를 1 늘리는 과정이기 때문에 현재 노드를 기준으로 본다면, 현재 노드의 부모노드의 목표 weight보다 작으면 부모노드의 연산으로 수행할 수 있다.

그러기 때문에 대충 1번 노드를 root node으로 잡고 정답은 root node의 weight + sigma 2~n : max(node weight - parent node weight, 0)으로 정의할 수 있다.

dfs으로 각 노드의 부모노드와 목표 가중치를 비교하자

http://boj.kr/a09ad08634884c31a098ffded497cf20

#kmp #sweeping

KMP알고리즘을 수행하면, 원본 문자열에서 부분문자열이 몇개 있는지, 어디에 있는지 모두 구할 수 있을 것이다. 그렇다면 투 포일터를 활용해 l~r 범위 내에 모든 부분문자열이 있느냐?를 체크할 수 있다. 매번 체크를 해주면서 최소 구간을 찾자.

대충 시간복잡도를 O(N+M+2N) 정도로... 선형시간내에 해결할 수 있을 것이다.

http://boj.kr/cceb8d4ecef14112bc5d6e4c24dfccc0

#implementation, #math

m을 3진수로 나눌 때 bit가 2인 경우, 왼편, 그 외인경우 오른편에 두어 비트연산을 했을 때 그 수가 나올 수 있게 구현하면 된다.

http://boj.kr/0c05d9e6d3314b0a9cd8ca5efdcc19ff

#tsp 

각 좌표간의 거리를 n^2으로 구해 distance를 구한 다음, 그것을 활용 해 외판원순회를 해주면 된다.

Bitonic Tour라는 좌표상의 외판원순회 알고리즘이 있던데, 이 문제인줄 알았는데, 알고보니 더 쉽게 해결할 수 있었다. 

Bitonic Tour 공부해보면 좋을듯. .

http://boj.kr/c10781df6e05442d9b9a98e5476d1a15

#bruteforce

그리디하게 접근해볼까 하다가 같은 가장 사전순 작은 문자열 일때, 얼마나 더 길게 나눌것인가 생각을 좀 해보았는데, n이 매우작기 때문에 n^3으로 모든 문자열조합을 만드는 방식으로 풀 수 있다.

http://boj.kr/d743bf5e470f4c3e9548127e69f6bc6d

#bruteforce

1251과 동일

#stack #implementation

스택을 사용해 구현해주면 된다. 다만 신경써줘야할 부분은 태그 내에 공백이 있는 case를 예외처리 해주면 쉽게 풀린다.

http://boj.kr/25acd514eba14c8db23fb88953dca17f

#string #z

Z알고리즘 연습용으로 풀었다.

http://boj.kr/a8c73387d9d648c598068aa554adf430

#parametric search

반대로 생각해 T가 주어 졌을때, 모든 시간안에 얼음을 녹일 수 있는가? 라는 문제로 변경해보면, parametric search으로 T시간안에 녹일 수 있냐 없냐? 문제로 변경하게 된다.  이점을 이분탐색으로 찾아나갈 수 있다

추가로 삼분탐색으로도 풀수 있는데, 2차원 그래프에서 y를 녹는 정도 max(D), x축을 i번째 히터의 위치로 둔다면, convex한 형태의 그래프가 나오는데 이 그래프의 극솟값이 최적으로 놔둘 수 있는 위치 i가 된다.

두 방법에 대해 둘다 풀어봤다. 재미있는 문제

parametric search

http://boj.kr/e49d28bae70644588301cf277803e28f 

tenary search

http://boj.kr/4a5de21ad8454c478a65ef7a57c32f04   

#tenary search

두 사람의 거리차 d를 y축으로 time을 x축으로 둘 때, 그래프의 형태는 아래로 볼록한 convex한 형태로 나타내지고, 이 그래프의 극솟값은 최소거리차이 가 된다.

위 극솟값을 삼분탐색으로 찾아주면 된다.

http://boj.kr/1c9f769c1d1d412a82d787d7e9c9a75e

#math #ad_hoc

n이 주어지면 x, y의 합이 n이 되어야 하고, x, y의 각 자릿수의 합이 최대 1차이가 나는 x, y를 찾는 문제

n의 각 자릿수 / 2가 x,y의 그 자리수가 되어야 하고, 짝수면 그냥 /2 나누면 된다.

만약 홀수 일 때  x,y를 /2, /2+1 두개로 나누어야 하는데 이에 대한 예외처리를 잘 해주어야 한다.

"최대" 라는 키워드를 안봐서 무조건 1차이가 나게 해야하는줄 알고 맞왜틀을 좀 한 문제

http://boj.kr/69fa722882684894b13221939d5a8e4d

#graph

BFS, DFS 아무거나 사용하여 그래프 내에 연결되어 있는 component를 찾은 다음,

각 component별 백신의 작용 대상이 될 수 있는지를 검사해야 한다.

http://boj.kr/abb4485a04cb4965b254a0c03fbce12a

#lca

lca의 weight가 붙어 있는 버전

direction이 주어지는데, 아~무쓸데없다. 혼동을주기 위한용

lca의 깊이를 dfs로 수행할때 현재 노드까지의 누적 weight를 같이 계산해주자.

lca 전체 코드는 log n으로 수행할 수 있는 템플릿을 사용했다. 

http://boj.kr/f5303fc3ee484382906ea347cee1f3ea

#scc

TBD

#mst

지문에 낚시가 많지만 1번 정점은 아~~~무 쓸데가 없다.

adjust matrix를 구성할때도, 1번해당되는 edge는 연결안해도 된다.

이후 mst를 무난하게 구성하고, 필요한 weight, edge정보, 갯수를 다 추출하면 된다.

http://boj.kr/11e5c7b37a974c37b613863185406485

#math

우선 https://gratus-blog.tistory.com/74  이걸 많이 참고해서 공부하여 구현하였다.

뫼비우스 함수를 정의해야하는데,

μ(1)=1

n이 제곱수로 나누어지면 μ(n)=0

n이 서로 다른 k개의 소인수의 곱이면 μ(n)=(−1) ^ k으로 정의 할 수 있다.

이후 포함배제 원리에 따라 1부터 N까지 제곱인수가 없는 수를 계산하고, 이분 탐색을 통해 k번째수를 찾아보자.

http://boj.kr/55e8a5d137594aa2bb06e038568883fb

#math

앞서 설명한 #1557번에 n의 범위가 다르고 반대로 K번째 제곱수를 찾는 문제이다.

이분탐색하는 코드에서 전체 갯수가 아닌 N-전체 갯수하면 되는 덤으로 따라오는 문제

(이걸 오랫동안 생각했다)

http://boj.kr/79f6802fb1084766a7eec6932fe10b80

#bfs #tsp

내가 푼 방법은 현재 위치를 1번, 나머지 청소해야할 부분을 2,3,4.. 노드라고 생각하고 각 node별로 갈 수 있는 distance를 인접행렬로 만든 다음, 외판원 순회를 해주었다.

이거보다 더 쉽게 푸는 방법이 있는 듯하다. 구현 + tsp 무조건 플레이상이라고 생각하는데 G1인거봐선..

http://boj.kr/e9f75bd538f54ad7b5751ac563df6ee0

#ad_hoc, #math

배치는 순열의 사이클 구조를 이용하여 n이 4의 배수이거나 n ≡ 1 mod 4일 때만 가능하며, 그 외의 경우는 불가능하다.

조건을 만족할땐, 팩토리얼 연산을 통해 배치 수를 구해보자.

http://boj.kr/1c2d6b729bfb4dcaa5a087d12aa26bde

#binary_search, #sorting #hash

나이브하게 풀면 n^2이 난다. n <= 100000이기 때문에 시간초과 남.

target배열을 정렬한 다음, binary search를 통하여 몇번쨰 인덱스에 넣을수 있는지 찾아보자. 

결과 인덱스보다 앞에있으면 이길수있는 상대, 뒤에있으면 지는 상대일것이다.

추가로 비기는 경우를 대비해 미리 hash map에다 count해 비기는 상대의 수는 미리 구할 수 있을 것이다.

http://boj.kr/cf25dc06258f490782015d263405f442

#dfs #tree

트리를 구성하고 제거할 정점을 graph를 돌면서 제거해주자.

제거하는데 있어 인덱스 문제가 생길수 있으니 그래프를 deepcopy하여 처리하자.

이후 dfs해서 leaf node들을 체크해 1씩 증가시켜주자.

만약 제거할 node가 정점이라면 답은 0으로 따로 예외처리를 해주자.

http://boj.kr/d6475b90e6aa4991a43f148d568f143f

#implement #graph

그냥 머... 지문에 있는 대로 구현해주면 된다.

맵 넘어가면 그만 탐색하고500x500이라 10^6회 순회하면 무한 루프라고 판단되어 그만하게 처리해주었다.

개인적으로 같은 난이도였던 #2344보다 훨씬 쉬웠음.

그 문제는 배열의 인덱스를 수식으로 관리해주었어야 했는데 이건 그런것도 없다.

http://boj.kr/70e67c6b98b44b87b4a21ff28debf544

#greedy

관찰을 해보면, 5 * K >= K * T 라면, 그 문제를 푼다해도 무조건 광기력이 0이 된다. 다음과 같은 case들은 우선적으로 바로 풀어주자.

나머지 case들에 대해선, 문제의 난이도에 대해 정렬을 해주고, 따로 tuple에 최소 n만큼 되어야 그 문제를 풀이 할 수 있는 시간을 정의해 주었다. 

이후엔 구현

http://boj.kr/df79d52185a7415d9abd35f392a77e6d

#bfs

각 node를 시작으로 하는 BFS를 수행해주고 가장 긴 distance를 구하는 문제이다.

머.. 무난무난해서 설명할게 없다.

http://boj.kr/5b1a0643aab84b9fa2af34f29fa3c210

#bfs

간단한 BFS 문제지만, 정점번호가 string으로 되어 있는 문제이다.

dictonary에서 정점번호 - string을 매칭시켜준 다음, bfs하면된다.

체크해야하는 점은 매번 value를 찾는 과정을 O(n)으로 수행하면, TLE가 발생하기 때문에, 역방항 dictionary를 만들어서 O(1)로 해결해주어야 한다.

http://boj.kr/88482fc719b6431093b8c30907137e48

#bipartite_matching 

주식차트를 이분그래프로 변경하기 위해서 (i, k)번째 시점이 (j, k) 시점 보다 값이 적다면, 이분그래프를 그릴 수 있다.

그뒤론 적절하게 이분매칭의 최대 수는 같이 그릴 수 있는 차트와 같기 때문에 n - 이분매칭 최대수가 답이 된다.

여담으로 똑같은 코드로 12633, 12988을 해결할 수 있다.

http://boj.kr/b07bfed22b0b441ab71104a5392e8934

#greedy, #hash

n<=1000000 이기 때문에 o(n)으로 풀수있는 방법을 생각해보자.

교환이 무한정 가능하기 때문에 dictonary으로 해당 요구하는 문자열이 있는지 매번 체크해주자.

아이디어 구현이 까다로웠던 문제.

http://boj.kr/08f3f038fcc9427ba56082f202a41329

#math, #graph

문제 자체는 순열을 Cycle Decomposition 했을 때, 가장 긴 length를 구하는 문제일거라 생각했다.

예제를 유심히 관찰해보자. 예제를 decomposition 해보면 3, 1, 2가 나오는데 답이 6이다.

답은 모든 length의 최대공배수를 구하면 된다. 예제에서 많은 힌트를 얻었다.

추가로 cycle의 갯수가 1개, 2개일때 예외처리를 잘해주자.

http://boj.kr/25d94752491c421bbeda4788d16a5cbe

#dp

각 쿼리 별 모든 문자열로 만들수 있는 경우의수를 구하는 문제이다.

각 단어는 무작위로 배치할 수 있으니 dictonary활용하여 a몇개, b몇개...z가 몇개 포함되어있는지 체크해주자.

dp[j]은 dp[0:j] 까지 만들수 있는 문자열의 경우의수로 정의해보자.

dp[j+1]=(dp[j+1]+dp[j−k]× 부분 문자열의 개수) mod MOD 으로 점화식을 세울 수 있다.

http://boj.kr/05c384ea5587447990aff951f4a63c5d

#14302와 동일

#graph, #dsu

3차원 공간을 graph으로 변환해 MST를 만드는 cost를 구하는 문제

무엇보다 구현과 input이 많이 이상하다...

코드가 너무 더럽다.... 시간이 있다면 수정해서 올릴 것.

#flow

전형적인 Flow Min cut 문제 

이분 그래프를 모델링 할 때, source -> 맞출수있다 -> 맞출수없다 -> sink 으로 모델링 가능하다

이렇게 모델링 돌려주고 edmonds karp 사용해서 답을 구하자.

http://boj.kr/49665f04166b44068a5357afb7cb8d21

#prefix sum

배열 2개를 누적합 해주면서 값이 겹치는 경우를 매번 update해주면 된다.

http://boj.kr/23d4f5fc5eec4b18af31bf44acd97ac6

#dp

n까지 도달하는데, 몇가지의 방법이 필요한가?를 묻는 문제

dp[n]을 n으로 만들수 있는 가짓수라고 가정했을때,

모든 자리수의 분해합을 i라고 정의했을때 dp[n]은 매번 dp[i] + 1로 update 할 수 있다.

먼가 말로 설명하면 어렵다... 코드보면 쉽게 이해할수있을 듯

http://boj.kr/313e5964c20e4a6a9c035c1b8fef54ac

#adhoc, #graph #greedy

입력범위가 매우 크기 때문에 o(1)로 푸는 방법을 생각해보자.

연결할 수 있는 최대 edge보다 m이 크다면, 모두다 연결 가능 할 것이다.

그렇지 않다면, 최대한 greedy하게 연결해야 하는데, 1번 node와 그 외 node를 먼저 다 연결하자.

그 다음은 어떻게 연결해야 최적으로 연결하는건지 생각해보자.

http://boj.kr/de287d5689a84ee59b6babbee96806b8

#bfs

BFS로 digit를 만드는 연산을 추적하면 되는 문제

문자열 + 연산으로 명령어를 append한다면 TLE난다. (+연산이 매우느림)

따라서, 구할 수 있는 연산들을 다 찾은 뒤,  마지막에 합치는 방식으로 최적화 해보자.

본 난이도보단 어려웠던 문제.

http://boj.kr/7b079291f2e84a378f2520e2b3432e9b

#flow #bipartite_matching

소수는 홀수이고, 홀수 + 짝수 = 홀수 인 성질을 이용해 이분매칭을 하기 위한 이분 그래프의 설계를 홀수집합, 짝수집합으로 나눌 수 있다.