주니어 개발자의 대나무숲

파라메트릭 서치 문제는 단독 문제로 나오기보다는 다른 알고리즘과 결합해서 출제되는 것 같습니다.파라메트릭 서치는 간단히 말하자면, (갓종만북의 표현을 빌려) 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것 이라고 할 수 있습니다. 지금은 이 표현이 와닿지 않을 수 있습니다. 간단한 그림을 통해 한 번 설명해보도록 하겠습니다. 다음과 같이 나이순으로 정렬된 사람들이 있습니다. 그리고 25살 이상이라면 소주를 좋아한다는 것이 증명되어 있다고 합니다. 그럼 이 중에서 소주를 좋아하는 나이가 가장 어린 사람은 누구일까요?? 물론 가장 간단한 방법은 앞에서부터 차례대로 "너 소주 좋아하니?"라고 물어보면서, 처음으로 "네!"라고 대답하는 사람을 찾는 ..

1. 개념 BFS(Breadth First Search)는 그래프 전체를 탐색하는 방법 중의 하나입니다. 그래프 전체를 탐색하는 방법은 크게 BFS와 DFS, 두 가지가 있다고 할 수 있습니다. 그 둘 중 오늘은 BFS에 대해 배워보도록 하겠습니다. BFS의 핵심은 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문하도록 구현한다는 점입니다. 그리고, 이를 구현하기 위해 STL의 queue를 사용하게 됩니다. 인접한 노드들을 먼저 방문한다는 말이 잘 이해가 안되신다면, 아래의 그림을 통해 이해하실 수 있을 겁니다. 위의 그림은, 노드 A부터 시작해서 BFS로 모든 노드를 방문하는 것을 나타낸 모습입니다. BFS는 인접한 노드들을 차례대로 방문한다고 했었습니다. 시작 노드인 노드 A에 인접한 노드는 노..

그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후에 푸는 것이 보편적입니다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다. 1. 인접 행렬2. 인접 리스트 1. 인접 행렬 1) 정의인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다. adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0 cf) 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수 있습니다. 2) 예시간단한 예시를 통해 이해해보도록 하겠습니다. 다음과 같은 그래프가 있는 경우, 이 그래프의 연결 관계를 인접 행렬로 나..

BOJ 13417 카드 문자열 (https://www.acmicpc.net/problem/13417) 이 문제는 한 면에 문자가 써 있는 카드를 왼쪽부터 하나씩 가져와 재배열하는데, 재배열한 카드들의 왼쪽 끝과 오른쪽 끝에만 카드를 놓을 수 있는 경우 사전순으로 가장 빠른 문자열이 되도록 재배열하는 문제입니다. 이 문제는 각각의 카드를 재배열할 때, 왼쪽 끝에 놓을 것인지 오른쪽 끝에 놓을 것인지를 판가름하는 기준이 무엇일지만 알면 쉽게 풀 수 있습니다. 예제로 나와있는 M,K,U에 대해 생각해 보겠습니다.M은 첫 번째 카드이므로 그냥 올려놓은 후, K를 추가할 때의 상황입니다. K를 M의 왼쪽에 올려놓아야 할까요 아니면 오른쪽에 올려놓아야 할까요? 답은 왼쪽입니다. 이유는 왼쪽에 올려놓는 경우와 오른쪽..

BOJ 13416 주식 투자 (https://www.acmicpc.net/problem/13416) 이 문제는 해당 날짜에 각 회사의 주식이 낼 수 있는 이익(양수)과 손해(음수)가 값으로 주어지고, 하루에 최대 한 회사의 주식만 구매할 수 있을 때(아무 회사의 주식도 구매하지 않을 수 있음) N일 동안 낼 수 있는 이익의 최댓값을 고르는 문제입니다. 최대 한 회사의 주식만 구매할 수 있고 구매할 수 있는 주식의 값에 제약 조건이 없으므로 매우 쉬운 문제입니다. 이익을 가장 많이 낼 수 있는 회사의 주식을 구매하되, 이익의 최댓값이 음수인 경우(모든 회사의 주식이 손해를 내는 경우)에는 아무 회사의 주식도 구매하지 않으면 전체 이익을 최대로 할 수 있습니다. 1234567891011121314151617..

BOJ 13414 수강 신청 (https://www.acmicpc.net/problem/13414) 이 문제는 C++ STL라이브러리의 map을 이용하므로, map에 대해 잘 모르신다면, 아래글을 참고해주세요!C++ STL라이브러리의 map, set(http://sarah950716.tistory.com/6) 해당 수업의 수강 가능 정원과 수강신청 버튼을 누른 학생의 학번이 순서대로 주어질 때, 수강신청에 성공한 학생들의 학번을 출력하는 문제입니다. (단, 동일한 학생이 수강신청 버튼을 두 번 이상 누른 경우 마지막에 누른 것만 유효처리됨) 이 문제는 단순한 구현 문제입니다. 단, 동일한 학생이 수강신청을 두 번 누른 경우, 마지막에 누른 것만 유효처리해야 하기 때문에 중복을 제거할 수 있는 자료구조를 ..

BOJ 13413 오셀로 재배치 (https://www.acmicpc.net/problem/13413) 앞면은 검정, 뒷면은 흰색으로 된 오셀로 말을 ① 임의의 2개의 말을 위치를 바꾸거나(인접한 말일 필요없음)② 말 1개를 뒤집어 색깔 변경 하는 작업 중 하나를 골라 시행할 수 있을 때, 초기 상태에서 목표 상태까지 도달할 수 있는 최소 작업 횟수를 구하는 문제입니다. 특정한 알고리즘을 사용하는 문제는 아니지만, 예시들을 통해 어떻게 말을 바꿔나가는 것이 최소 작업 횟수가 되는지를 생각하다 보면 방법을 알 수 있습니다. 제가 사용한 방법은 B여야 하는데 W인 말과, W여야 하는데 B인 말을 서로 모두 바꾼 후에(①) 아직 목표 상태에 도달하지 못한 말들을 각각 뒤집는(②) 방법입니다. 검정색에서 흰색이..

5. map 1) 정의인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열(후에 사용법을 이해하기 편하도록 '배열'이라고 했지만, map의 내부적인 구조는 각 노드가 key와 value의 쌍으로 이루어진 '트리'입니다. 특히 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중의 하나인 '레드 블랙 트리'로 구현되어 있습니다. 검색 속도가 특히 빠른데 이는 key를 기준으로 정렬된 상태이기 때문입니다.) 2) 용도연관 있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우 (Ex. 만약 SNS상 사람들의 친구 관계를 그래프를 이용해 나타내고, 이 그래프에 여러가지 알고리즘들을 적용해 멋진 일들을 하고 싶다고 합시다. 일반적인 경우라면, 사람을 정점으로, 사람들 간의 친구..

1. queue 1) 정의 FIFO(First In First Out, 선입선출) 자료구조 2) 용도 ① BFS(Breadth First Search, 너비우선탐색) ② 특별한 알고리즘을 사용하는 것이 아니라 직접 문제 상황을 구현하는 문제들 중 FIFO의 구조를 가지는 문제를 풀 때 (Ex. 다리에 올라갈 수 있는 최대 하중과 각 트럭의 무게가 주어질 때, 모든 트럭이 다리를 지나가는 데 걸리는 최소 시간을 구하는 문제. 다리에 먼저 올라간 트럭이 먼저 나오게 되기 때문에 queue를 이용해 구현하면 풀 수 있다.) 3) 사용법 queue를 사용하기 위해서는 를 include 해야 합니다. 편의상 멤버 함수의 적용 대상이 되는 queue를 q라고 부르도록 하겠습니다. 멤버 함수 기능 q.size() q..

가장 기본적인 STL 컨테이너라고 할 수 있는 pair와 vector에 대해서 먼저 알아보도록 하겠습니다. 이해하기 쉽도록 제 나름대로 정한 정의와 문제를 풀 때의 쓰임새를 알아보고 난 후, 멤버 함수들과 예제를 통해 사용법을 익혀보도록 하겠습니다. 1. pair 1) 정의 이름이 'first', 'second'인 두 개의 변수를 저장할 수 있는 struct 2) 용도 ① 이차원 배열의 인덱스 ② 이차원 좌표평면에서의 좌표 ③ 정점 번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야 되는 경우 3) 사용법 pair를 사용하기 위해서는 를 include 해야 합니다. pair는 다른 컨테이너들에 비해 간단한 구조이기 때문에 멤버 함수가 적습니다. 따라서, 바로 예제를 통해 pair의 기본적인 사용법을 ..