싱이의 devlog

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의 시간..

해결법 얘기 전 조금의 주절주절. 알고리즘 공부를 하면서 C++ 코드를 짜기 위해 Visual Studio 2022를 설치했다. 원래 쓰던 프로그램은 2010 버전이었기 때문에 (..) 알고리즘 공부하는 참에 업데이트를 해보자!는 의미에서 2022 버전으로 갈아탔다. 코드를 짜던 도중 Visual Studio에서 #include 를 입력했을 때 오류가 나는 것을 발견하였다. 처음 헤더 파일 선언부터 빨간 줄이 떠서 '이게 뭐야..' 싶었지만, Visual Studio 자체 특성 때문에 생기는 오류라는 것을 발견했다. 문제 원인 라는 헤더 파일에는 우리가 자주 쓰는 헤더파일들이 모두 include 되어있다. 이는 gcc 계열의 컴파일러에는 추가가 되어있지만, Visual Studio의 경우 msvc 컴파일..

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에서 구현하는 연결 리스트는 이중 연결 리스트임! 그리고 세 번째 원형 연결 리스트에서 그림은 단일..