lastnamesong

그리디 알고리즘 (Greedy Algorithm)프로그래밍에서 어떤 선택이 “지금 가장 좋아 보이는 것”이라고 해서 최선의 해가 되는 것은 아니다. 하지만, 그런 탐욕스러운 선택이 오히려 정답으로 이어지는 경우가 있다. 이러한 전략을lastnamesong.tistory.com이전 글에서도 얘기는 했지만 그리디 알고리즘을 이해하는 것의 종착지는 "이 문제를 그리디로 풀 수 있는가?"를 판단하는 능력인 것 같다.그리디 관련 문제 중 하나로 백준 온라인 저지의 1931번 "회의실 배정" 문제를 풀이해본다.문제 분석 및 해결 전략회의가 겹치지 않게 최대한 많은 회의를 진행해야 한다. 이는 완전탐색으로 해결하는 것보다는 주어진 회의 리스트에서 최적의 선택을 반복하는 그리디 알고리즘을 고려하는 것이 적절하다. 그 ..

프로그래밍에서 어떤 선택이 “지금 가장 좋아 보이는 것”이라고 해서 최선의 해가 되는 것은 아니다. 하지만, 그런 탐욕스러운 선택이 오히려 정답으로 이어지는 경우가 있다. 이러한 전략을 우리는 그리디 알고리즘(Greedy Algorithm)이라고 부른다. 이번 글에서는 그리디 알고리즘이 무엇이고, 어떤 상황에서 이를 사용할 수 있는지에 대해서 정리해본다.그리디 알고리즘을 어떤 수식이나 그래프가 있는 그림으로 설명하는 것은 어렵다. 그래서 철학적인(?) 배경과 그 방법에 대한 이론을 정리하는 식으로 내용을 정리해본다.지금 당장 좋은 선택일반적으로 알고리즘 문제를 풀다 보면 전체적인 상황을 고려해서 최적의 해를 찾아야 한다. 동적 계획법 (Dynamic Programming)이나 백트래킹 같은 방식이 대표적..

[C++] 깊이 우선 탐색 (DFS)프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Searchlastnamesong.tistory.comDFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 10451번 "순열 사이클" 문제를 풀이해본다.문제 분석 및 해결 전략배열의 두 번째 열 (주어지는 순열)이 다음 노드의 인덱스 (배열의 첫 번째 열)를 결정한다.그래서 이 문제에서는 어렵지 않게 재귀함수를 생각해볼 수 있다.DFS의 구조와 유사하게 한 번 방문한 이력이 있는 노드에 다시 이르게 되면 함수 발동이 끝나는 식으로 코드를 작성..

이전 글에서 풀이했던 백준의 미로 관련 문제들을 보면 띄어쓰기 없이 입력 받는 것을 볼 수 있었다.이런 문제를 풀기 위해서 우리는 숫자 형태의 데이터를 2차원 배열에 저장해야 한다. 그런데 막상 cin으로 입력을 받아보면, 생각보다 쉽지 않다. 이번 글에서는 이런 상황에서 char 자료형과 '0'의 관계, 그리고 왜 c - '0'이라는 코드를 쓰는지 정리해본다.숫자를 char로 받는 이유먼저, 위 입력에서 한 줄을 보면 101010처럼 공백 없이 숫자들이 이어져 있다. 이걸 cin으로 입력 받을 때, 많은 입문자들이 이렇게 생각하곤 한다.int num;cin >> num; // 한 글자씩 숫자를 받는다?하지만 이렇게 하면 한 줄 전체가 하나의 정수로 읽힌다.즉, 101010이 숫자 하나로 들어오는 것이지..

[C++] 넓이 우선 탐색 (BFS)프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 너비 우선 탐색 (Breadth-First Searlastnamesong.tistory.comBFS 활용 문제 중 하나로 백준 온라인 저지의 2206번 "벽 부수고 이동하기" 문제를 풀이해본다.이전 글인 "미로 탐색" 문제에서 벽이 하나 생긴 형태의 문제로 볼 수 있다.문제 분석 및 해결 전략최단 경로 문제이므로 BFS를 사용해야 한다는 것은 쉽게 생각할 수 있다. 여기에 벽을 부순 이력까지 같이 관리를 해주어야 한다. 그리고 각 좌표에 도달했을 때 거리 계산 내용도 벽 부순 이력에 따라 ..

[C++] 넓이 우선 탐색 (BFS)그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 너비 우선 탐색 (Breadth-First Search)은 가장 널리 사용되는 탐색 방법 중 하나이다.lastnamesong.tistory.comBFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 2178번 "미로 탐색" 문제를 풀이해본다.미로 탐색 문제에서 BFS는 시작점에서 가까운 정점부터 탐색하므로, 목표 지점에 도달했을 때 찾은 경로는 항상 최단 경로가 된다.문제 분석 및 해결 전략이 문제는 최단 거리 (최소 이동 횟수)를 구하는 문제이므로 BFS가 적합하다. BFS는 탐색하는 순간 최단 거리임을 보장하기 때문에, 도착점에 처음 도달한 순간이 답이 된다. 이게 가능한..

[C++] 깊이 우선 탐색 (DFS)프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Searchlastnamesong.tistory.comDFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 13023번 "ABCDE" 문제를 풀이해본다.문제는 아래와 같다. 사람 수가 많지 않다면 그래프를 직접 그려보며 풀이하는 것을 생각해볼 수 있다.문제 분석 및 해결 전략그래프를 그릴 수 있다는 것은 완전 탐색 알고리즘을 사용해볼 수 있다는 것이다. 여기에 이 친구 관계를 보면 재귀적으로 풀 수 있다는 생각을 할 수 있다. 그러면 DFS를 ..

[C++] 깊이 우선 탐색 (DFS)그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Search)은 가장 널리 사용되는 탐색 방법 중 하나이다.lastnamesong.tistory.comDFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 2023번 "신기한 소수" 문제를 풀이해본다.신기한 소수의 정의와 문제의 입력과 출력이 아래와 같이 정의된다.문제 분석 및 해결 전략숫자의 각 자리를 확장하면서 조건을 만족하는지를 확인해야 하므로, DFS를 활용한 재귀 함수의 사용이 적절하다는 생각을 해볼 수 있다. 우선, 한 자리의 소수는 정해져있으므로 2, 3, 5, 7에서 시작하는 것을 생각할 수 있다.다음으로는 자리수를 확장하..