명이나물 라이브러리

정수 삼각형, 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. 자른 배열을 정렬한..

할인 행사 - 고정길이 슬라이딩 윈도우로 풀기문제를 풀게 된 이유슬라이딩 윈도우를 공부한 뒤, 실제 문제에 적용해보기 위해 프로그래머스의 할인 행사 문제를 풀어봤다.이 문제는 10일 동안 할인하는 상품 목록을 확인해서, 내가 원하는 상품과 수량을 모두 구매할 수 있는 회원가입 날짜의 개수를 구하는 문제다.처음 문제를 봤을 때는 단순히 10일씩 잘라서 확인하면 될 것 같았다.하지만 직접 코드를 작성해보니, 단순 반복보다 고정길이 슬라이딩 윈도우로 푸는 게 더 깔끔하다는 걸 알게 됐다.문제 이해회원가입을 하면 가입한 날부터 10일 동안 할인 상품을 구매할 수 있다.예를 들어 내가 원하는 상품이 다음과 같다고 하자.want = ["banana", "apple", "rice", "pork", "pot"];num..

연속된 부분 수열의 합 Java 풀이 — 투포인터로 시간초과 해결하기1. 문제 소개이번에 풀어본 문제는 프로그래머스 Lv.2 문제인 연속된 부분 수열의 합이다.문제에서는 비내림차순으로 정렬된 정수 배열 sequence와 정수 k가 주어진다.이때 합이 k가 되는 연속된 부분 수열을 찾아, 해당 구간의 시작 인덱스와 마지막 인덱스를 배열로 반환해야 한다.조건은 다음과 같다.부분 수열의 합은 k여야 한다.합이 k인 부분 수열이 여러 개라면 길이가 가장 짧은 수열을 선택한다.길이도 같다면 시작 인덱스가 더 작은 수열을 선택한다.처음에는 단순히 모든 구간의 합을 구하면 되지 않을까 생각했다.하지만 제한사항을 보고 완전탐색으로는 풀기 어렵다는 것을 알 수 있었다.2. 제한사항 확인문제의 제한사항은 다음과 같다.5 ..

문제 설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제한사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다. 입출력 예sanswer "()()" true "(())()" true ")()(" false "(()(" false 입출력 예 설명 ..

문제 설명 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다. arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요. 제한사항 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 크거나 ..

문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫..

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예participantcompletionreturn ["leo", "kiki",..