본문 바로가기

알고리즘

 (401)
네트워크 유량. [2316] [1. 문제 설명] https://www.acmicpc.net/problem/2316 [2. 풀이 접근] 유량 네트워크로 접근해야 한다. 단, 특정 도시(이하 정점) 을 여러번 지나갈 수 없다. 포드-풀커슨 알고리즘은 간선의 유량에 대해서 동작한다. 따라서, 정점을 간선처럼 만들어야 한다. # 이하 코드 주석 참조. 주의 할 점. 정점을 간선처럼 만들 때는, 연결 된 두 도시를 입력받는 시점에서 만들면 안된다. 모든 입력을 받고 나서, edge 를 순회하면서 확인해야 한다. => 원하는 형태 : {u1 -> u2} -> {v1 -> v2} => 잘못된 형태 : {u1 -> u2} v2} \ > {z1 -> z2} # 즉, 이미 정점 u 는 사용하였는데, 정점 v 에서 u2 와 연결되고, u2->z1 간선..
이분매칭 [1. 개요] 이분 매칭을 설명하기에 앞서 이분 그래프에 대한 개념 정의 그래프의 모든 정점이 두 그룹으로 나누어 질 때 서로 다른 그룹의 정점들은 연결되지만 같은 그룹의 정점들은 서로 연결하지 않는 형태의 그래프 두 집합 간의 대응 관계를 표현하기 위해 사용 https://testkernelv2.tistory.com/338 매칭 그래프에서 끝점을 공유하지 않는 간선의 집합을 의미한다. 여기서 끝점을 공유하지 않는다는 의미는 아래와 같다. 두개 이상의 간선이 공유하는 정점이 있는 경우. 아래와 같은 형태의 그래프에서 어떤 조건을 만족하는 edge 만 선별하였다고 가정했을 때, 빨간색 간선이 선별된 edge 그래서 매칭 문제(최대 매칭 문제) 는 그래프에서 가장 큰 매칭을 찾는 문제를 말하며, 가장 큰 매..
네트워크 유량. [17412] [1. 문제 설명] https://www.acmicpc.net/problem/17412 [2. 풀이 접근] 인접한 두 도시를 연결하는 edge 의 용량을 1로 하는 유량 네트워크에서 포드-풀커슨 알고리즘을 이용하여 최대 유량을 계산한 결과는 Source 에서 Sink 로 가는 겹치지 않는 경로의 개수가 된다. 자세한 설명은 코드 주석 참조. [3. 코드]
네트워크 유량 - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/MATCHFIX [2. 풀이 접근] [3. 코드]
네트워크 유량, 포드-풀커슨 [1. 개요] 그래프에서 간선에는 가중치라는 개념이 있다. 여기서 가중치 대신 용량이라는 개념을 적용하여, 일종의 파이프라고 모델링을 하고 이 간선을 통해 물을 흘려보낸다고 하자. 출발지에서 목적지까지 물을 흘려보낸다고 했을 때, 이 간선에 흐르는 양을 유량이라고 부를 수 있다. 이렇게, 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 흐름 혹은 유량을 보낼 수 있는지 계산하는 문제를 네트워크 용량 문제라고 한다. [2. 유량 네트워크] 각 간선에 용량(Capacity) 라는 추가 속성이 존재하는 방향 그래프를 말한다. 이 간선을 통해 유량을 흘려 보낼 수 있다 정점 u 에서 정점 v 로 가는 간선에 대해서 아래와 같이 표기하도록 한다. 용량: c(u, v), capacity 유량: f(u..
kmp. [13506] [1. 문제 설명] https://www.acmicpc.net/problem/13506 [2. 풀이 접근] 고찰 아래 코드에서 H 에 해당하는 부분을 for 문 안에서 구하면 시간 초과 발생. 물론 이 때는, postfix 만큼을 원래 문자열 S 에서 제거하여 생성하였음. 부분 문자열을 만드는데 걸리는 시간이 선형 시간이라서? prefix 와 postfix 를 만들 때 에도 비슷하게 걸릴 거 같긴 한데, [3. 코드]
kmp. [7575] [1. 문제 설명] https://www.acmicpc.net/problem/7575 [2. 풀이 접근] 임의의 프로그램에 대해서, 발생 할 수 있는 K 개의 모든 코드를 구하고, 이 코드를 나머지 프로그램에서 찾는다. 문제에서는 코드 길이가 K 이상인 경우에도 바이러스라고 판정가능하다 하였는데, 사실 K 개만 일치하면, K개 보다 큰 경우에 대해서 코드 일치 여부와 관계 없이 바이러스 코드로 추정 할 수 있다. # K+1 개, 일치 => K 개가 일치하므로 상관 없다. # K+1 개. 불일치 => 역시 K 개는 일치하므로 상관 없다. 일종의 함정인 셈 # K=4 라고 하면, # K=5 코드, K=6 코드를 구할 필요가 없다. 연산 횟수를 대강 계산하면, 생성할 수 있는 코드 개수 : 1000개 (정확하..
kmp. [11585] [1. 문제 설명] https://www.acmicpc.net/problem/11585 [2. 풀이 접근] kmp search 원형에 대해서 문자열을 이어 붙이고, 이 문자열에서 다른 문자열을 찾는 전형적인 kmp 탐색 문제이다. 주의 할 점 주석에도 언급했지만, 이어붙인 문자열 X=2B 에 대해서 X[len(B)...] 에서 A 를 찾는 것은 의미가 없다. 기약 분수 분자와 분모의 최대공약수를 찾아야 한다. 유클리드 호제법을 이용하여 계산하도록 한다. 생각이 안나서 과거에 정리한 글을 참조 https://testkernelv2.tistory.com/107 [3. 코드]
kmp. [10266] [1. 문제 설명] https://www.acmicpc.net/problem/10266 [2. 풀이 접근] 최초에 생각해 본 방식 첫번째 시계의 배치를 1도 단위로 회전시켜서 이어 붙인다. 여기서, 두번째 시계의 배치를 찾는다. 그런데, 각도가 0 ~ 360,000 이므로, 1도 단위로 회전 시키면 메모리 및 시간 초과가 발생할 것이다. 현실적인 시간/공간 복잡도가 되도록 해야 한다. 올바른 풀이 역시 첫번째 시계의 배치를 확장한다. 그러나, [0, 360,000) 에 대해서 각도가 있으면 1, 없으면 0 으로 설정한다. 회전 한 경우는 [360,000, 720,000) 범위에 대해서 1 또는 0으로 설정하도록 한다. 이제 이 배치에서 두번째 시계의 배치를 찾는다. 즉, 첫번째 시계의 배치는 길이가 72..
kmp. [4354] [1. 문제 설명] https://www.acmicpc.net/problem/4354 [2. 풀이 접근] 시간 초과 풀이 게시판 참조한 풀이 기타 정해 풀이 [3. 코드] [4. 시간 초과 코드]

티스토리툴바