본문 바로가기

알고리즘

 (405)
동적계획법. [9465] [1. 문제 설명] https://www.acmicpc.net/problem/9465 [2. 풀이 접근] 완전 탐색 접근.. 동작방식 이차원 배열의 좌상단 -> 우하단으로 이동하면서, 선택 여부에 따라 재귀를 호출한다. 현재 위치를 선택하지 않는 경우 현재 위치를 선택하는 경우 => 상,하,좌,우로 인접한 위치를 선택하지 못하게 한다. => 재귀 호출 한다. => 상,하,좌,우로 인접한 위치를 다시 선택 할 수 있게 업데이트 한다. 위와 같은 동작방식에서 메모이제이션을 적용하기는 어렵다. here 위치에서 앞으로 선택 대상은 색칠된 위치들이다. 그러나 이 위치들은 here 보다 앞선 1,2,3, 선택 여부에 따라 고려 대상이 될 수도 있고, 안될 수도 있다. 좌상단 -> 우하단 이동 방식으로는 최적 부분..
동적계획법. [11052] [1. 문제 설명] https://www.acmicpc.net/problem/11052 [2. 풀이 접근] 나에게는 정답률에 비해 다소 까다로웠던 문제... 완전 탐색 풀이부터 접근... 메모이제이션 현재가지 m 개 샀다고 하자 이번에는 l 번째 pack 을 사는 경우를 따져본다. 즉, 메모이제이션 해야하는 팩터는 m 과 l 로 결정 할 수 있다. 첫번째, 이번 pack 을 사지 않고, 다음 pack 부터 사는 경우=> 캐시를 최대 값으로 업데이트 두번째, 이번 pack 을 여러번 사고, 이 금액과 다음 pack 을 사는 재귀 결과의 합 => 캐시를 최대 값으로 업데이트 => 이 부분을 구현하는데 좀 오래걸렸는데,, 왜 그랬을까? => 이 외에도, 완전 탐색에서 메모이제이션을 적용하는 과정에서 내 생각대..
동적계획법. [9095 / 2193] [1. 문제 설명] https://www.acmicpc.net/problem/9095 https://www.acmicpc.net/problem/2193 [2. 풀이 접근] 문제 9095 완전 탐색에서 시작한다. 부분 문제 정의: 현재 값이 N 일 때, 목표로 하는 n 까지 만들 수 있는 경우의 수를 반환 한다. 메모이제이션: 현재 값이 N 인 경우 문제 2193 완전 탐색에서 시작한다. 맨 앞자리는 1을 고정 한 채로 시작한다. 주의 할 점 => 바로 앞에 오는 수가 0인 경우와 1인 경우를 별도로 생각해야 한다. => 1000~~~ 인 경우 뒤에 오는 숫자는 0과 1 모두 올 수 있지만 => 1001~~~ 인 경우 뒤에 오는 숫자는 0 만 올 수 있기 때문이다. 부분 문제 정의: 가장 마지막에 설정 된..
동적 계획법. [1010] [1. 문제 설명] https://www.acmicpc.net/problem/1010 [2. 풀이 접근] 완전 탐색에서 시작한다. 다리가 교차되지 않기 위해서는 일정한 순서를 갖고 다리를 연결 해야 한다. 강 서쪽 에서 1번 다리와 강 동쪽에서 2번 다리를 연결 강 서쪽 2번 다리는 3번 다리 이후부터 연결 할 수 있음 강 서쪽 내 모든 다리가 이러한 규칙대로 모두 연결 된 경우 한가지 경우 완성 중복 문제 빨간색 구간이 어떻게 연결되든 화살표 이후 경우의 수에는 영향을 주지 않는다. 즉, 한번 계산해 놓은 값을 재활용 할 수 있다. 서쪽과 동쪽에서 연결 된 경우에 대해서 메모이제이션을 적용 할 수 있다. [3. 코드]
분할정복. [2104] [1. 문제 설명] https://www.acmicpc.net/problem/2104 [2. 풀이 접근] 문제만 읽어 보면 구간 트리로 해결 할 것 처럼 보인다. 구간의 합을 O(N) 에 구하지 않아야 한다. 구간의 최소 값을 O(N) 에 구하지 않아야 한다. 그러나 구간 트리는 구간 내 값이 변화 할 때 사용 하는 의미가 있다. 구간 내 값이 변하지 않는 다면, 부분 합을 통해 구간 합을 O(1) 에 구할 수 있기 때문이다. 분할 정복 구현 패턴을 따른다. 기저 사례, 한번에 해결 할 수 있는 경우 왼쪽 구간에 대한 재귀 호출 오른쪽 구간에 대한 재귀 호출 전체 구간에 대한 O(N) 내 문제 해결 전체 구간에 대한 O(N) 내 문제 해결 먼저 mid 와 (mid+1) 에 대한 문제를 해결한다. # (이..
분할 정복. [1725] [1. 문제 설명] https://www.acmicpc.net/problem/1725 [2. 풀이 접근] 기타 참고 자료 https://testkernelv2.tistory.com/248 [3. 코드]
분할정복. [2261] [1. 문제 설명] https://www.acmicpc.net/problem/2261 [2. 풀이 접근] 주의 사항 중복되는 점을 제거해서는 안된다. => 같은 점이 있다고 했을 때, 모든 점들 간 최소 거리는 0 이 되는 것이 맞기 때문이다. => 중복되는 점을 제거하면 이러한 경우는 찾을 수 없다. 분할 정복 및 스위핑으로 접근해야 한다. 먼저 분할 정복을 사용하는 이유이다. x 를 기준으로 정렬 후, 모든 경우의 수를 찾는 다면, 그 시간 복잡도는 O(N2) 이므로 시간 내 풀 수 없다. 분할 정복 패턴을 적용한다. => 재귀로 구현하므로 기저 사례를 먼저 작성한다. => 기저 사례는 [head, tail] 구간의 길이가 2인 경우, 즉 두 개 의 점간 거리를 반환한다. => head ~ mid 구..
완전 탐색. [1759] [1. 문제 설명] https://www.acmicpc.net/problem/1759 [2. 풀이 접근] 핵심 포인트 재귀 구현 패턴을 따른다. 기저 사례 처리 => 기저 사례에서, 완성된 한가지 조합이 답이 될 수 있는지 체크 => 종료 (성공 여부 리턴...) 이번 index 를 선택하지 않는 경우 이번 index 를 선택하는 경우 => 이번 선택을 vector 에 push_back() => 재귀 호출 => 재귀 호출 종료 후, vector 에서 pop_back() 입력으로 주어진 문자 배열을 먼저 정렬한다. 정렬 여부 조건을 기저사례에서 체크 할 필요가 없다. 기저 사례에서 완성 된 조합을 정렬하는 작업이 필요하다. 재귀 호출하여 완전 탐색에서 발견된 정답 데이터는 stack 에 저장하도록 한다. ..
완전 탐색. [2309, 1182] [1. 문제 설명] https://www.acmicpc.net/problem/2309 https://www.acmicpc.net/problem/1182 [2. 풀이 접근] 이번 문제는 재귀를 이용한 전형적인 완전 탐색 문제이다. 여기서는 재귀 구현 방식에 대한 내용을 정리한다. 개인적으로 재귀를 이용한 완전 탐색 구현 시 코드는 아래 두가지 패턴이 있다고 생각한다. 반복문 없이 재귀를 여러번 호출 반복문 내부에서 재귀를 호출 단, 두 패턴 사용은 상황에 맞게 적절히 사용해야 한다. 먼저은 1182 풀이이다. 여기서는 1번 패턴으로 작성한 코드만 통과한다. 2번 패턴이 틀린 이유는 코드 구조 상 마지막 원소만 선택되지 않은 경우를 체크 할 수 없기 때문이다. index == N-1 인 경우에 재귀 호출을 ..
SCC 관련 솔루션 [1. 개요] SCC 의 특성 방향 그래프에서 정의 된다. 같은 SCC 에 속한 노드들은 Cycle 을 형성한다. => 같은 SCC 에 속한 노드 간 경로는 반드시 존재한다. SCC 를 연결하는 간선들을 모으면 DAG 를 형성한다. SCC 를 응용한 문제 SAT SCC 를 찾는데 사용되는 알고리즘은 아래와 같이 크게 두가지가 있다. 타잔 알고리즘 => 시간 복잡도 O(V+E) 코사라주 알고리즘 타잔 알고리즘은 한번의 DFS 를 통해 모든 SCC 를 찾을 수 있다. 따라서 타잔 알고리즘의 구현 패턴을 익히도록 한다. dfsAll 을 수행한다. 각 dfs 는 프로토 타입은 아래와 같이 작성하며, 동작은 아래와 같다. # int dfs(u int), u 에서 dfs 수행 시 가장 먼저 방문 한 방문 순서를 반..

티스토리툴바