Notebook

목차 1. 동적 프로그래밍소개 2. 중복되는 부분 문제 3. 최적 부분 구조 4. 재귀적 솔루션 작성 5. 우리 솔루션의 시간 복잡도 6. 우리 솔루션의 문제점 7. Memo에 값을 저장하는 방법 소개 8. Memo에 값을 기록하는 솔루션의 시간 복잡도 9. Tabulation: 상향식 접근 1. 동적 프로그래밍소개 동적 계획법 - 나무위키 (namu.wiki) 슬라이드 : Dynamic Programming (work in progress) (slides.com) 동적 프로그래밍을 제대로 이해하기 위해서 재귀를 알고있어야 한다. 동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼개서 각 하위 문제들을 풀어서 그 답을 저장하는 방식으로 문제를 푸는 것이다. 2. 중복되는 부분 문제 예시 ..

보호되어 있는 글입니다.

문제 코딩테스트 연습 - 실패율 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 문제설명 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율..

문제 코딩테스트 연습 - 폰켓몬 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각..

문제 코딩테스트 연습 - 체육복 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 ..

문제 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수..

문제 코딩테스트 연습 - K번째수 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 코드 function solution(array, commands) { let answer = []; for (let command of commands) { answer.push(array.slice(command[0]-1, command[1]).sort((a, b) => a - b)[command[2]-1]); } return answer; } solution( [1, 5, 2, 6, 3, 7, 4], [ [2, 5, 3], [4, 4, 1..

문제 https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 풀이 1. 함수(solution)의 인자(nums)로 들어온 배열 값 중에 3개의 값을 조합으로 찾는다. 2. 3개로 조합된 값들을 합산한 값이 소수이면 answer값을 1증가 시킨다. 3. 2번을 완료하면 answer를 리턴한다. 코드 느낀점 이번 문제의 목표는 아래와 같다 1. 배열인자들 중에 3개 값을 조합으로 구하는 것 2. 소수..

문제 https://programmers.co.kr/learn/courses/30/lessons/86051 코딩테스트 연습 - 없는 숫자 더하기 0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. programmers.co.kr 코드 및 풀이 1. 숫자 배열 변수 생성 2. 함수인자 배열의 루프 돌면서 숫자 배열(numArr)안에 있는 값과 비교하며 해당 되는 값 삭제 시킴 3. 숫자 배열에 남은 요소들을 합산 해서 리턴함 더 나은 풀이 1. [0~9] 의 숫자 합인 45에서 함수인자 배열을 reduce 메서드로 더한 값을 빼줌 2...

문제 코딩테스트 연습 - 키패드 누르기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 코드 function solution(numbers, hand) { let answer = ''; let keyPad = { '1' : [0, 0], '2' : [0, 1], '3' : [0, 2], '4' : [1, 0], '5' : [1, 1], '6' : [..