본문 바로가기

알고리즘/Baekjoon

 (196)
네트워크 유량. [11405] [1. 문제 설명] https://www.acmicpc.net/problem/11405 [2. 풀이 접근] [3. 코드]
네트워크 유량. [2316] [1. 문제 설명] https://www.acmicpc.net/problem/2316 [2. 풀이 접근] 유량 네트워크로 접근해야 한다. 단, 특정 도시(이하 정점) 을 여러번 지나갈 수 없다. 포드-풀커슨 알고리즘은 간선의 유량에 대해서 동작한다. 따라서, 정점을 간선처럼 만들어야 한다. # 이하 코드 주석 참조. 주의 할 점. 정점을 간선처럼 만들 때는, 연결 된 두 도시를 입력받는 시점에서 만들면 안된다. 모든 입력을 받고 나서, edge 를 순회하면서 확인해야 한다. => 원하는 형태 : {u1 -> u2} -> {v1 -> v2} => 잘못된 형태 : {u1 -> u2} v2} \ > {z1 -> z2} # 즉, 이미 정점 u 는 사용하였는데, 정점 v 에서 u2 와 연결되고, u2->z1 간선..
네트워크 유량. [17412] [1. 문제 설명] https://www.acmicpc.net/problem/17412 [2. 풀이 접근] 인접한 두 도시를 연결하는 edge 의 용량을 1로 하는 유량 네트워크에서 포드-풀커슨 알고리즘을 이용하여 최대 유량을 계산한 결과는 Source 에서 Sink 로 가는 겹치지 않는 경로의 개수가 된다. 자세한 설명은 코드 주석 참조. [3. 코드]
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. 시간 초과 코드]
kmp. [1701] [1. 문제 설명] https://www.acmicpc.net/problem/1701 [2. 풀이 접근] 얼핏보면 kmp 와는 관련이 없어 보이지만, kmp 에서 부분 일치 테이블을 이용하여 풀 수 있다. 부분 일치 테이블에 저장된 값이 의미하는 바를 생각하면 n 개의 글자만큼 일치 했을 때, 접두사도 되고 접미사도 되는 최대 길이 이다. 이 값이 0보다 크다면 동일한 부분문자열이 전체 문자열에서 앞에도 오고 뒤에도 오게 된다. 즉, 부분 문자열이 적어도 두번 발생하게 된다. 그래서, 입력으로 주어지는 문자열에 대해서 부분 일치 테이블 계산 한 뒤, 여기서 최대값을 출력하면 될 것 같지만, 좀 더 고민해야 하는 부분이 있다. 아래 입력에 대해서는 정확한 결과를 구하지 못한다. qbqtzqqt 위 문자열에..
위상정렬. [2056] [1. 문제 설명] https://www.acmicpc.net/problem/2056 [2. 풀이 접근] 일반적인 위상 정렬 풀이로 접근한다. 동시에 처리가능한 작업들이 있으므로, bfs 를 응용하여 처리한다. dfs 로는 "동시에 처리 가능한 작업" 에 대한 처리가 힘들다. 주의 할 점 전체 작업이 끝나는데 걸리는 시간은 가장 마지막에 실행되는 작업에 의존적이지 않다. 가장 마지막에 끝나는 작업에 의존한다. 예를들어, {a -> b}, {d -> e -> f} 가 있을 때, f 가 가장 마지막에 실행 되지만, b 를 처리하는데 걸리는 시간이 다른 작업 보다 월등히 크다면 이러한 접근은 후순위 작업의 실행 시점에도 영향을 준다. => 코드 참조. [3. 코드]

티스토리툴바