1. 알고리즘 설명 다이나믹 프로그래밍(Dynamic Programming, DP) - 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘이다. dp를 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 2. 연습 문제 BOJ 1463번: 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 테이블 정의하기 d[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 d[12] = ? 3으로 나누거나 (d[12] = d..

1. 알고리즘 설명 시뮬레이션 - BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하면 되는데 이 때 구현이 빡세게 필요한 것들을 통틀어서 시뮬레이션 유형의 문제라고 한다. 2. 연습 문제 1 - 감시 BOJ 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. 각 cctv 방향 정하기 2. 정한 방향에 대해 사각 지대의 크기 구하기 두 가지로 나눠서 생각하면 된다. cctv의 방향을 정할 때는 4종류의 방향에 대해 4진법을 사용한다. 나머..

1. 알고리즘 설명 DFS - 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 2. 예시 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4. 스택가 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N). 사실상 BFS에서 큐가 스택으로 바뀐 것이다. 큐 - BFS 스택 - DFS DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다. BFS와 DFS는 방문 결과는 똑같지만 방문 순서에서 큰 차이가 있다. DFS 구현..

1. 알고리즘 설명 Flood Fill - 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 것 구현 방법 - BFS BFS - 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 2. 예시 우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하면 된다. 큐가 빈 순간 과정은 종료되고 (0, 0)과 상하좌우로 이어진 모든 같은 영역의 칸을 잘 방문했음을 알 수 있다. 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그..

1. 수식의 괄호 쌍이란? 수식의 괄호 쌍 - 말 그대로 수식의 괄호 쌍을 의미하며 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 2. 문제 해결을 위한 관찰 괄호 문자열이 올바른지 아닌지 판단하는 방법 중 가장 보편적인 방법은 바로 안쪽부터 짝맞추기를 해서 지워나가는 방법이다. 다 짝이 맞으면 올바른 괄호 쌍인거고 그렇지 않으면 올바르지 않은 괄호 쌍입니다. +) ) 의 갯수가 ( 의 갯수를 넘지 않으면 된다. 그런데 괄호가 여러 종류일 때에는 여는 괄호의 갯수와 닫는 괄호의 갯수 만으로는 해결이 되지 않는다. 예를 들어 ({}), ({)}라는 두 괄호 문자열을 생각해보면 첫 번째는 올바르고 두 번째는 올바르지 않다. 그런데 둘 다 ) 의 갯수가 ( 을 넘은 적도 없고, } 의 갯수가 { 을 넘은 ..

1. 정의와 성질 덱 - 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가진다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로 스택과 큐를 덱의 특수한 경우이다. 덱의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL st..