은학의 코딩 일기장

문제 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 입력 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다. 출력 2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라. 빗물이 전혀 고이지 않을 경우 0을 출력하여라. 풀이 시뮬레이션 문제이다. 특정위치를 기준으로 물이 고이는지를 판단하면 되기 때문에 for문을..

문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값..

정렬이란? - 자료들을 일정한 순서대로 나열한 것 -오름차순방식과 내림차순 방식이 있음 - 대표적인 예) 사전 정렬 알고리즘의 종류 -선택정렬 -삽입정렬 -퀵정렬 -병합정렬 -기수정렬 -히프정렬 -버블정렬 등등 정렬 알고리즘의 구현 1. 선택정렬 개념 : 여러 데이터중 가장 작은 값을 뽑는 동작을 반복하여 값을 정렬하는 방법 ex) 2. 삽입정렬 개념 : 기존의 데이터중에서 자신의 위치를 찾아 데이터를 삽입하여 정렬하는 방법 ex)

완전탐색 개념 완전탐색은 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 방법 '무식하게 푼다'의 의미인 Brute Force 라고도 부름 모든 경우의 수를 탐색하기에 정확성은 100%, 효율성은 꽝 따라서 주어진 N의 크기가 작을 때 사용하는 것이 좋음 '알고리즘' 이라기보다는 문제를 푸는 방법!! 완전탐색 풀이 방법 1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산 2. 가능한 모든 방법을 다 고려 3. 실제 답을 구할 수 있는지 적용 위의 2에서 말한 "모든 방법" 5가지 1. 단순 Brute Force 2. 순열 3. 재귀 호출 4. 비트마스크 5. BFS, DFS 단순 Brute Force 반복문, 조건문을 활용하여 단순하게 모든 방법을 찾는 방법 ex) 자물..

DFS의 기본 개념 BFS 알고리즘은 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘 BFS 구현 방식 BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색한다는 점에서, 선입선출 방식의 큐(Queue) 자료구조를 활용 BFS 동작 과정 1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다. 2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다. 3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 파이썬 구현

DFS 개념 (1) DFS의 기본 개념 DFS란 Depth first search의 약자로서 그래프 자료에서 데이터를 탐색하는 알고리즘 위에서 아래로 찾는 방식이 바로 DFS (2) DFS의 기본 원칙 DFS에서 데이터를 찾을 때는 항상 "앞으로 찾아야 가야할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색을 합니다. 이 원칙을 반드시 기억해주셔야 해요. 그래서 특정 노드가 "앞으로 찾아야 가야할 노드"라면 계속 검색을 하는 것이고, "이미 방문한 노드"면 무시하거나 따로 저장하면 됩니다. (3) DFS의 구현 방식 DFS를 구현할 때는 기본적으로 "스택/큐"를 활용할 수도 있고, "재귀함수를 통해 구현할 수도 있습니다. 스택 / 큐를 사용한 DFS 구현 (1) 리스트를 활용한 DFS 구현 여기서..

다이나믹 프로그래밍이란? 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식이 있다. 메모이제이션(Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다. 한 번 계산한 결과를 말 그대로 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도..

그리디 알고리즘 그리디 알고리즘은 Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다. 그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음) 그리디 알고리즘의 장점 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용..