lastnamesong

그리디 알고리즘 (Greedy Algorithm)프로그래밍에서 어떤 선택이 “지금 가장 좋아 보이는 것”이라고 해서 최선의 해가 되는 것은 아니다. 하지만, 그런 탐욕스러운 선택이 오히려 정답으로 이어지는 경우가 있다. 이러한 전략을lastnamesong.tistory.com이전 글과 다른 그리디 문제 풀이 글에서도 이야기했지만, "이 문제를 그리디로 풀 수 있는가?"를 판단할 수 있는 것이 중요하고, 여기에 "그리디를 어떻게 쓸 것인가?"를 결정하는 것도 어려운 문제이다. 그리디 알고리즘을 적용하는 방법을 1) 기준을 정의하고, 2) 정렬을 하거나 우선 순위를 지정하고, 3) 그에 따라 선택하는 흐름이라고 정리했던 적이 있다. 이전에 풀었던 회의실 배정 문제 (백준 1931번)를 풀 때에는 회의가 끝나..

이전 글을 비롯한 여러 예제 풀이에서 정렬을 사용했던 적이 있다.단순한 일차원 vector나 array 외에도 다양한 차원의 자료형을 다뤄야 하는 상황이 있으며, 그 때 당황하지 않고 정렬을 사용할 수 있도록 공부하고자 C++에서의 sort 함수에 대해 정리해보도록 한다.sort 함수는 "시작과 끝"을 알려주면 동작하며, 시작과 끝을 정의하는 방식이 벡터와 배열에서 조금씩 다르다.sort함수 기본형C++에서 sort함수를 사용하는 기본적인 방법은 아래와 같다.sort(시작주소, 끝주소);여기서 시작주소와 끝주소는 범위를 나타낸다. 벡터에서는 .begin(), .end()로 범위를 줄 수 있고, 배열에서는 포인터 방식으로 범위를 준다.벡터를 sort하는 방법벡터는 .begin()과 .end()로 간단하게 ..

그리디 알고리즘 (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는 탐색하는 순간 최단 거리임을 보장하기 때문에, 도착점에 처음 도달한 순간이 답이 된다. 이게 가능한..