공작소

도입 이 글은 모든 경우의 수를 찾는 상황에서 사용할 수 있는 백트래킹 (Backtracking) 에 대한 개념 설명을 담고 있습니다. 재귀를 배운 이후에 같이 배우면 좋은 이 백트래킹 알고리즘은 브루트포스와는 다르게, 여러 경우의 수를 조건에 맞게끔 깊게 구해낼 수 있습니다. 재귀를 사용하므로 코드도 간단하게 작성할 수 있어서, 익히게 된다면 재밌게 문제를 해결할 수 있다고 생각합니다. 입력 제한이 큰 경우에는 시간복잡도가 지수적으로 증가하는 백트래킹보다 그리디나 DP를 사용하는 것이 효율적이겠지만, 백트래킹만이 빠르게 문제 상황을 해결할 수 있는 상황도 존재합니다. 백트래킹의 기본 원리를 익히고 예제 문제와 함께 이해하는 것이 이 글의 목표입니다. 본 글은 C를 기반으로 작성되었습니다. 다음 알고리즘..

도입 이 글은 재귀 알고리즘에 대한 설명을 담고 있습니다. 프로그래밍 언어를 공부하다보면, 함수 혹은 메소드에 대해 배우면서 접할 수 있는 알고리즘이 바로 재귀입니다. 사실 재귀는 반복문을 실행하는 것보다 메모리 측면에서 비효율적이라는 의견도 존재하지만 (함수를 종료시키지 않은 채로 계속 실행하기에) 잘 사용하면 문제를 다른 시선으로 바라볼 수 있으며, 복잡한 문제 상황을 간결한 코드로 해결할 수도 있는 알고리즘입니다. 재귀 알고리즘을 학습하고 여러 문제 상황에 대응할 수 있는 능력을 기르는 것이 이 글의 목적입니다. 본 글은 C를 기반으로 작성되었습니다. 접근 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로..

도입 이 글은 그래프 탐색에서 사용할 수 있는 깊이 우선 탐색 (DFS, Depth-First Search) 과 너비 우선 탐색 (BFS, Breadth-First Search) 에 대한 개념 설명을 담고 있습니다. 개인적으로 자료 구조 분야에서 스택 및 큐 개념을 배운 이후 중간 단계를 건너뛰고 바로 DFS와 BFS를 배우면서 PS에 입문한 사람으로써, DFS와 BFS는 실버 시절 제가 많은 실버 문제와 골드 문제를 풀 수 있도록 도와준 알고리즘입니다. 그래프 탐색이라고 해서 단순 그래프 측면이 아닌 다양한 방식으로 응용이 가능한 알고리즘이기에, 익힌다면 여러 분야에서 실전적으로 활용할 수 있을 것입니다. DFS와 BFS의 기본적인 개념을 응용 방식과 함께 배우고 풀이하는 것이 이 글의 목적입니다. 본..

도입 이 글은 자료구조에서 스택 다음으로 배우게 되는 큐에 대한 개념을 담고 있습니다. 스택과 유사하지만 다른 특징을 가지고 있으며, 큐 자료 구조에 대한 기반을 다져 놓으면 실전적으로 활용이 가능합니다. 큐는 다른 수많은 알고리즘 (BFS, 위상 정렬, 데이크스트라 등등) 을 배우는 데에 있어서 필수적인 기초가 되는 알고리즘이기 때문에, 큐의 개념을 이해하고 여러 문제에 활용하며 풀이한 뒤, 추후 적극적으로 응용이 가능하도록 능력을 기르는 것이 이 글의 목적입니다. 본 글은 C를 기반으로 작성되었습니다. 스택 자료 구조를 먼저 공부한 이후 큐를 공부하는 것을 추천드립니다. https://readytojoin.tistory.com/35 스택 (Stack) 스택 (Stack) 은 한 쪽 끝에서만 데이터를 ..

도입 세그먼트 트리 이후 작성하는 알고리즘 튜토리얼 글입니다. 이 글은 세그먼트 트리의 응용 방식 중 하나인 Lazy Propagation in Segment Tree ( 느리게 갱신되는 세그먼트 트리 ) 에 대한 원리 및 응용 방식을 다루고 있으며, 이 글을 읽은 후 느리게 갱신되는 세그먼트 트리를 이용하여 여러 문제를 풀 수 있도록 하는 것이 이 글의 목적입니다. Lazy 값을 이용한 느린 전파 테크닉을 이해하여 추후 더 나아가 Segment Tree Beats 등을 배우면서 어려운 구간 쿼리를 해결하는 능력을 기를 수 있을 것입니다. 본 글은 C를 기반으로 작성되었습니다. 세그먼트 트리에 대한 이해가 필요합니다! https://readytojoin.tistory.com/57 [ Algorithm ]..

도입 이 글은 세그먼트 트리를 처음 접하거나, 세그먼트 트리의 기초적인 응용에 대한 solution idea를 얻고 싶은 분들을 위하여 제가 세그먼트 트리 태그를 풀면서 정립한 세그먼트 트리 개념을 설명하는 글입니다. 이 글을 읽은 뒤 세그먼트 트리의 기본적인 사용법을 익히고 기초 응용 문제를 풀 수 있도록 하는 것이 이 글의 목적입니다. 기초적인 응용 이후에 세그먼트 트리에 관련한 여러 응용 문제를 직접 풀어본다면, 세그먼트 트리를 깊이 이해하며 트리 구조를 변형할 수 있는 능력을 기름과 동시에 추후 Lazy Propagation with Segment Tree, Persistent Segment Tree 등의 알고리즘에 대한 배경 지식을 얻을 수 있을 것입니다. 본 글은 C를 기반으로 작성되었습니다...

도입 이 글은 자료구조에서 가장 초반에 배우는 스택에 대한 개념을 담고 있습니다. 자료구조에 해당한다고 해서 겁먹을 필요 없이, 순서에 따라 차근차근 원리를 이해하면 쉬운 난이도를 가지고 있으니 걱정하지 않아도 됩니다. 스택의 개념을 이해하고 여러 문제에 활용하며 풀이한 뒤, 추후 적극적으로 응용이 가능하도록 능력을 기르는 것이 이 글의 목적입니다. 본 글은 C를 기반으로 작성되었습니다. 접근 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc..