Leo.K | To become a cooler Developer

오늘은 이분탐색 문제를 풀이하려 한다. 이 문제는 백준 단계별로 풀어보기에서 이분탐색 카테고리에 있는 골드 5문제이다. 문제를 읽는 순간 이게 무슨말이지? 하는 내용으로 생각이 되어 문제를 이해하는데만 오랜 시간이 걸렸다. 기본적으로 이분탐색 알고리즘을 푸는 순서를 한 번 정리하고자 한다. 이분탐색이란 어떠한 대상을 두 부분으로 쪼개면서 탐색하는 방법론이다. 분할 정복은 어떤 전체문제를 해결하기 위해 부분적으로 나눠들어가면서 부분 문제를 해결하는 방식이라면, 이분탐색은 위 메커니즘과 유사하게 두 부분으로 나누어 들어가긴 하지만, 특정 값 또는 구간을 찾는 탐색이라는 것이다. 이분 탐색의 가장 쉬운 예시로는 UP&Down 게임이 있다. 기본적으로 업다운 게임을 진행할 때 무조건 전체 범위에 대해서 중간값만..

한동안 jdbc부터 시작해서 웹 쪽 언어를 공부하다 보니 시간이 부족해서 알고리즘을 풀이만 하고, 따로 정리를 하지 못했다. 살살 귀찮을 뻔 했는데, 다시 마음을 잡고 시작해보려 한다. 이번 문제는 백준 단계별로 문제 풀기 중 백트레킹 카테고리에 있는 골드5 문제로, 완전탐색과 백트레킹을 응용하는 문제이다. 필자는 처음 완전탐색으로 풀어보려다가 애매하게 재귀를 섞어서 백트레킹을 쓰다보니 문제가 풀리지 않아서 한 참을 헤맸다. 이후에는 재귀를 사용해서 백트레킹으로 풀었는데 메모리 초과가 나서 마음이 흔들렸지만,,,, 멘탈을 잡고 다시 수정해서 결국에 성공했다. 문제를 풀기 위해 생각한 의사코드는 다음과 같다. 퀸의 이동 가능한 위치를 일일히 방문처리를 미리 해야 하나? 사실 이 방법으로 처음에 완전탐색을 ..

백트레킹이란 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드(나를 호출한 지점)로 돌아가 다른 자식 노드를 찾는 방법이다. 모든 경우의수를 찾아보지만, 그 중에서도 가능성이 있는 경우의 수만 찾는다. 재귀를 통해 구현한다. 브루트포스와 백트레킹, DFS를 혼동한 경우가 많아서 한 번 정리하고 가겠다. 예를 들어 다음과 같은 문제가 있다고 가정하겠다. "a + b + c = 20을 만족하는 수를 모두 찾으시오.(0

도로는 수평방향으로 일직선 상위에 있다. 인접한 도시간의 거리는 다를 수 있다. 가장 처음위치에서는 반드시 기름을 채워야 한다. 키로당 1리터의 거리 이동(연비똥이네,,,) 주유소는 도시마다 한 개이고, 기름 가격은 다르다. 기름가격이 싼 곳에서 적절히 기름을 구매해서 최종적으로 소요되는 기름의 가격을 최소화 시켜라 기름 가격이 가장 싼곳에서 최대한 많이 사야한다. 변수의 최댓값을 생각했을 때, int형이 아닌 Long형을 사용해야 한다. 다음과 같이 입력예제로 예를 들어보자. 4 2 3 1 5 2 4 1 첫 번째 도시는 기름 가격이 5원으로 비싸지만, 기본적으로 이동해야 하기 때문에 최소한으로 삽니다. (5 * 2) = 10 두번째 도시는 기름가격이 저렴하기 때문에 구매하는데, 이때 다음 도시의 가격을..

출력형식만 맞춰주고, 큐를 이해하고 있다면 기본적인 개념으로 간단하게 풀이할 수 있는 문제입니다. [문제 분석] 환형큐에 대한 문제가 나왔습니다. 환형 큐 또한 기본 큐를 기준으로 만든것이기 때문에 값을 넣고 빼는 메커니즘은 동일합니다. 환형큐 내부가 요소로 가득찬 경우, front에 있는 값을 poll or remove하면 front의 위치가 한 칸 이동하기 때문에, 새로운 값을 offer or add할 때 rear의 위치가 기존에 front가 있던 위치로 이동하게 됩니다. 원활한 이해를 통해 그림을 보겠습니다. 그렇다면 원으로 둘러쌓인(환형큐) 사람들을 탐색하면서 K번째 사람들을 연쇄적으로 배출할겁니다. 이때, 큐의 요소를 중간부터 삭제하고자 하는 것은 기본적인 큐에대한 이해가 부족한 것입니다. 물론..

[문제 분석] 회의시간이 겹치지 않도록 최대한 많은 회의가 진행되어야 합니다. 그렇다면 어떤 회의를 먼저 진행시켜야 할까요? 시작시간이 빠른 회의를 먼저 배치하게 된다면, 회의시간이 얼마나 걸리는지까지 고려해야 하기 때문에, 종료시간을 기준으로 종료시간이 빠를수록 다음 회의를 배치하고 최대한 많은 회의를 진행할 수 있습니다. 주어진 예제 입력값에는 종료시간이 겹치는 경우가 없지만, 문제를 풀기 위해서는 겹치는 경우도 생각해 보아야 합니다. 예를 들어 (2 2), (1 2)이렇게 두 가지의 회의가 있다고 했을 때, 시작시간이 1인 것을 먼저 배치하면, 해당 회의가 끝나자마자 (2 2)회의를 진행할 수 있습니다. 하지만 (2 2)를 먼저 진행하게 되면 회의가 진행되는 시간이 겹치기 때문에 그 뒤에는 (1 2..

알고리즘 스터디를 하면서 큐에 관련된 문제를 풀었습니다. 순서대로 풀다가 마지막에 이 문제의 정답률을 보고 살짝 겁을 먹은 상태로 문제를 읽었을 때는 생각보다 쉬운데? 하고 풀었지만, 시간 초과로 몇 번이나 실패를 했습니다. 사실 아직은 시간 복잡도의 개념을 잘 몰라서 문제에서 제시되는 입력값의 범위를 고려하지 않았는데 디버그를 몇 번을 돌려보고 해 봐도 모르겠어서 포기하려던 와중,,, 문제 밑에 "덱을 활용하여 시간 복잡도를 해결하는 문제"라는 문구를 보고 다시 다른 방법을 생각해보게 되었습니다. 문제에 제시된 대로, 조건과 에러 처리를 충분히 했는데 왜 시간 초과가 날까 생각하면서 코드를 봤더니 결국 시간이 걸릴만한 코드는 배열의 순서를 뒤집는 거였던 것 같아서 그 부분만 수정했더니 코드가 제출되었습..

그리디 알고리즘을 적용하는 첫 번째 문제입니다. 오름차순으로 입력된 동전의 가치를 위에서부터 차례대로 사용합니다. 동전을 사용하면서 매번 조합해야 하는 금액을 넘지 않는지 체크를 해주어야 합니다. 기본적으로 입력의 조건을 보면, 다음 원소는 이전 원소의 배수라는 조건이 있습니다. 여기를 확인해보시면 동전 교환에서는 탐욕 알고리즘으로 최적해를 구하지 못하는 경우의 수가 있지만, 문제 자체에서 배수 조건을 줌으로써 문제 형태를 매트 로이드로 만들었습니다. 따라서 알고리즘만 구현하면 풀 수 있는 쉬운 문제입니다. 핵심 알고리즘은 다음과 같습니다. 1 2 3 4 5 6 7 8 //동전의 가치가 가장 큰 것부터 비교를 시작합니다. for(int i=N-1; i>=0; i--) { //몫 연산자가 0보다 커야 그 ..

스택을 응용하는 알고리즘 문제입니다. 풀이를 시작하기게 앞서 문제를 먼저 분석하여 접근해보겠습니다. 1. 동일한 괄호가 짝을 이루어야 한다. ㄴ> 두 개의 괄호를 구분해서 생각해줘야 합니다. 2. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 있다. ㄴ> 반드시 왼쪽 괄호가 먼저 나와야만 짝을 이룰 수 있다. 3. 짝을 이루는 문자열이 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. ㄴ> 균형이 이루어진 괄호 안에도 괄호가 있을 수 있는데 이 내부에 있는 괄호 또한 균형이 맞아야 합니다. ㄴ> ( ] [ ) 이런 문자열도 외부 괄호는 균형을 이루지만 내부 괄호는 균형을 이루지 않기 때문에 조건에 맞지 않습니다. 위의 문제 분석을 통해 알아낼 수 있는 핵심중에서 이 문제를 해결하기 ..

문제 설명 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있..