본문 바로가기

알고리즘일반10

백트래킹 vs DFS 알고리즘 문제를 풀다보면 DFS인 것 같은데 백트래킹으로 분류된 문제들이 있다. 헷갈린 부분이 있어서 이번 기회에 확실히 정리를 하고 넘어가고자 한다. * DFS (깊이 우선 탐색) 가능한 모든 경로를 다 탐색한다. 따라서, 불필요한 경로도 무조건 끝까지 탐색을 하기 때문에 경우의 수를 줄이지는 못한다. * 백트래킹 (Back-tracking) 답을 찾아가는 도중, 지금의 경로가 답이 될 것 같지 않으면 더이상 진행하지 않고 윗단계로 되돌아간다. 이를 가지치기라고 하는데, 불필요한 경우의 수를 줄일 수 있으므로 시간복잡도를 개선할 수 있다. 문제풀이에서는 DFS로 모든 경우의 수를 완전탐색하는 과정 중에 조건문을 걸어서 답이 절대로 나올 수 없는 상황을 정의하고, 해당이 되면 탐색 중단 후 그 이전으로 .. 2023. 2. 19.

닥익스트라 최단경로 알고리즘 다익스트라 알고리즘 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'한 뒤에, 그 노드를 거쳐 가는 경우를 확인하여 최단 거리를 갱신하는 방법이다. 우선순위 큐를 이용하여 풀 수 있다. 1. 문제가 주로 한 정점에서 다른 정점까지 가는 최단거리를 계산하는 게 주로 나온다. 2. Java의 경우 class Node를 만들어서 정점과 간선을 표현하자. // PriorityQueue 사용을 위해 Comparable 사용함 class Node implements Comparable { int v; // 정점 int c; // 이동값 Node (int v, int c) { this.v = v; this.c = c; } @Override public int compareTo(Node o) .. 2022. 10. 13.

플러드 필(Flood Fill) 알고리즘 플러드 필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다. 플러드 필 문제는 BFS/DFS 알고리즘으로 풀 수 있다. [BFS의 풀이과정] 1. 시작하는 칸을 큐에 넣고 방문 표시를 한다. 2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 탐색을 한다. 3. 해당 칸을 이전에 방문했다면 무시하고, 처음 방문했다면 방문 표시를 하고 해당 칸을 큐에 넣는다. 4. 큐의 모든 원소가 빌 때까지 2를 반복한다. 5. 모든 칸이 큐에 1번씩만 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. ※ 참고 : https://blog.encrypted.gg/941 2022. 10. 1.

이분탐색 알고리즘(Upper Bound, Lower Bound) 오름차순으로 정렬된 배열에서 찾고자 하는 값 key가 있을 때, Upper Bound는 key보다 큰 첫번째 위치(초과)를 반환한다. Lower Bound는 key보다 크거나 같은 첫번째 위치(이상)블 반환한다. 예) 배열 {1, 3, 3, 5, 7}이 있을 때, key = 3이면 Upper Bound = 3(인덱스), Lower Bound = 1(인덱스)가 된다. key = 2이면 Upper Bound = 1(인덱스), Lower Bound = 1(인덱스)가 된다. lower bound, 하한은 찾고자 하는 값 '이상'의 값이 처음으로 나타나는 위치를 의미한다. 즉, 왼쪽부터 볼 때 찾고자 하는 값이 같거나 큰 경우를 처음 만나는 위치를 의미한다. key 값이 4일 때 처음 마주하는 키 값 이상을 갖고.. 2022. 9. 22.

Java의 자료구조 사용법 1. HashMap // key:String, data: Integer으로 선언 HashMap map = new HashMap(); // 값 삽입하기 for (String key : A) { map.put(key, map.getOrDefault(key, 0)+1); // key를 찾아서 그 값을 읽어서 +1해서 다시 입력하기. } // map에서 각 키의 값을 읽어서 제일 큰 수인 key를 고르는 구문 for (String key : map.keySet()) { if (map.get(key) > max) { max = map.get(key); ans = key; } } 2022. 9. 22.

메모이제이션을 통한 동적 프로그래밍 동적 프로그래밍(dynamic programming)은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다. 메모이제이션(memoization)은 하위 문제가 중첩될 때 재귀 호출을 감소시키는 간단하면서도 아주 뛰어난 기법이다. 본질적으로 메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다. * 메모이제이션 구현 int fib(int n, int[] memo) { if (n == 0 || n == 1) return n; // memo 테이블을 확인해 fib(n)이 이미 계산된 건지 본다. if (memo[n] == 0) { // 값이 없으면 재귀호출 실행 memo[n] = fib(n-2, memo) + fib(n-1, memo); } return memo[n]; // 이미 계산된 값이 .. 2022. 9. 20.

재귀함수 - 재귀적으로 작성하는 법 1. 재귀 카테고리 : 반복 실행 - 반복적으로 한 작업을 실행하는 알고리즘이다. - 파라미터를 전달해 반복 계산한다. - 재귀에는 항상 종료 조건이 있어야 한다.(!) - 재귀 함수는 전체 작업의 일부만 수행하고, 나머지는 재귀 호출에 위임한다. 2. 재귀 카테고리 : 계산 - 하위 문제의 계산 결과에 기반해 계산할 수 있다. - 하위 문제는 입력값을 더 작게 한 똑같은 문제이다. - Factorial 함수가 대표적이다. - 계산 방식은 "상향식"과 "하향식"이 있는데, 상향식은 루프와 재귀의 방식이 같다. - 하향식이야 말로 재귀를 사용하는 주된 이유이다. 3. 하향식 재귀 : 새로운 사고방식 3-1. 하향식 사고 절차 a. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자. b. 문제의 하위 .. 2022. 9. 19.

문자열 입력 처리 방법 1. 문자열에서 (-) 기호를 기준으로 분리하고, 그 토큰은 (+)를 기준으로 다시 분리할 때 a. 입력받은 문자열은 - 기준으로 분리한다. b. 자른 토큰들을 + 기준으로 다시 분리한다. c. 자른 토큰들을 정구형으로 캐스팅해서 합친다. str = in.next(); String[] sub = str.split("-"); // -로 문자열을 자른다. for (int i=0; i 2022. 9. 19.

온라인 코딩 테스트의 사전준비 1. 연습장과 필기 도구 재귀 구조를 구현할 때 머릿속으로만 구조를 그려내면 실수하기가 쉽다. 처음부터 연습장에 값의 변화나 최종 결과를 기록하고 머릿속에 떠올린 구조와 비교하면서 풀이해나가자. 2. 자신만의 코드 스니펫 준비 코딩테스트 시 자주 쓰이는 동작들에 대해 코드 스니펫을 미리 만들어 두면 도움이 된다. 예를 들어 연결리스트를 뒤집거나 삭제하는 등의 작업들은 갑자기 구현하려면 헷갈리기도 하고 시간이 걸리는데, 이런 작업에 대한 코드를 미리 만들어두면 좋다. 3. 모든 테스트 케이스를 통과하도록 풀어야 코딩 테스트 시에는 충분히 생각하고 문제가 없는지 코드를 다시 한번 더 꼼꼼히 확인 후에 제출하는 편이 유리하다. 실무에서처럼 일단 돌아가는 코드를 제출하고 테스트를 지속적으로 돌려보면서 오류를 수.. 2022. 9. 17.

이전 1 2 다음

티스토리툴바