민규의 흔적

2024년 9월 26일문제 링크 : 백준 5972번 - 택배 배송 문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-..

2024년 9월 24일문제 링크 : 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 문제 접근 현재 나의 숙련도에 따라 퍼즐을 푸는 시간이 달라진다. diffs의 각 요소는 최대 100000이므로, 나의 숙련도는 1 ~ 100,001일 것이다. 1 부터 100,001 까지 일일이 확인해보기엔 시간복잡도 측면에서 좋을 게 없다. (퍼즐의 개수 n의 최대 값은 300,000 이므로, 최악의 경우 100,001 * 300,000 ~= 10^10번 연산해야 한다.) 그러므로 우리는 효율적으로 숙련도의 최소값을 찾아야 한다. 어떻게? 이분 탐색으로! 내가 가질 수 있는 숙련도의 범위는 1 ~ 100,001 이므로 양 끝 값인 left, right는 각각 1, 100,001로 초기화 시켜준다. le..

2024년 9월 24일문제 링크 : 프로그래머스 - 과제 진행하기 문제 접근 주어진 데이터를 자신이 원하는 목적에 맞게 가공하여 활용할 수 있는지가 문제의 난이도를 좌우한다고 생각한다. 구현 문제는 문제에서 요구하는 바를 정확히 이해해야 한다. 1. plans의 요소들은 진행할 과제들에 대한 정보를 담고 있으며, 이는 [과제명, 과제 시작시간, 소요시간]으로 이루어져 있다. 2. 과제는 시작하기로 한 시각이 되면 시작한다. 3. 새로운 과제를 시작할 시간이 되었을 때, 기존에 진행하고 있던 과제가 있다면 해당 진행을 멈추고 새로운 과제를 시작한다. 4. 진행 중이던 과제를 끝냈을 때, 멈춰두었던 과제가 존재한다면 해당 과제를 이어서 진행한다. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시..

2024년 9월 10일문제 링크 : 프로그래머스 - 땅따먹기문제 접근 0번째 행부터 마지막 행까지 규칙에 맞춰 칸을 한 칸 씩 밟아가며, 최대로 많이 누적시킬 수 있는 점수를 출력하는 문제이다. 여기서 말한 규칙은 다음과 같다. 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 만약 1번째 열의 칸을 밟았다면, 다음 행에선 1번째 열 칸은 밟지 못한다는 의미이다. 마지막 행까지 도달하는 모든 경우의 수를 계산하기엔 최대 행의 개수가 100,000개로 시간복잡도가 엄청 불어나게 된다. 이를 효율적으로 풀기 위해 다이나믹 프로그래밍 기법을 활용하기로 결정하였다. DP(다이나믹 프로그래밍) 기법을 활용하고자 결정한 이유는 다음과 같다. 특정 칸 까지 누적할 수 있..

2024년 9월 5일문제 링크 : 백준 1283번 - 단축키 지정문제한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다.먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약 단축키로 아직 지정이 안 되어있다면 그 알파벳을 단축키로 지정한다.만약 모든 단어의 첫 글자가 이미 지정이 되어있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 지정한다.어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문..