민규의 흔적

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개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다.먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약 단축키로 아직 지정이 안 되어있다면 그 알파벳을 단축키로 지정한다.만약 모든 단어의 첫 글자가 이미 지정이 되어있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 지정한다.어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문..

2024년 8월 14일문제 링크 : 백준 9095번 - 1, 2, 3 더하기문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 알고리즘 분류다이나믹 프로그래밍 문제 접근 테스트 케이스마다 11 미만의 양의 정수 n이 주어졌을 때, n을 1, 2, 3..

2024년 8월 14일문제 링크 : 백준 15558번 - 점프 게임문제  상근이는 위 그림과 같은 지도에서 진행하는 게임을 만들었다.지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다. ..

2024년 8월 14일문제 링크 : 백준 25195번 - Yes or yes 문제  N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "..