본문 바로가기

분류 전체보기

 (694)
네트워크 유량, 포드-풀커슨 [1. 개요] 그래프에서 간선에는 가중치라는 개념이 있다. 여기서 가중치 대신 용량이라는 개념을 적용하여, 일종의 파이프라고 모델링을 하고 이 간선을 통해 물을 흘려보낸다고 하자. 출발지에서 목적지까지 물을 흘려보낸다고 했을 때, 이 간선에 흐르는 양을 유량이라고 부를 수 있다. 이렇게, 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 흐름 혹은 유량을 보낼 수 있는지 계산하는 문제를 네트워크 용량 문제라고 한다. [2. 유량 네트워크] 각 간선에 용량(Capacity) 라는 추가 속성이 존재하는 방향 그래프를 말한다. 이 간선을 통해 유량을 흘려 보낼 수 있다 정점 u 에서 정점 v 로 가는 간선에 대해서 아래와 같이 표기하도록 한다. 용량: c(u, v), capacity 유량: f(u..
각종 ref url 댓글에 작성하시오
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 관련 솔루션 [1. 개요] [2. 구현 패턴] 구현 시 헷갈리면, 최초 위치에서 탐색이 어떻게 되는지 떠올리도록 한다. [3. 예제] https://testkernelv2.tistory.com/593 https://testkernelv2.tistory.com/595 https://testkernelv2.tistory.com/596 https://testkernelv2.tistory.com/597 https://testkernelv2.tistory.com/598 https://testkernelv2.tistory.com/599
kmp. [1701] [1. 문제 설명] https://www.acmicpc.net/problem/1701 [2. 풀이 접근] 얼핏보면 kmp 와는 관련이 없어 보이지만, kmp 에서 부분 일치 테이블을 이용하여 풀 수 있다. 부분 일치 테이블에 저장된 값이 의미하는 바를 생각하면 n 개의 글자만큼 일치 했을 때, 접두사도 되고 접미사도 되는 최대 길이 이다. 이 값이 0보다 크다면 동일한 부분문자열이 전체 문자열에서 앞에도 오고 뒤에도 오게 된다. 즉, 부분 문자열이 적어도 두번 발생하게 된다. 그래서, 입력으로 주어지는 문자열에 대해서 부분 일치 테이블 계산 한 뒤, 여기서 최대값을 출력하면 될 것 같지만, 좀 더 고민해야 하는 부분이 있다. 아래 입력에 대해서는 정확한 결과를 구하지 못한다. qbqtzqqt 위 문자열에..
shell script 정리 [1. 개요] 리눅스에서 윈도우 배치파일에 대응되는 shell script 작성 및 사용법 정리 [2. 기본적인 작성법] [3. 변수] 기본적인 변수 작성 myvar = 5 myvar = $(ls -l | grep mylog) # 명령어 결과를 저장 디폴트 값이 있는 변수 NPROC = ${BUILD_CONCURRENCY:-$(grep -c ^processor /proc/cpuinfo 2>/dev/null || 1)} BUILD_CONCURRENCY 가 정의되어 있다면, 이 값을 NPROC 에 할당하고, 정의되어 있지 않다면, 명렁어 결과를 NPROCE 에 할당 여기서도, 표준출력이 없다면 1을 사용한다. => stderr 을 전부 null 에 버리므로, stdout 이 없다면, 1 을 사용할 수 밖에 ..

티스토리툴바