Algorithm

BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하는 문제들을 통틀어 시뮬레이션 유형의 문제라고 한다. 시뮬레이션 유형의 문제들은 배경 지식보다는 구현력을 필요로 한다. 구현력을 가지고 빠르고 정확하게 풀어내는 것이 중요한 문제이다! 연습 문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있..

알고리즘 설명 백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 오목을 하면서 돌을 어디에 둘 지 생각할 때, 백트래킹을 사용하게 된다. 위처럼 생긴 트리를 상태 공간 트리라 한다. 출처: 바킹독님 블로그

알고리즘 설명 재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 절차 지향적인 사고를 탈피해야 한다! 함수 호출 과정을 하나하나 따라가는 대신 귀납적인 사고를 통해서 이해하도록 하자. 재귀 함수의 조건 특정 입력에 대해서는 반드시 자기 자신을 호출하지 않고 종료되어야 한다.(Base condition) 모든 입력은 Base condition으로 수렴해야 한다. 재귀에 대한 정보 함수의 인자로 무엇을 받고, 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다. 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다. 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만, 메모리와 시간에서는 손해를 본다. -> 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 ..

알고리즘 설명 DFS(Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 알고리즘 수행 과정 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다. 스택이 빌 때까지 2번을 반복한다. 모든 칸이 스택에 한 번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. 이전 BFS의 수행 과정과 비교해보았을 때, DFS는 스택을 쓴다는 차이만 존재한다. 큐를 쓰면 BFS이고, 스택을 쓰면 DFS가 된다. DFS와 BFS는 노드의 방문 순서에도 차이가 있다. B..

알고리즘 설명 BFS(Breadth First Search)는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 여기서 그래프는 정점과 간선으로 이루어진 자료구조를 말한다. BFS 과정 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행한다. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다. 큐가 빌 때까지 2번을 반복한다. 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N)이다. 만약 행이 R개이고 열이 C개이면 시간 복잡도는 O(RC)이..

수식의 괄호 쌍이란? 위 식은 계산이 가능한 올바른 식이지만, 아래 식은 괄호가 이상하게 배치되어 있다. 수식의 괄호 쌍이란 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 문제 해결을 위한 관찰 보편적인 방법으로는, 안쪽부터 짝 맞추기를 해서 괄호를 지워나가는 방법이다. 짝이 모두 맞으면 올바른 괄호 쌍이고, 그렇지 않으면 올바르지 않은 괄호 쌍이다. )의 개수가 (의 개수를 넘지 않아야 한다. 괄호가 여러 종류일 때에는 여는 괄호와 닫는 괄호의 개수만으로는 판단할 수 없다. 대신 짝이 되는 소괄호() 와 중괄호{} 를 지우는 방법은 여전히 잘 동작한다. 이 방법은 배열로 구현할 경우, 최대 N번 중간에 있는 원소의 삭제가 발생하기 때문에 O(N2)이고 연결리스트로 구현할 경우, O(N)이다. 스택을..

정의와 성질 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque이고 Double Ended Queue라는 뜻을 가지고 있다. 덱의 성질 원소 추가/제거의 시간 복잡도는 O(1)이다. 제일 앞/뒤 원소 확인의 시간 복잡도는 O(1)이다. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다. 그러나 STL deque에서는 인덱스로 원소에 접근할 수 있다. 기능과 구현 배열의 형태로 덱을 구현해 보았다! STL deque STL deque은 매우 독특하게 double ended queue보다는 vector와 느낌이 비슷한데, front에서도 O(1)에 데이터의 추가와 제거가 가능하다는 느낌이 강하다. insert, erase 함수가 있고 인덱스로 원소에 접근할 수도 있..

정의와 성질 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데, 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)라고 한 것과 비슷하게 큐를 FIFO(First In First Out)라고 하기도 한다. 큐의 성질 원소 추가/제거의 시간 복잡도는 O(1)이다. 제일 앞/뒤 원소 확인의 시간 복잡도는 O(1)이다. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 기능과 구현 배열 형태로 선형 큐를 구현해 보았다. STL queue 큐가 비어있을 때 front, back, pop을 호출하면 런타임 에러가 발생할 수 있으므로 주의해야 한다. 출처: 바킹독님 블로그