본문 바로가기

알고리즘/Baekjoon

 (196)
컨벡스 헐. [1708] [1. 문제 설명]https://www.acmicpc.net/submit/1708/87944456[2. 풀이 접근]컨벡스 헐 알고리즘의 기본 문제[3. 코드]
네트워크 유량. [6086] [1. 문제 설명]https://www.acmicpc.net/problem/6086[2. 풀이 접근]동일한 edge 가 여러 번 주어질 수 있다.이 경우 해당 edge 의 용량을 그 만큼 늘려 주도록 한다. 그리고,,, [3. 코드]
아호코라식. [10256] [코드]
트라이. [5052] [1. 문제 설명]https://www.acmicpc.net/problem/5052[2. 풀이 접근]공통 된 접두어가 있는 경우 해당 목록은 일관성이 없다고 볼 수 있다.트라이를 이용하여, 공통된 접두어가 있는지 확인 할 수 있다.[3. 코드]
기타. [11401] [1. 문제 설명]https://www.acmicpc.net/problem/11401[2. 풀이 접근]페르마 소정리를 이용하여, 모듈러 연산의 분배 법칙을 유도해야 한다. 여기서 p 는 1,000,000,007 로 이 값은 소수이다.이 값이 소수임이 문제에 있진 않지만.,,z 와 p 가 서로소가 될 수 있나?[3. 코드]
정렬. [20920] [1. 문제 설명]https://www.acmicpc.net/problem/20920[2. 풀이 접근]기본적인 접근중복된 단어를 체크할 때, multiset 이나 map 을 이용해서 카운트multiset 보다는 map 을 이용하는게 나을지도,key 를 string, value 를 중복된 개수성능 개선문제에 제시된 정렬 우선순위과 관계 없이, 입력된 문자열 배열을 단어 순으로 정렬하면, 중복된 단어는 서로 인접해 있다는 것을 이용하도록 한다.[3. 코드]
부분합. [25682] [1. 문제 설명]https://www.acmicpc.net/problem/25682[2. 풀이 접근] 완전 탐색모든 구간에 대해서, 색칠해야 할 개수를 확인 후 최소값을 업데이트 해나가는 방법위 방식은 3중 for 문을 유도하며, N, M, K 가 최대 2000 까지이므로, 1초 안에 계산하기 어려움,그러나, 모든 구간에 대해서는 확인 해봐야 함.# 어떤 구간이 최소가 될지는 알 수 없기 때문,즉, 특정 구간에 대해서 (crop? 한 영역) 에서 몇번 색칠 할 지를 logn 이하로 확인 할 수 있어야 한다.결과의 특성문제 조건 상, K*K 로 잘라내고, 색칠한 형태는 아래와 같은 두가지 구조만 갖는다.(y, x) = (1, 1) 위치가 검정색인 경우 => Case A(y, x) = (1, 1) 위치가 ..
탐욕법. [1339] [1. 문제 설명] https://www.acmicpc.net/problem/1339 [3. 코드]
분할 정복. [5904] [1. 문제 설명] https://www.acmicpc.net/problem/5904 [2. 풀이 접근] 생성 되는 문자열은 Left / Middle / Right 로 구성 되고 있으며, 여기서 Left 와 Right 는 서로 같다. 최소 어느 정도의 k 일 때 해당 문자열이 찾고하는 위치를 포함하게 된다. 여기서, Left 와 Middle 의 문자열 각각의 길이를 알 수 있기 때문에 찾고자 하는 문자열이 Left 와 Middle 의 속하는지 확인하고, Left 에 속하면 재귀 호출을 반복하고, Middle 에 속하면 M 인지 O 인지 바로 알 수 있다. 마지막으로 Right 에 속하는 경우는 Left 에 속하는 것과 같다고 볼 수 있으므로, 찾고자 하는 문자의 위치를 Left 와 대칭되는 위치로 변경하..
이분탐색. [2473] [1. 문제 설명] https://www.acmicpc.net/problem/2473 [2. 풀이 접근] 먼저 두 용액의 조합을 모두 찾는다. 이제 각 조합에 대해서 한 용액만 첨가하여 0에 가장 가까워지는 조합을 찾아내도록 한다. 주석 참조 삼분 탐색 (?) [3. 코드]

티스토리툴바