프로그래머스

이 문제는 문제에서 어피 치과 과녁을 쏜 이후에 라이언이 과녁을 쏘는데 문제에 규칙에 따라서 라이언이 최대 점수차로 이기게 과녁을 쏠려면 어떻게 점수를 얻어야 할지 구하는 문제이다. 이 문제를 보면서 어떻게 구현할지 고민을 했는데 나에게 힌트가 됐던 점은 점수가 1에서 10까지 있다는 것과 오직 점수 얻는 방식이 상대편(어피치) 보다 많이 그 점수를 맞췄을 때 딱 그 점수만 얻는다는 점이다. 예를 들면 어피치가 10점 3발, 라이언이 10점 4발을 맞춘다면 점수는 라이언만 10점을 얻게된다는 점이다. 즉, 10개의 점수판 중에서 1점을 획득한다/ 못한다, 2점을 획득한다 / 못한다 이런 식으로 경우의 수가 2의 10 제곱으로 완전 탐색을 할 수 있다는 점이 나에게 힌트였다. 나는 위의 아이디어를 바탕으로..

이 문제는 한 마을에서 다른 마을로 이동할 때 비용(시간)이 주어질 때 다른 마을까지의 비용이 주어진 K보다 작은 마을의 개수를 구하는 문제이다. 가장 먼저 다익스트라가 떠올랐고 실제로 다익스트라 알고리즘을 통해 문제를 풀었다. 한가지 특이점은 보통 다익스트라는 목적지까지의 최소비용을 구할 때 많이 사용해온 알고리즘이지만 이 문제는 특별한 목적지가 존재하지 않다. 그렇기 때문에 나는 이 문제에서 heap 자료구조를 사용하지 않았다. 최소비용으로 갈 수 있는 경우에만 enqueue를 하면서 그래프 탐색을 하다가 더 이상 최소비용으로 갈 수 있는 도시가 없을 때 종료하도록 코드를 만들었다. (지금 생각해보니 heap을 사용하여 현재까지 비용이 K가 넘어가면 중지하는 식으로 구현해도 될 것 같다.) 정리하자면..

문제에서 요구하는 대로 코드를 짜면 되는 구현문제이다. 이 문제는 요구사항도 일곱단계로 정리해서 주었고, 효율성을 크게 요구하는 문제도 아니기 때문에 문제가 원하는대로 구현하면 쉽게 풀수 있는 문제이다. 약간 까다로운 조건이라하면, 연속으로 마침표를 사용할 경우에는 마침표가 제거된다는 점이 있었는데 백준 문자열폭발 문제에 비하면 까다로운 조건도 아니였다. 문자열 폭발처럼 스택으로 해결하지 않고 플래그로 해결했어도 됐지만, 나는 스택을 이용하여 풀었다. 문제조건은 아래와같다. stack 자료구조를 이용하여 쉽게 풀 수 있었다.

이 문제는 작업이 들어오는 시간과, 그 작업이 걸리는 시간을 알려주는 이차원 배열이 주어질 때 각 작업이 요청부터 종료까지 걸린 평균시간이 가장 적은 답을 구하는 문제이다. 살짝 보면 Greedy문제 같지만, 문제에서 제공된 예시들을 봤을 때, CPU 스케줄링의 SPN방식과, SRN 방식이 떠올랐다. 물론 문제에서 선점, 비선점에 대한 설명을 해주지 않아 어떤 방식으로 해야 할지 고민했지만, 우선 구현이 쉬워 보이는 SPN방식으로 문제를 풀어보았고 다행히 정답이 나왔다. SPN방식이란 기본적으로는 작업이 들어온 시간을 기준으로 작업을 처리하지만, 작업을 처리하는 중에 들어온 작업들에 대해서는, CPU요구량이 적은 것 부터 처리하는 비선점 방식의 스케줄링이다. 즉, 이문제의 요구사항과 같이, 기본적으로는 ..

오늘 풀어본 문제는 프로그래머스의 야근지수라는 문제이다. 문제를 간략히 요약하자면, 리스트안의 수들을 n만큼 줄일 수 있는데, n만큼 줄인 후 리스트의 제곱합이 최소가 된 경우의 값을 구하라는 문제이다. 문제를 읽었을때, 그리디하게 생각해서 가장 큰 수를 줄일수록 야근시간(리스트의 제곱합)이 줄어들지 않을까?라는 생각으로 풀었다. works의 최대 길이가 20000이였기 때문에 이중 포문으로 가능할 수도 있겠다 싶어서 풀었고 다행히 통과하였다. 가장 큰 값을 기준으로 잡고, works를 돌면서 기준과 같은 값은 -1 처리를 해주었다. 순회가 끝날 때마다, 기준값을 1씩 낮춰주었고, 기준값이 0보다 작아지거나, n이 0이 되면 답을 반환하였다. 사실 문제를 풀면서도 시간 초과가 될 줄 알았는데, 운이 좋게..

이 문제를 처음 본 순간 든 생각은 이게 왜 '이분 탐색'이지? 였다. 다른 방법으로 풀까 했지만 n이 1,000,000,000을 for 문으로 돌릴 자신이 없었기 때문에 결국 다른 풀이들을 레퍼런스 했다. 다른 블로그 글들을 보면서 내가 아직 이분 탐색을 제대로 이해하지못했고, 아직 많이 부족하다는 것을 깨달았다. 우선, 다른 풀이들을 보면서 나 스스로 한번 문제와 이분탐색을 정리해보았다. 이진 탐색은 정렬된 배열에서 내가 원하는 값을 가지고 있는 배열의 인덱스를 찾는 기법이다 즉, 이문제에서 우리가 찾고 싶은 것은 총 소요되는 최소 시간이기 때문에 시간을 인덱스로 생각해야 한다. 시간을 인덱스라고 생각하고 이분 탐색하듯이 LEFT와 RIGHT값을 찾아야 하는데, 시간은 무한하기 때문에 우리가 범위를 ..

사실 이 문제는 어렵지는 않지만, 제한사항과 문제 카테고리가 없었으면 좀 헤매었을 것 같다. 왜냐하면 완전 탐색 문제만 보면 DP문제가 아닌가? 하는 겁이 나기 때문이다. 하지만, 위에 말한것 처럼 제한사항에서 주어지는 숫자 개수가 20개 이하인걸 확인한다면, 쉽게 풀 수 있을 것이다. 이문제는 숫자들의 배열과 타겟넘버가 주어질 때, 숫자들의 배열의 합과 차로 타깃 넘버를 만들 수 있는 방법의 개수를 묻는 문제이다. 더하거나 뺄 수 있다는 부분에서 부분집합(itertools)를 활용하기에는 조금 어려움이 있을 것 같아 나는 완전 검색(DFS) 방식으로 문제를 풀었다. 원하는 타겟넘버가 되는 조건을 종료 조건으로 그전까지는 배열을 진행하면서 합과 차를 각각 구해보는 전형적인 완전 탐색 풀이법을 사용해 보았..

달팽이 문제는 많이 기억에 남는 문제이다. 왜냐하면 싸피를 시작하며 처음 알고리즘을 알게 되었고, 알고리즘 스터디에서 문제를 풀 때, 나에게 절망을 준 문제 중 하나였기 때문이다. 그때 다른 분들이 조건을 찾아서 풀거나 delta기법을 이용하여 문제를 풀 때, 어떻게 그렇게 구현하지 생각하며 부러워했던 기억이 난다. 그래도 이제는 나도 그때 달팽이 문제보다 조금 어려워진 문제를 구현으로 바로 풀어내는 것을 보니 성장했다는 것이 체감되는 아주 기분 좋은 문제였다. 문제는 아마 알고리즘 문제를 풀어 보는 모든 사람들이 익숙한 문제일 것이다. 이문제가 다른점은 달팽이가 삼각형 모양으로 움직인다는 것이다. 문제를 보면 1번위치에서 출발해서 왼쪽 아래 꼭짓점, 오른쪽 아래 꼭짓점, 다시 위쪽 꼭짓점 방향으로 달팽..