곰탱이 성장

17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 단어 뒤집기 2 문제 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '

알고리즘 문제에서 자주 다뤄지는 DFS에 대해 알아보자. DFS란? DFS는 말 그대로 깊이 우선 탐색으로 인접한 노드부터 넓게 탐색하는 BFS와 달리 깊이를 우선으로 탐색하는 방법이다. 하나의 정점에서 시작하여 그 정점의 깊이까지 우선적으로 탐색하는 방법을 말한다. ❗️dfs 사용하는 경우: 모든 노드를 방문하고자 하는 경우 ex) 어떤 지점 a에서 b까지 이동하는 거리를 그래프로 표현한 후 a와 b사이에 존재하는 경로를 찾는 경우 > DFS - 일단 한 경로를 선택하여 끝까지 가보고 막혔다면 다시 이전 분기점으로 돌아와 탐색 > BFS - 시작점과 가까운 곳부터 '차례대로' 살펴보며 탐색 DFS 특징 1️⃣ DFS는 BFS보다 비교적 간단하다. 2️⃣ 단순 검색 속도 자체는 BFS에 비해 느리다. 3..

📝 목차 1. 도입 2. 문제: 도시락 데우기(문제 ID: LUNCHBOX, 난이도: 하) 3. 문제: 문자열 합치기(문제 ID: STRJOIN, 난이도: 중) 1. 도입 탐욕법(그리디)은 가장 직관적인 알고리즘이라고 할 수 있다. 재귀호출과 같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적계획법과 다를 것이 없다. 하지만 모든 선택지를 고려하고 그 중 전체 답이 가장 좋은 것을 고르는 방법과 달리, 탐욕법은 각 단계마다 지금 가장 좋은 방법만을 선택한다. 🏷 탐욕법 알고리즘 사용되는 경우 1️⃣ 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적계획법보다 수행 시간이 훨씬 빠르다. 📝 만약 탐욕법 알고리즘을 사용해 결과 ..

백준 문제를 풀다가 유니온 파인드라는 알고리즘을 고맙게도 알게 되었다. 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net Union-Find 두 노드가 서로 같은 그래프에 속하는 지 판단 Disjoint-Set / 서로소 집합 알고리즘이라고도 불린다. 주로 그래프 이론과 연결 요소 찾는 데 활용 Union-Find는 다음 두 연산을 지원한다. Find() : 특정 원소가 속한 집합을 찾는다. 즉, 어떤 원소가 어떤 집합에 속해 있는 지를 확인하는 연산 Union() : 두 ..

📝 목차 1. 도입 2. 문제: 와일드카드(문제 ID: WILDCARD, 난이도: 중) 3. 전통적 최적화 문제들 4. 문제: 합친 LIS(문제 ID: JLIS, 난이도: 하) 5. 문제: 원주율 외우기(문제 ID: PI, 난이도: 하) 6. 문제: Quantization(문제 ID: QUANTIZE, 난이도: 중) 7. 경우의 수와 확률 8. 문제: 비대칭 타일링(문제 ID: ASYMTILING, 난이도: 하) 9. 문제: 폴리오미노(문제 ID: POLY, 난이도: 중) 10. 문제: 두니발 박사의 탈옥(문제 ID: NUMB3RS, 난이도: 중) 1. 도입 먼저 동적 계획법(dynamic programming)은 '동적(dynamic)'과 '프로그래밍(programming)이란 단어와는 아무런 관계가 ..

더보기 📝 목차 1. 도입 2. 문제: 쿼드 트리 뒤집기 3. 문제: 울타리 잘라내기 4. 문제: 팬미팅 1. 도입 분할 정복은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 설명할 수 있다. ✏️ 분할정복과 일반적인 재귀호출과의 차이점 재귀호출: 항상 문제를 한 조각과 나머지로 쪼갠다. 분할 정복: 항상 문제를 절반씩으로 나눈다. ✏️ 분할정복의 세가지 구성 요소 문제를 더 작은 문제로 분할하는 과정(divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) ✏️ 분할 정복의 필요조건 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다. 부분 문제의 답을 조..

더보기 ❗️이 글은 구종만 - 알고리즘 문제해결 전략 책을 참고하여 작성되었습니다. 📝 목차 1. 재귀 호출과 완전 탐색 2. 문제: 소풍 3. 문제: 게임판 덮기 4. 최적화 문제 5. 문제: 시계 맞추기 6. 많이 등장하는 완전 탐색 유형 알고리즘을 고안하기 위해서는 문제의 특성을 이해하고, 동작 시간과 사용하는 공간 사이의 상충 관계를 이해하여, 적절한 자료구조를 선택할 줄 알아야 한다. 알고리즘 설계 패러다임: 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점 알고리즘 문제를 풀면서 "어떻게 하면 무식하게 풀 수 있을까"에 대해 생각하는 것이 실수를 방지하는데 좋다. "무식하게 풀기"는 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법으로 "완전 탐색"이라고 한다. 1. 재귀 호출과 ..

더보기 ❗️이 글은 구종만 - 알고리즘 문제해결 전략 책을 참고하여 작성되었습니다. 해결해야하는 간단한 알고리즘은 직관적으로 문제를 해결할 수 있지만, 문제가 복잡해지면 알고리즘이 이 문제를 제대로 해결하는지 확인하기 어렵다. 알고리즘의 정확한 증명을 하기 위해 각종 수학적인 기법이 동원되어야 한다. 알고리즘의 증명은 알고리즘의 유도 과정에 대한 통찰을 담고 있다. 그렇기 때문에 증명을 제대로 이해해야 알고리즘을 제대로 공부했다고 할 수 있다. 📝 목차 1. 수학적 귀납법과 반복문 불변식 2. 귀류법 3. 다른 기술들 1. 수학적 귀납법과 반복문 불변식 📍 수학적 귀납법 예를 들어 100개의 도미노가 순서대로 놓여있다고 해보자. 그리고 우리가 다음 두 가지 사실은 안다고 가정해보자. 첫번째 도미노는 직접..