Doby's Lab

이번 문제는 sort함수를 이용하며 compare에 더 깊게 파고들었다. sort 할 때 compare 함수를 다음 코드로 짜서 컴파일했지만 계속 어디서 나는지도 모를 오류 Invalid Comparator가 발생한다. (Comparator라서 비교 함수 쪽에 문제가 있구나는 인식할 수 있었다.) bool cmp(string a, string b) { if (a.size() = 0) { sumA += a[i]; } if (b[i] = 0) { sumB += b..

이번 문제는 50점과 100점으로 나뉘어 채점을 하게 되며 계속해도 100점이 나오지를 않았다. 해싱의 개념과 Mod의 연산을 알아보며 풀어보자. 개념 해싱(Hashing)이란 데이터를 관리하는 비법으로 이분 탐색 혹은 다른 탐색보다 시간 복잡도를 O(1) 안에서 해결할 수 있다. 어떠한 데이터를 저장하려 할 때 그 데이터를 보관하는 곳을 해시 테이블(Hash Table)이라고 한다. 그리고 각 버킷(bucket, 각 행)이 고유한 주소를 가지게 되는데 데이터를 해시 함수(Hash Function)를 통해 데이터를 주소 값으로 바꾸어서 해시 테이블에 저장한다. 각 버킷에 얼마큼 저장할 수 있는 지를 알 수 있는 곳이 슬롯(slot, 각 열)이다. 한 슬롯에 계속 데이터가 들어오면 이를 충돌(Hash Co..

드디어 백준 골드를 찍었다. 골드를 찍으면 블로그에다가 골드를 찍기까지 과정이나 이렇게 하면 좋을 거 같다는 생각들을 정리해두고 싶었다. 대단한 건 아니다. 말 그대로 대단한 게 아니다. 골드가 되었지만 내 실력은 골드가 아니라고 생각한다. 아직 그래프 이론, 해싱, 그리디 알고리즘 등 다른 기초 알고리즘은 건들지도 않았었다. 이분 탐색, 백트래킹 조금, Monotonic Stack 조금 이 종류들만 깊게 풀었었는데 골드에 금방 왔다. 이제 골드가 되었으니 다른 알고리즘들도 개념 공부하고, 문제로 깊게 들어가 보면서 백준을 풀어나가야 할 거 같다. 티어가 서열 척도가 될 수는 없다. 위에서 말한 거처럼 한 알고리즘을 깊게 파서 티어가 높아지는 경우가 있다. 이럴 경우 장점도 있지만 다른 알고리즘들을 모른..

이번 문제는 꽤나 건들기 싫었던 문제였다. 빡구현의 기미가 풀기 전부터 계속 느껴졌었다. 그래도 CLASS 2가 3문제 남은 시점에서 빨리 졸업하자라는 생각으로 문제에 임했다. 개념 이번 문제는 브루트 포스(Brute-Force) 알고리즘을 사용했다. 브루트 포스란 완전 탐색의 의미를 가지고 '모든 경우의 수를 다 확인해보자'라는 뜻이다. 'for문을 몇 개를 쓰거나 복잡해지든 말든 일단 모든 경우를 다 탐색해보자' 같은 주관적 느낌도 생겼다. 그렇다고 해서 브루트 포스가 무식한(?) 느낌의 알고리즘은 아니다. 오히려 컴퓨터의 장점(단시간 안에 수억 개의 연산을 처리한다는 점)을 잘 살리는 알고리즘이다. (책에서 그랬다..ㅎ) 고생했던 포인트 1. 8x8 사이즈의 체스판을 선언해둬야 했었다. 처음에는 문..

이번 문제가 어려웠던 이유는 무엇을 이분 탐색해야 하는지도 정확히 파악하고 있고, 논리까지 짰었지만 센스(?)가 없어서 풀지 못하던 문제이다. (알고리즘은 이분 탐색을 사용했기에 이분 탐색 카테고리에 넣어둔다.) 우선 블루레이의 크기를 탐색하기 때문에 1을 low로 두고, 모든 강의 길이의 합을 high로 두고, 나오게 된 mid에 맞춰서 sum변수를 선언하고, 강의의 길이를 하나씩 더해가며 sum이 mid를 넘을 때마다 블루레이 하나 더 써야겠다 라는 논리로 접근하면 된다. 이번 문제에서 해결하지 못하는 포인트가 2가지였다. sum이 mid를 넘어갈 때, sum을 0으로 초기화해버리면 넘어갈 때 순간의 원소(강의의 길이)는 어떻게 해결하나 mid로써 주어진 길이가 7이라고 치면 한 강의의 길이가 8일 ..

(이번 문제는 첫 골드 문제이다 (울컥)) 이번 문제의 유형이 'Monotonic Stack'이라고 하는데 이 유형의 문제를 처음 접한 것은 아니다. 예전 SCPC 준비를 할 때, 같이 준비하던 친구들과 영어 문제를 풀면서 접했었던 경험이 있다. 많은 시간을 썼었지만 풀리지 않았었고, 해답을 찾다가 Monotonic Stack에 대한 자료가 많이 없어서 나중에 또 이런 유형을 만나게 되면 정리를 해둬야겠다고 생각했었다. (해당 영어문제 링크) https://www.acmicpc.net/problem/6105 6105번: Look Up Farmer John's N (1 a; arr.push_back(a); } vector answer(n, 0); stack s; for (int i = arr.size() ..

(추가 내용 2021.11.15) https://draw-code-boy.tistory.com/96 [알고리즘] 백준 6443번: 애너그램 (C++), 백트래킹 중복 처리 유형 2번째! https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램 draw-code-boy.tistory.com 비슷한 문제가 나와서 정리해두었다. 백트래킹의 코드 구조를 익히면서 [N과 M 시리즈]를 풀고 있었다. 이번 문제에서 막히게 되었는데 해당 문제에서 이런 걸 요구했기 때문이다. 'N이 4이고, M이 2일 때, 9 7 9 1의 수들로 부분 수..

(N과 M (1) 문제를 중심으로 설명하려 했으나 Backtracking과 DFS의 차이를 설명하기 위해 N과 M (2) 문제가 적합하다는 생각이 들었다.) 개념 백트래킹은 DFS를 응용하여 나온 알고리즘 같았다. DFS에 대해서는 그래프 이론에 대한 문제를 풀기 시작할 때 제대로 다시 다루겠지만 간단히 정리하면 어떠한 그래프가 주어졌을 때, 시작 노드로부터 연결돼있는 모든 노드를 탐색해나가는 완전 탐색 알고리즘이다. 또한 노드끼리 연결되었는가도 따져보아야 하는데 다음에 다시 다루겠다. 이러한 그래프가 있다고 가정하자. 시작 노드가 1일 때, DFS는 모든 노드들을 다음과 같이 탐색해나간다. 백트래킹은 DFS에 어떠한 조건을 주어서 (조건이라고 해서 무조건 if문을 사용하지 않는다.) 원하는 부분만 탐색..