싱이의 devlog

1. 알고리즘 설명 투포인터 알고리즘이란? 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)으로 해결하는 알고리즘 보통 이중 for문을 돈다면 시간복잡도는 O(N^2)가 될 것임. 이 과정에서 i=0일때 계산하면서 얻은 정보는 i=1일때 사용이 되지 않음. 하지만 투 포인터를 활용한다면 i=0일때 계산하면서 얻은 정보를 i=1일 때 활용할 수 있음! 그리고 그 정보는 바로 포인터의 이동으로 나타남. 여기서 포인터라는 건 C에서 흔히 말하는 포인터는 아니고, 커서의 개념과 동일함! 투포인터 문제 ⇋ 이분 탐색 문제 투포인터 문제의 경우 이분 탐색으로 풀 수 있는 경우가 많음. 반대로 이분 탐색 문제 역시 투포인터 문제 유형으로 바꿔 풀 수 있는 경우가 많음. ..

1. 문제 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 2. 풀이 처음 풀이는 단순하게 for문 2개를 활용하는 방법이였지만, 역시나 시간복잡도가 너무 커서 틀렸었다. (당시 시간복잡도는 O(N^2)) for (int i = 0; i m && diff < minDif) diff = minDif..

1. 알고리즘 설명 이분탐색이란? 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가면 찾는 탐색 방법 ex) 정수 10개로 이뤄진 정렬된 배열에서 선형 탐색의 경우 탐색 시 앞에서부터 순차적으로 탐색을 하게 됨. 그렇게 한다면 시간복잡도는 O(N). 하지만 이분탐색의 경우 배열을 반절로 나눠가면서 효율적으로 탐색하여 시간복잡도를 O(log N)으로 줄일 수 있음! 2. 구현 및 STL 📌 이분탐색 문제 유형의 경우 간단한 문제들은 STL에 존재하는 함수들을 이용해 구현할 게 별로 없지만, 살짝만 복잡해져도 난이도가 훨씬 올라가게 됨. 따라서 코테 공부 초보 단계일 경우 개념과 STL 사용법을 위주로 공부하고 다른 주요 강의들에 집중하는 것..

1. 알고리즘 설명 그리디 알고리즘(Greedy Algorithm)이란? 현재 가장 최적인 답을 근시안적으로 택하는 알고리즘 관찰을 통해 탐색 범위를 줄이는 알고리즘 예시로는 0x0E강-정렬1에서 언급된 예시가 있음! 정렬된 두 배열을 하나의 배열로 합칠 때, 기본 정렬(삽입, 선택, 버블)이 O((N+M)^2)을 걸려서 했던 일을 O(N+M)에 수행할 수 있었음. 즉, 관찰을 통해 탐색 범위를 줄였고 시간을 줄였기 때문에 그리디 알고리즘의 예시라고 할 수 있음. 풀이 흐름 이상적인 풀이 흐름 1) 관찰을 통해 탐색 범위를 줄이는 방법을 고안함 2) 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명함 3) 구현하여 문제를 통과! ...이지만 코테에서 현실적인 풀이 흐름을 보자면 1) 관찰을..

1. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 2. 논리 방식 해당 문제에서 회의 스케쥴을 표현하면 아래와 같다. 가장 최적의 경우로 회의실을 배정하는 과정을 생각해보았을 때, 아래와 같은 조건들을 만족시켜야 한다. 1) 선택한 회의 시간의 시작 시간 >= 직전에 시행된 회의가 끝나는 시간 선택한 회의 시간의 시작 시간과 직전에 시행된 회의가 끝나는 시간이 동일해도 상관없다는 걸 유의한다. 2) 가능한 회의들 중 소요 시간이 가장 짧은 회의. 즉, 회의가 끝나는 시간이 제일 빠른 것을 고른다. 결론적으로 이 문제의 핵심은 바로 회의 종료 시간에 있..

1. 알고리즘 설명 DFS(Depth First Search) 정의 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 2. 예시 DFS 과정 1) 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2) 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 3) 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4) 스택이 빌 때까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N) BFS에서 큐를 스택으로 바꾸면 DFS가 됨!스택을 활용하면 2)에서 상하좌우로 한 번 훑은 뒤에 스택에 추가된 가자 최근의 원소가 pop 되고, pop 된 원소를 기준으로 또 상하좌..

1. 알고리즘 설명 BFS(Breadth First Search. 너비 우선 탐색) 그래프에서 모든 노드를 방문하기 위한 알고리즘. 그래프는 정점과 간선으로 이뤄져있음. 하지만 우린 여기서 다차원 배열로 BFS를 이해하고 활용할 예정! 2. 예시 초기 세팅에서 BFS는 좌표를 담을 큐가 필요함. BFS 알고리즘이 시작되면 우선 (0,0)을 방문했다는 표시를 남기고 해당 칸을 큐에 넣음. BFS 과정 1) 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2) 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3) 해당 칸을 이전에 방문했을 시 아무 것도 하지 않고, 처음으로 방문했을 시 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 4) 큐가 빌 때까지 2번 반복 참고로 BFS의 시간..

1. 수식의 괄호 쌍이란? 스택은 여러 문제 유형에서 활용이 됨. 대표적으로 수식의 괄호 쌍, 전위/중위/후위 표기법, DFS(깊이 우선 탐색), Flood Fill이 있음. 이 중 전위/중위/후위 표기법은 코테에서는 너무 지엽적인 부분이므로 해당 강의에서는 다루지 않을 예정! 수식의 괄호 쌍의 정의 주어진 괄호 문자열이 올바르게 매치가 되는 지 판단하는 문제. 2. 문제 해결을 위한 관찰 '올바르게 매칭'를 한다는 것은 각 괄호가 짝이 맞을 때를 의미함. 하지만 하나의 괄호만 사용이 된다면 단순히 여는 괄호의 갯수 = 닫는 괄호 갯수이면 되겠지만, 여러 종류의 괄호가 사용이 된다면 닫힌 괄호가 들어왔을 때 가장 최근에 들어온 여는 괄호와 종류가 같아야 한다는 조건을 붙여야 함. 정리하자면! 문자열을 앞..

1. 정의와 성질 정의 양쪽 끝에서만 삽입과 삭제가 전부 가능한 자료구조. Restricted Structure의 끝판왕! *참고로 스택과 큐를 덱의 특수한 예시라고 생각해도 무관함. 성질 1) 원소 추가 시간복잡도 O(1)2) 원소 제거 시간복잡도 O(1)3) 제일 앞/뒤의 원소 확인이 O(1)4) 제일 앞/뒤가 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능....하지만! STL deque는 stack, queue와 달리 인덱스로 특정 원소로 접근할 수 있음. 구체적인 활용 사례는 마지막에서 볼 수 있겠지만, stack과 queue에서는 구현을 하지 않았던 것을 생각하면 꽤 독특한 일:) 2. 기능과 구현 직접 구현 덱도 역시 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 통..

1. 정의와 성질 정의 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조. 먼저 들어간 원소가 먼저 나옴!(FIFO) 성질 1) 원소의 추가 시간복잡도는 O(1) 2) 원소의 제거 시간복잡도는 O(1) 3) 제일 앞/뒤의 원소 확인이 O(1) 4) 제일 앞/뒤가 아닌 나머지 원소들의 확인 및 변경은 원칙적으로 불가능함! 2. 기능과 구현 직접 구현 큐도 스택처럼 배열 혹은 연결 리스트 둘 중 어느 것을 이용해서 구현 하는데 문제가 없지만 배열이 훨씬 쉽기 때문에 배열로 가보는 걸로! 배열에서 제일 위에 있는 원소를 가리키는 pos 변수가 1개 있었던 스택과 다르게, 큐에서는 앞쪽을 가리키는 head와 맨 뒷쪽을 가리키는 tail이 존재해 총 2개의 변수가 활용됨. 배열로 구현하는 과정에..