개발자공부일기

https://www.acmicpc.net/problem/1717기본적인 유니온 파인드를 사용해서 푸는 문제입니다. 첫째줄에 n,m이 주어지고 n개의 원소의 집합이 있으며 m개의 줄만큼 명령이 주어집니다.0 a b는 union을 1 a b는 두 수가 같은 집합에 속하는지 판별하는것을 의미합니다.우리는 vector로 "arr[n] = 대표 노드" 이렇게 표현할겁니다. 초기 상태모든 노드가 자기 자신을 대표 노드로 가집니다.즉, arr[i] = i 입니다.12345671234567집합 상태: {1}, {2}, {3}, {4}, {5}, {6}, {7}1단계: 0 1 3 (union(1,3))1의 루트 = 1, 3의 루트 = 3 → 3을 1의 대표로 연결.12345671214567집합 상태: {1,3}, ..

유니온 파인드(Union-Find) 알고리즘은 여러 원소들을 몇 개의 그룹(집합)으로 나누고, 다음 두 연산을 빠르게 수행하는 데 목적이 있는 서로소 집합(Disjoint Set Union, DSU)을 효율적으로 관리하기 위한 자료구조이자 알고리즘입니다.핵심 연산Find(찾기)어떤 원소가 속한 집합(대표자, 루트 노드)을 찾는 연산.보통 트리 구조로 구현되고, 루트 노드가 그 집합의 대표자가 됩니다.경로 압축(Path Compression) 기법을 쓰면 시간 복잡도를 크게 줄일 수 있습니다.Union(합치기)두 원소가 속한 집합을 하나로 합치는 연산.두 집합의 대표자를 찾아서 하나로 연결해 줍니다.보통 "랭크(rank) 기반 합치기" 또는 "사이즈 기반 합치기"를 사용해서 트리가 한쪽으로 치우치지 않게 ..

https://www.acmicpc.net/problem/2251 세 개의 물통 A, B, C가 있다. A, B, C 물통의 용량이 주어지고, 처음에는 C 물통에만 물이 가득 차 있다.이때 A 물통이 비어 있을 때, C 물통에 담겨 있을 수 있는 물의 양을 모두 구하는 문제다. 물이 다양하게 담겨있는 여러가지 경우의 수 를 따지는 BFS(너비 우선 탐색) 방법을 이용하는 문제다.핵심 아이디어상태 표현(A, B, C) 세 물통에 들어 있는 물의 양으로 상태를 표현한다.하지만 세 개 다 저장할 필요는 없다.왜냐하면 C = 전체 물의 양 - (A+B)로 항상 계산할 수 있기 때문이다.따라서 (A, B) 두 값만 저장하면 충분하다.상태 전이(물 붓기)물을 옮기는 경우의 수는 6가지다.A→B, A→C, B→A, ..

백준 https://www.acmicpc.net/problem/1934를 유클리드 호제법으로 풀던 와중 코드를 잘 썼다고 생각했는데 정상작동하지 않았습니다.그래서 유클리드 호제법에 대해 다시 정리하며 제가 실수한 부분을 다시 살펴보려 합니다. 두 정수 a, b의 최소공배수(LCM)를 구하려면 보통 최대공약수(GCD)를 먼저 구한 뒤LCM(a, b) = a × b / GCD(a, b) 공식을 씁니다.이때 핵심이 되는 게 유클리드 호제법이고, 재귀식은 다음 한 줄로 요약됩니다.gcd(a, b) → gcd(b, a % b) 유클리드 호제법의 이론1.큰 수를 작은 수로 나누는 MOD 연산을 수행한다.2.앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD연산을 수행한다.3.2를 반복하며 MOD연산의 결과가 0..

에라토스테네스의 체란?에라토스테네스의 채(Sieve of Eratosthenes)는 소수 판별 알고리즘이다.특정 범위(예: 1 ~ N) 안에 존재하는 모든 소수를 효율적으로 찾기 위해 고안되었다.핵심 아이디어는어떤 수가 소수라면, 그 수의 배수들은 모두 소수가 아니다.따라서 소수를 하나씩 찾으면서, 그 소수의 배수를 지워 나가면 된다.1.알고리즘 흐름2부터 N까지를 모두 후보로 둔다.아직 지워지지 않은 가장 작은 수 p를 찾는다. p는 소수다.p의 배수들을 지운다. (보통 p*p부터 지운다)p를 다음 수로 옮기며, p ≤ √N일 동안 반복한다.남은 수가 모두 소수다.2. 동작 과정예를 들어 N = 30 까지의 소수를 구한다고 하자.초기화2부터 30까지 모든 수를 후보로 둔다. (1은 소수가 아니므로 제외..

stringstream으로 C++에서 문자열 다루기개발하다 보면 문자열을 숫자로 바꾸거나, 공백 또는 구분자를 기준으로 잘라야 할 일이 있습니다.전화번호 "010-1234-5678"를 쪼개거나 "5000"이라는 문자열을 숫자 5000으로 바꾸는 작업이 그 예입니다.이때마다 복잡한 루프나 substr()을 쓰기보다는, C++의 stringstream라는 친구가 있습니다.stringstream이란?C++ 표준 라이브러리 에 포함된 stringstream은 문자열을 cin처럼 다룰 수 있게 해주는 클래스입니다.즉, 문자열을 스트림에 싣고, 그 안에서 >>, cin: 키보드 입력을 받는 스트림stringstream: 문자열을 입력처럼 다루는 스트림기본 사용법1. >> 연산자 – 공백 기준으로 문자열 자르기str..

auto란 무엇인가?auto는 C++11부터 도입된 타입 추론 키워드입니다. 즉, 변수 선언 시 개발자가 자료형을 직접 쓰지 않아도 컴파일러가 자동으로 판단하여 변수 타입을 정해줍니다.예전에는 반복자를 다음과 같이 선언해야 했습니다.std::vector::iterator it = vec.begin();하지만 auto를 사용하면 아래처럼 훨씬 간단하게 쓸 수 있습니다.auto it = vec.begin();auto의 주요 특징복잡한 타입도 자동 처리: 반복자, 람다, map, pair 등에서 유용코드 가독성 향상: 자료형 생략으로 깔끔한 코드 작성 가능유지보수에 유리: 자료형이 바뀌어도 변수 선언을 바꿀 필요가 없음rbegin()과 rend()란 무엇인가?STL 컨테이너에서는 일반적으로 begin()과 e..

DFS (Depth-First Search)1. DFS란?DFS는 깊이 우선 탐색이라 하며, 한 정점에서 시작해 갈 수 있는 한 깊이 들어갔다가, 더 이상 갈 수 없으면 이전 지점으로 되돌아오는(backtracking) 방식의 그래프 탐색 알고리즘이다.스택(Stack) 자료구조를 사용하거나, 재귀 호출을 통해 시스템 호출 스택을 활용한다.2. DFS의 원리시작 정점을 방문하고 방문 표시를 한다.현재 정점에서 갈 수 있는 이웃 정점 중 아직 방문하지 않은 정점을 하나 선택해 이동한다.이동한 정점에서 1~2 과정을 반복한다.더 이상 방문할 이웃이 없으면 이전 정점으로 되돌아가 다른 경로를 탐색한다.모든 정점을 방문할 때까지 반복한다.3. 반복형 DFS 코드vector dfs_iter(int start, co..