방배동 고구마

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 백준 2468번, 안전영역에 대한 풀이이다. 문제는 링크를 참조해주기를 바란다. 문제해결 빗물의 높이가 주어지지 않는 상황에서 Input의 범위를 보고 빗물의 높이를 추정해야하는 것이 주의점이다. 영역의 탐색은 전체 map을 순회하며 visit되지 않은 구역을 Dfs로 탐색하며 방문 표시를 하기로 하였다. 인접 연결된 지역은 하나의 지역으로 판단되므로 Dfs 호출시에 cnt를 올려주었다. 필자는 탐색을 ..

문제 벽돌쌓기를 하자. 인부들이 N명 있고 벽돌 쌓기를 할 작업 갯수가 T만큼 있다. 한명의 인부가 A번 만큼 작업을 하게 되면 R만큼 쉬는시간을 부여한다. 또한 작업 개수 T만큼의 작업 시간이 주어진다. 위의 규칙으로 작업을 할 때 작업이 끝날때까지의 시간을 구하라. 예를 들어 3명의 인부(N=3), 10개의 작업(T=10), 휴식까지 3번의 작업(A=3), 쉬는 시간 2(R=2)라고 주어지고 각 작업시간이 1 2 1 4 3 2 1 5 2 3 라고하면 작업시간표는 아래와 같다. 작업시간은 10 N이 2, T가 8, A가 3, R이 2이고 작업시간이 각각 2 3 4 1 1 5 4 2 일 경우는 아래와 같다. 작업 시간은 13 입력 case1 3 10 3 2 1 2 1 4 3 2 1 5 2 3 case2 ..

문제 지렁이게임을 하자. 지렁이게임은 가장 긴 지렁이를 만드는 게임이다. 지렁이는 1과 0으로 이루어져있고 1과 0이 연속되어 있어야한다. 예를들어 0101은 길이 4짜리 지렁이이다. 0110은 지렁이가 될 수 없고 01과 10 각각 길이 2짜리 지렁이가 될 수 있다. 0과 1의 Input이 주어질때 참가자는 한가지 구간을 변경하여 지렁이를 만들 수 있다. 아래의 표를 보자 길이 10짜리 input이 주어질때 1,2 idx의 input을 바꾸면 참가자가 만들 수 있는 가장 긴 지렁이는 길이 7짜리 지렁이이다. 지렁이 게임에서 참가자가 만들 수 있는 가장 긴 지렁이를 구하라. 입력 지렁이를 구성하는 input의 갯수 N을 입력받는다. N개만큼 1과 0이 입력된다. N은 2이상 100000이하이다. 10 1..

문제 투자게임을 하여 최대의 수익을 내려고 한다. N번의 투자기회가 있다. 각 기회마다 투자시기에 따른 기대수익이 있다. 투자기대 수익은 P이며, 투자시기는 T이다. 각각의 기회에 투자시기를 잘 조정하여 투자결정을 하면 최대의 수익을 낼 수 있다고 한다. 투자시기는 1부터 P값까지이다. 예를 들어 아래의 투자기회가 있다고 하자. N은 5이며 P와 T값은 아래와 같다. 투자시기가 1부터 4까지 있으며 최대 기대수익을 이룰 수 있는 투자시기 조정은 아래와 같다. 투자시기 4에는 투자기회 3번을, 투자시기 3에는 투자기회 4번을, 2시기에는 2번을, 1시기에는 0번이 오게 투자결정을 해야하며 이때의 기대수익은 35이다. 투자기회 N번과, 각각의 P, T가 주어질때 최대 투자기대수익의 값을 구해보자. 입력 투자..

링크드리스트에는 단일, 양방향, 원형 등이 있다. 해당 글에서는 양방향 링크드 리스트를 알아보자. 먼저 링크드 리스트란 논리적인 개념으로 포인터를 활용하여 메모리 순차적인 공간에 data를 만드는 것이다. 얼핏 느끼기엔 배열과 비슷하다. 배열 역시 메모리의 순차적인 공간에 특정 data들이 나열되어 있기 때문이다. 배열과 차이점은 무엇일까? 배열과 차이점 배열은 아래와 같이 선언하게 되어있다. 물론 이것은 모두가 아는 내용. int Arr[4]; 메모리 구조적으로 보면 배열은 컴파일타임에 메모리에 공간이 할당된다. 그렇다. 즉, stack 혹은 data 영역에 메모리가 할당 된다는 뜻이다. (stack과 data 메모리 구조가 기억이 나지 않는다면 아래 글을 보자.) 2021.09.03 - [SW/C] ..

순열은 조합과는 다르다. 순열은 순서가 중요시 되는 수열이다. 예를들어 5개의 숫자 중 3개를 순서에 상관없이 고르는 것은 조합이다. 즉, 조합에서 (1,2,3)과 (3,2,1)는 같은 경우로 판단된다. 그러나 순열은 다르다. 순서가 중요하기 때문에 순열에서 (1,2,3)과 (3,2,1)은 다르다. 중고등학교에서 배웠던 공식이 기억날 것이다. 사실 기억나지 않는다. 0!은 1이다. 기억을 더듬어 5개의 숫자중에 3가지를 뽑아내는 조합의 경우의 수는 10이며, 순열은 60가지가 되겠다. 이를 코드로 어떻게 구현할 수 있을까? 순열 보통의 경우 DFS 알고리즘으로 순열을 구현할 수 있다. 5가지의 수 중에 3가지를 뽑아내는 순열의 경우는 아래와 같다. void Dfs_permutation(int level)..

문제 아이템을 먹어주는 프로그램을 만들려고 한다. 단, 아이템을 먹는 규칙이 있다. 바닥에 떨어져 있는 아이템을 1번 부터 N번까지 있을때, S번의 아이템부터 시작하여 M번째 아이템을 먹는다. 그 후 다음 번호의 아이템부터 셈하여 M번째 아이템을 먹게 된다. 아이템을 먹게되는 순서를 구하라. 예를들어 아래와 같다고 하자. S가 1이고 M이 4이므로 가장 먼저 먹을 수 있는 아이템은 4이다. 이후 4 다음인 5부터 M번째 아이템은 1이므로 두번째 먹을 수 있는 아이템은 1이다. 다음으로 먹게 될 아이템은 1이다. 이와 같은 순서로 다음은 6, 5, 7, 3, 2의 순서로 아이템을 먹게 된다. 입력 N개의 아이템이 입력되며 N은 1부터 10000개이다. 시작하는 아이템 번호가 S로 입력되며 S는 1부터 N까..

우리가 알고리즘을 할때 가장 단순하고도 쉽게 생각할 수 있는 것이 일일이 대조하면 찾는 순차탐색일 것이다. 순차탐색은 for으로 보통 구현되며 경우의 수 N과 M개의 경우에 시간복잡도 O(N*M)을 가진다. 즉, case가 적은 경우 문제될 것이 없으나 N과 M이 10000, 100000을 넘어갈 경우 부하가 심해진다. 때문에 우리는 이진탐색을 알아야한다. 시간복잡도가 logN으로 줄기 때문이다. 순차탐색은 보통의 경우 이진탐색으로 표현될 수 있다. 이진탐색의 기본 개념은 '분할정복'이다. Divide & Conquer. 이진탐색은 3개의 parameter가 필요하다. 탐색하려는 start point, end point, 그리고 찾으려는 target. 이진탐색은 기본적으로 오름차순으로 정렬이 되어 있어야..

문제 영화제에서 작품상을 투표한다. 후보작품은 N개이며 투표 참여 인원은 M명이다. 투표 용지에 1~10점의 점수가 써있고 작품이름이 써있다. 그런데 잘못 기입된 작품 이름이 있어 해당 표는 무효표 처리한다고 한다. 작품상 투표가 완료되었을때, 상위 3등을 구하라. 단, 동점일시 후보번호가 빠른 순서가 상위로 한다. 입력 N은 5부터 10000이다. 작품이름은 20자 이하 알파벳이며 M은 5부터 100000이다. 5 ABC Apple Banana Melon Skycastle 6 Banana 3 Melon 3 Apple 1 ABC 1 SKcastle 10 ABC 1 출력 Banana 3 Melon 3 ABC 2 문제해결 후보자별 이름과 투표용지의 이름을 1:1로 대조하여 모든 비교를 한다. 그럼 시간복잡도..

문제 N개의 샘플이 있고 각각의 샘플에는 정수가 주어진다. 연구를 위해 N개중 2개의 샘플을 채취한다. 이때 샘플이 가진 정수의 합이 0에 가까운 2개의 샘플을 채취하고자 한다. N(2~100000), 정수A(-1000000 ~ +1000000) 이며 샘플의 정수 값으 오름차순으로 입력된다고 한다. 0에 가까운 값이 여러 경우일 경우 가장 빠른 번호의 샘플을 답으로 한다. 위 조건에 맞는 2개의 샘플 번호를 구하라 입력 5 -102 -58 59 78 101 출력 0 4 문제해결 조합 문제이다. N개의 샘플중 2개의 샘플을 고른다. 순서는 상관이 없다. 트리를 구성하는 DFS로 모든 경우의 수를 수행할 수도 있지만 N이 10만개이므로 시간복잡도 N제곱으로 timeout일 경우가 생긴다. 따라서 DFS는 적..

룩업테이블이랑 예상된 결과값을 미리 계산하여 놓은 배열과 같은 집합을 의미한다. 알고리즘 해결에 있어 룩업테이블을 활용해야하는 경우가 있다. 아래의 문제를 살펴보자 문제 주어진 map은 감염경로와 같다. N*N크기의 map에 숫자가 입력되어 주어지며 숫자는 미로의 길을 의미하는데 아래와 같은 정보를 가진다. 지도의 크기 N과, 병균의 위치가 주어진다. 병균은 주어진 지도의 경로를 통해서만 전염된다고 한다. 주어진 map에서 감염되지 않은 경로의 수를 구하라. 입력 4 0 0 2799 7439 0652 2172 출력 5 해결전략1-DFS 1. 주어진 좌표에서 DFS로 확산한다. 2. 확산시에는 방문하지 않은 경로, 경로가 연결된 지점만 확산한다. 3. 각 도로 모양에 따른 상하좌우 방문정보를 미리 Tabl..

스택문제는 참으로 까다롭다. 경험으로 봤을때는 코드로 만들고나서 반드시 Test case를 손으로 똑같이 해봐야 하는 거 같다. 그래야 문제점을 발견할 수 있다. 또한 스택처리 반복안에서 분기를 치거나 첫노드를 먼저 Push하거나 하는 것은 좋지 못하다. 스택처리 반복이 복잡해질 수록 추적하기 어렵기 때문이다. 간단한 스택처리 Test case로 한줄한줄 한손한손 따라가면서 디버깅해보자. 문제 높이가 다른 N개의 전봇대가 주어진다. 서로다른 전봇대끼리 전깃줄을 잇는다. 1. 이웃한 두개의 전봇대는 전깃줄을 잇는 것이 무조건 가능하다. 2. 이웃하지 않은 두개의 전봇대 사이에 양측의 두 전봇대보다 높이가 높거나 같다면 전깃줄을 이을 수 없다. 위의 그림의 경우 5가지의 경우가 있다. 1번과 3번 전봇대는 ..