기록공간

문제가 길어보여 어려워 보이지만, 생각보다 간단한 문제였다. N마리의 폰켓몬 중 절반만큼 선택하는데, 폰켓몬이 가장 많은 종류부터 한 마리씩 선택하여 몇 종류의 폰켓몬을 선택 할 수 있는지 출력하는 문제이다. 여기서 핵심은 폰켓몬의 종류이다. 답 부터가 몇가지 종류를 선택 할 수 있는지를 물어보기 때문이다. 종류가 N / 2개 보다 많은 경우 종류별로 한마리씩 골라도 N / 2개를 넘어가므로, 최대로 고를 수 있는 종류 N / 2를 답으로 출력하면 된다. 만약 종류가 N / 2개 보다 적은 경우 종류별로 한마리씩 골라도 남은 갯수 만큼은 똑같은 종류에서 골라야 하므로, 폰켓몬 종류 수만큼 출력하면 된다. 코드는 다음과 같다. #include #include using namespace std; int s..

동적계획법을 사용하는 문제였다. 위의 예제를 표로 표현하면 다음과 같다. 이 표는 동적 테이블에 저장될 값들이다. 0부터 표현하는 인덱스 특성상 1~4, 1~3 범위를 그대로 표현하기 위해 5 x 4 크기의 배열로 만들었고, 0번째 행열은 값을 모두 0으로 설정하였다. 웅덩이 위치도 0으로 설정하였다. 0이 설정되면 지나 갈 수 없다. 이제 집과 물 위치를 제외하고 (x, y) 위치의 값은 (x - 1, y) + (x, y - 1)로 설정해주면 된다. 위 표에서 (1, 2)위치를 예로 들어보자. 위의 값이 1, 왼쪽 값이 0으로 1 + 0 = 1이다. (2, 4) 위치는 위의 값 1, 왼쪽 값 1로 1 + 1 = 2이다. 이 작업을 학교인덱스까지 해준다. 그러면 다음과 같이 된다. 집에서 학교까지 갈 수..

BFS/DFS 문제로 분류되었었는데 처음에는 잘 몰랐다. 이미 입력된 값에 +, -를 하는 문제이다. 처음에 +와 - 두가지 경우가 있다. 그리고 +를 선택하면 두번째에 +와 - 두가지 경우가 올 수 있다. 이것이 마지막 번째까지 반복된다. 즉, 배치 가능한 모든 +, -의 경우의 수를 찾는다. 이런 이유로 BFS/DFS 문제로 분류되었다고 생각한다. 그림으로 표현하면 다음과 같다. +, -를 해주는 작업은 재귀함수를 사용해주면 된다. 재귀함수로 처음부터 끝까지 +또는 -를 해주는 방향으로 나아가다, 끝까지 도달했을때 target 값과 같은지 확인하고 같다면 answer값을 1 증가시켜주면 된다. 코드는 다음과 같다. #include using namespace std; void search(const ..

백트래킹(backtracking)은 한정 조건을 가진 문제를 풀려는 전략이다. 문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이루어지는데, 한정 조건을 구성하기 위해서 각각의 변수들은 값이 있어야 한다. 백트래킹은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 가지는 장점은 많은 부분의 조합을 배제(가지치기)하는 것이다. 이로 인해 풀이 시간이 단축된다. 예를 통해서 백트래킹을 알아 보도록 하자. 가장 쉽게 접할 수 있는 예시로는 4-Queens Problem이 있다. N-Queens Problem은 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 만들기 위해서..

처음 내가 접근했던 방법은 다음과 같다. 수업 시작 시간을 기준으로 오름차순하여 정렬한다. 강의실을 담을 벡터 컨테이너를 선언한다. (벡터에 들어가는 값은 수업이 끝나는 시간이다.) 첫 번째 수업이 끝나는 시간을 벡터에 담는다. 이때 강의실은 1개이다. 벡터에서 강의실 수업이 끝나는 시간이 두 번째 수업 시작시간 보다 크거나 같은 경우 해당 강의실의 수업 종료 시간을 두 번째 수업 종료 시간으로 갱신한다. 만약 벡터에서 만족하는 강의실을 찾지 못한 경우, 강의실을 추가하고 해당 수업 종료 시간을 값으로 넣는다. 4 ~ 5 작업을 마지막 수업까지 반복한다. 벡터의 사이즈를 출력한다 코드는 다음과 같다. #include #include #include using namespace std; int main()..

DFS, BFS를 잘 알고 있다면 어렵지 않은 문제였다. 너비 우선 탐색 (BFS) 너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 �� lipcoder.tistory.com 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (Depth First Search : DFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 �� lipcoder.tistory.com DFS, BFS 둘 중 무엇을 사용하더라도 정답이 도출되기 때문에 더 잘되는 것을 사용하..

역시 그리디 알고리즘 관련 문제였다. 예전에 풀었던 섬 연결하기 문제와 비슷한 줄 알았지만, 도시들이 서로 다른 도시를 가는 길이가 최소가 나오도록 도로를 깔아야 했다. 이 문제를 풀기 위해서는 플로이드 워셜 알고리즘이 필요하다. 이 알고리즘은 모든 위치에서의 최단 경로길이를 찾게해주는 알고리즘이다. 자세한 내용은 다음 링크를 참고하자. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 처음 반�� lipcoder.tistory.com 문제에서는 이미 최단 경로를 입력 예제로 주어진..

그리디 알고리즘을 사용하는 문제였다. 처음 접근 방법은 가방의 무게는 오름차순으로, 보석은 가격의 내림차순으로 정렬한 후 가격이 비싼 보석부터 가방에 넣도록하였다. 넣은 보석은 컨테이너에서 제거하였다. 이렇게 해서 올바른 정답이 나왔다. 하지만 컨테이너에서 erase(iterator)로 제거하는 방식은 O(n)이다. 여기에 보석들을 순회 돌기 위한 첫번째 반복문, 넣을 수 있는 가방을 찾기위한 두번째 반복문이 있기 때문에 총 O(n^3)의 시간 복잡도가 된다. 결국 시간 초과로 오답이 났다. 그래서 연산 시간을 좀 더 줄이고자 erase(iterator)를 제거하기 위해 Heap을 사용하였다. Heap에 가방에 담을 수 있는 만큼의 무게의 보석들을 담아놓는다. 이때 Heap은 가격 기준의 최대 힙으로 설..