명이나물 라이브러리

프로그래머스 등굣길, 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..

프로그래머스 체육복 Java 풀이이번에는 프로그래머스 그리디 유형의 체육복 문제를 풀었다.체육복 문제는 그리디 입문 문제로 많이 언급되는 문제이다.문제 자체는 어렵게 느껴지지 않았지만, 실제로 풀면서 연산자 실수 때문에 잠깐 헤맸다.특히 +=를 써야 하는 부분에서 =+처럼 작성하면서 값이 예상과 다르게 나왔고, 디버깅하여 실수를 확인하고 수정하였다.문제 정보항목내용문제프로그래머스 체육복유형그리디사용 언어Java핵심 자료구조int 배열주요 개념학생별 체육복 개수 관리, 앞뒤 학생에게 빌려주기시간복잡도O(N log N)공간복잡도O(N)풀이시간40분결과통과문제 설명 정리전체 학생 수 n이 주어진다.일부 학생은 체육복을 도난당했고, 일부 학생은 여벌 체육복을 가지고 있다.체육복을 도난당한 학생은 수업을 들을 수..

정수 삼각형, DFS로 접근했다가 DP로 다시 풀기처음에는 삼각형의 꼭대기에서 시작해서 아래로 내려가며 모든 경로를 탐색하면 된다고 생각했다.각 위치에서 아래 왼쪽 또는 아래 오른쪽으로 내려갈 수 있기 때문에, 자연스럽게 DFS처럼 모든 경우를 따라가보는 방식을 떠올렸다.하지만 그렇게 접근하니 시간초과가 났다.이 문제는 모든 경로를 직접 탐색하는 문제가 아니라, 각 위치까지 도달했을 때의 최대 합을 저장하면서 내려가는 DP 문제였다.문제 정보항목내용문제프로그래머스 정수 삼각형레벨Level 3유형DP (동적 계획법)사용 언어Java첫 접근DFS / 완전탐색결과시간초과최종 접근DP핵심각 칸까지 도달할 수 있는 최대 합 저장문제 설명삼각형 모양으로 숫자가 주어질 때, 맨 위에서 시작하여 아래층으로 내려가면서 ..

프로그래머스 타겟 넘버 Java 풀이 기록DFS/BFS 개념을 공부한 뒤, 프로그래머스 타겟 넘버 문제를 풀어보았다.이번에는 30분을 잡고 문제를 풀었지만, 시간 안에 풀이를 완성하지 못했다.문제 설명을 아예 이해하지 못한 것은 아니었다. 오히려 “각 숫자마다 + 또는 - 두 갈래로 경우의 수가 나누어진다”는 점까지는 이해했다.하지만 문제는 그다음이었다.머릿속으로는 트리처럼 가지가 나뉘는 구조가 그려졌는데, 이걸 Java 코드로 어떻게 옮겨야 할지 감이 잘 오지 않았다.특히 두 가지 갈래로 나누어지는 부분을 for문 안에서 구현해야 하는지, 아니면 dfs() 메서드 안에서 구현해야 하는지 헷갈렸다.결국 생각은 어느 정도 했지만, 그 생각을 코드로 표현하는 단계에서 막힌 문제였다.문제 풀이 정보문제프로그래..

프로그래머스 K번째수정렬 알고리즘을 공부한 뒤, 연습 문제로 프로그래머스 K번째수 문제를 풀어보았다.문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748사용 언어: Java풀이 시간: 약 24분제한 시간: 30분결과: 성공남은 시간: 약 6분처음에는 단순히 배열을 자르고 정렬하면 되는 문제라고 생각했다.하지만 직접 풀어보니 Arrays.copyOfRange() 사용법, 인덱스 처리, 원본 배열 보존 여부가 중요한 문제였다.1. 문제 설명배열 array의 i번째 숫자부터 j번째 숫자까지 자른 뒤,자른 배열을 정렬했을 때 k번째에 있는 수를 구하는 문제이다.문제 흐름1. array의 i번째부터 j번째까지 자른다.2. 자른 배열을 정렬한..