싱이의 devlog

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

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. 알고리즘 설명 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개의 변수가 활용됨. 배열로 구현하는 과정에..

1. 정의와 성질 정의 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조. 구조적으로 먼저 들어간 원소가 제일 나중에 나오는 구조(FILO) 🎯 참고로 스택, 큐, 덱은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 있으며 이들은 묶어 Restricted Structure이라고 함! 성질 - 원소의 추가/제거/상단 원소 확인 및 변경 1) 원소의 추가 시간복잡도는 O(1) 2) 원소의 제거 시간복잡도는 O(1) 3) 제일 상단의 원소 확인 시간복잡도는 O(1) 4) 제일 상단이 아닌 나머지 원소들의 확인 및 변경은 원칙적으로 불가능함! 물론 스택을 구현할 때 가장 상단이 아닌 나머지 원소들을 확인하거나 변경할 수도 있겠지만, 애초에 스택은 그런 의미로 만들어진 것이 아님! 실제 스택의 용례를 보아도 ..

1. 정의와 성질 연결리스트란? 원소들을 저장할 때 그 다음 원소가 있는 위치 정보까지 포함시키는 방식으로 데이터를 저장하는 자료구조 연결리스트 성질 k번째 원소를 확인/변경하기 위한 시간복잡도는 O(k) 3 --- 73 ---- 88 로 연결된 연결리스트에서 3번째 원소 88을 찾고 확인하고 싶다면 3을 거치고 73을 거쳐 쭉 가야하므로 시간복잡도가 O(3)임을 알 수 있음 임의의 위치에 원소를 추가하거나 제거하는 데 시간복잡도는 O(1) 메모리 상에 원소들이 불연속적으로 배치되어 있어 Cache hit rate이 낮지만 할당은 쉬움 연결리스트 종류 참고로 STL에서 제공하는 연결 리스트 컨테이너 list에서 구현하는 연결 리스트는 이중 연결 리스트임! 그리고 세 번째 원형 연결 리스트에서 그림은 단일..