명이나물 라이브러리

프로그래머스 입국심사, 사람배정이 아닌 시간을 이분 탐색하기이번에는 프로그래머스의 입국심사 문제를 풀어보았다.👉프로그래머스 입국심사 문제처음에는 꽤 어려웠다.문제를 읽었을 때 자연스럽게 이렇게 생각했다.각 사람을 어떤 심사관에게 배정해야 하지?더 빠른 심사관에게 먼저 보내야 하나?비어 있는 심사대가 있어도 기다렸다가 더 빨리 끝나는 심사대를 이용해야 하나?하지만 이 문제는 사람을 심사관에게 직접 배정하는 문제가 아니었다.핵심은 n명을 모두 심사할 수 있는 최소 시간을 구하는 것이었다.문제 설명입국심사를 기다리는 사람 수 n명이 있고, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 times 배열로 주어진다.모든 사람이 심사를 받는 데 걸리는 최소 시간을 구해야 한다.예를 들어:n = 6;times =..

👉프로그래머스 체육복 문제문제 설명전체 학생 수 n명이 있고, 일부 학생은 체육복을 도난당했다.또 일부 학생은 여벌 체육복을 가지고 있다.체육복을 도난당한 학생은 바로 앞번호나 바로 뒷번호 학생에게만 체육복을 빌릴 수 있다.즉, i번 학생은 아래 학생에게만 빌릴 수 있다.i - 1번 학생i + 1번 학생체육복을 빌려줄 수 있는 학생은 여벌 체육복을 가진 학생뿐이고, 여벌 체육복은 한 벌만 빌려줄 수 있다.이때 체육 수업을 들을 수 있는 학생의 최댓값을 구해야 한다.문제 유형 분류이 문제는 그리디 문제이다.체육복을 도난당한 학생을 앞번호부터 확인하면서, 빌릴 수 있는 학생이 있으면 바로 빌리는 방식으로 접근할 수 있다.이 문제에서 중요한 점은 앞번호부터 차례대로 처리해야 한다는 것이다.예를 들어 도난당한..

등굣길 문제를 두 번째로 풀면서 DP 접근 자체는 맞게 잡았다.dp[y][x]에 시작점부터 (x, y)까지 이동하는 경우의 수를 저장하고, 위쪽과 왼쪽 값을 더하는 방식으로 구현했다.다만 처음 제출한 코드에서는 구현 과정에서 몇 가지를 놓쳤다. 👉등굣길 - 첫풀이(문제포함)1. 웅덩이 좌표 순서를 반대로 사용했다문제에서 puddles는 [x, y] 형태로 주어진다.하지만 DP 배열은 행, 열 순서로 사용했기 때문에 dp[y][x] 형태가 되어야 한다.처음에는 아래처럼 작성했다.dp[puddle[0]][puddle[1]] = -1;하지만 올바른 코드는 아래와 같다.dp[puddle[1]][puddle[0]] = -1;배열을 new int[n + 1][m + 1]로 만들었기 때문에,첫 번째 인덱스는 세로 ..

프로그래머스 등굣길, DP로 풀기이번에는 프로그래머스의 등굣길 문제를 풀어보았다.👉프로그래머스 등굣길 문제문제 설명집에서 학교까지 가는 길이 격자 형태로 주어진다.집은 왼쪽 위에 있고, 학교는 오른쪽 아래에 있다.이동은 오른쪽과 아래쪽으로만 할 수 있다.중간에 물웅덩이가 있는 칸은 지나갈 수 없다.이때 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구해야 한다.단, 경로의 수가 매우 커질 수 있으므로 정답은 1,000,000,007로 나눈 나머지를 반환해야 한다.문제 유형 분류이 문제는 DP, 동적 계획법 문제이다.처음에는 DFS로 모든 경로를 탐색하면 되지 않을까 생각했다.각 칸에서 이동할 수 있는 방향은 최대 두 가지이다.오른쪽으로 이동아래쪽으로 이동그렇기 때문에 DFS로 모든 경로를 탐색할 수도..

프로그래머스 타겟 넘버, DFS로 모든 경우 탐색하기3주 전에 풀었던 프로그래머스의 타겟 넘버 문제를 다시 풀어보았다.👉 처음 풀이 programmers) 타겟 넘버, 재귀 연습하기 👉 프로그래머스 타겟 넘버 문제문제 설명n개의 음이 아닌 정수들이 주어진다.이 숫자들의 순서는 바꾸지 않고, 각 숫자 앞에 + 또는 -를 붙여서 원하는 타겟 넘버를 만들어야 한다.예를 들어 아래 숫자들이 있을 때,[1, 1, 1, 1, 1]타겟 넘버 3을 만드는 방법은 다음과 같다.-1 +1 +1 +1 +1 = 3+1 -1 +1 +1 +1 = 3+1 +1 -1 +1 +1 = 3+1 +1 +1 -1 +1 = 3+1 +1 +1 +1 -1 = 3총 5가지 방법이 있으므로 정답은 5이다.제한 사항numbers의 개수는 2개 ..

프로그래머스 | 더 맵게이번에는 프로그래머스의 더 맵게 문제를 풀어보았다.문제 링크는 아래와 같다.👉프로그래머스 더 맵게 문제문제 설명매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어 한다.이때 스코빌 지수가 가장 낮은 두 개의 음식을 골라 아래 방식으로 섞는다.섞은 음식의 스코빌 지수= 가장 맵지 않은 음식의 스코빌 지수+ (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)이 과정을 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복해야 한다.만약 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없다면 -1을 반환해야 한다.입출력 예시scovilleKreturnKreturn[1, 2, 3, 9, 10, 12]72예시를 직접 따라가 보면 다음과 같다.처음 음식의 스코빌..

프로그래머스 가장 큰 수 이번에는 프로그래머스의 가장 큰 수 문제를 풀어보았다. 👉 프로그래머스 가장 큰 수 문제문제 설명0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 구하는 문제이다.예를 들어 주어진 정수가 아래와 같다면,[6, 10, 2]만들 수 있는 수는 다음과 같다.6102, 6210, 1062, 1026, 2610, 2106이 중 가장 큰 수는 6210이다.즉, 배열 numbers가 주어졌을 때 숫자의 순서를 재배치해서 만들 수 있는 가장 큰 수를 문자열로 반환해야 한다.제한 사항numbers의 길이는 1 이상 100,000 이하numbers의 원소는 0 이상 1,000 이하정답이 너무 클 수 있으므로 문자열로 반환입출력 예시는 다음과 같다.numbersre..

연속된 부분 수열의 합 | 두 번째 풀이3주 전에 풀었던 프로그래머스 연속된 부분 수열의 합 문제를 다시 풀어봤다.이전에 풀었던 기록은 아래 글에 정리해두었다.👉 프로그래머스 - 연속된 부분 수열의 합 이전에 풀었을 때도 투 포인터를 사용했지만, 그때는 for문 + while문 구조로 풀었다.이번에는 while문 하나를 사용해서 left와 right를 직접 움직이는 방식으로 다시 풀어봤다.문제 이해하기이 문제는 주어진 수열 sequence에서 합이 k가 되는 연속된 부분 수열을 찾는 문제다.조건은 다음과 같다.1. 연속된 구간의 합이 k가 되어야 한다.2. 합이 k인 구간이 여러 개라면 길이가 가장 짧은 구간을 선택한다.3. 길이가 같다면 시작 인덱스가 더 작은 구간을 선택한다.예를 들어,sequenc..

이분 탐색이분 탐색은 영어로 Binary Search라고 한다.처음에는 이름이 조금 어렵게 느껴졌는데, 개념 자체는 생각보다 단순하다.핵심은 이것이다.정렬된 데이터에서 가운데 값을 확인하고,필요 없는 절반을 버리면서 원하는 값을 찾는 방법이다.즉, 처음부터 끝까지 하나씩 확인하는 것이 아니라,범위를 계속 절반으로 줄여가며 찾는 탐색 방법이다.이분 탐색이란?이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘이다.예를 들어 1부터 100까지 숫자 중에서 73을 찾는다고 해보자.하나씩 찾는다면 이렇게 확인해야 한다.1, 2, 3, 4, 5, ... 73운이 나쁘면 꽤 많은 숫자를 확인해야 한다.하지만 이분 탐색은 가운데부터 본다.1 ~ 100의 가운데쯤인 50을 확인한다.73은 50보다 크다.그러면..