돌고 돌아 기본

프로그래머스 12914번 - 멀리 뛰기 요구사항 1. 한 번에 1칸 또는 2칸을 뛸 수 있을 때, n개의 칸을 건너 끝에 도달하는 방법의 수를 1234567로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. n개의 칸을 건너 끝에 도달하는 방법의 수를 dp[n]이라고 정의하면 다음과 같습니다. dp[n] = dp[n-2] + dp[n-1] ( n >= 3 ) dp[1] = 1 ( 1칸 ) dp[2] = 2 ( 1칸 + 1칸, 2칸 ) n개의 칸을 건너 끝에 도달하는 경우 마지막에 2칸을 뛰어 끝에 도달하는 경우와, 1칸을 뛰어 끝에 도달하는 경우가 있습니다. 마지막에 2칸을 뛰는 경우는 마지막 2칸을 제외한 n-2 개의 칸을 건너오는 경우의 수이고, 마지막에 1칸을 뛰는 경우는 마지막 1칸을 제..

프로그래머스 17680번 - [1차]캐쉬 요구사항 1. LRU 캐시 교체 알고리즘을 기반으로 주어진 도시 이름들을 조회할 때 걸리는 실행 시간을 측정하여 반환하라. 2. 캐시 히트(cache hit) 일 경우 실행시간은 1, 캐시 미스(cache miss) 일 경우 실행시간은 5이다. 요구사항 분석 및 풀이과정 LRU 캐시 교체 알고리즘은, 캐시의 크기가 꽉 찼을 경우 가장 오래된 캐시 데이터를 삭제하고, 새로운 데이터를 캐싱하는 알고리즘입니다. 자세한 알고리즘이 궁금하다면 여기를 참고해주세요. 우리는 LRU 캐시 교체 알고리즘을 리스트를 이용하여 구현할 것입니다. 리스트의 가장 앞부분은 캐시에 가장 오래된 데이터가 존재하며, 가장 뒷부분으로 갈수록 최근에 캐시에 저장된 데이터가 존재하는 방식입니다. 리..

프로그래머스 42578번 - 위장 요구사항 1. 스파이가 가진 의상으로 입을 수 있는 서로 다른 옷의 조합의 수를 반환하라. 2. 스파이는 하루에 최소 한 개의 의상은 입습니다. 요구사항 분석 및 풀이과정 1. 각 의상 종류마다 의상을 선택할 수 있는 경우의 수는 입지 않는 경우를 포함해서 총 "의상의 수 + 1"입니다. 2. 스파이가 입을 수 있는 서로 다른 옷의 조합의 수는 "모든 의상 종류에 대한 경우의 수를 곱한 값에서 1을 뺀 값"입니다. 1을 빼는 이유는 스파이는 하루에 최소 한 개의 의상은 입어야 하기 때문에, 모든 의상을 입지 않는 경우를 빼줘야 합니다. 3. 각 의상 종류마다 몇 가지 의상이 있는지를 기록하여 경우의 수를 구합니다. 소스코드 작성 import java.util.Map; i..

프로그래머스 12951번 - JadenCase 문자열 만들기 요구사항 1. 문자열의 모든 단어의 첫 문자는 대문자, 그 이외의 문자는 소문자인 문자열을 JadenCase 문자열이라고 합니다. 2. 문자열이 주어질 때 해당 문자열을 JadenCase 문자열로 바꾸어 반환하라. 3. 문자열의 단어는 공백문자(" ")로 구분됩니다. 요구사항 분석 및 풀이과정 1. 문자열의 단어는 공백문자로 구분되기때문에, 모든 단어의 첫 문자의 좌측 문자는 공백문자가 위치합니다. 2-1. 문자열의 모든 문자를 순회하면서, 각 문자의 좌측 문자가 공백문자일 경우 단어의 첫 문자이므로 대문자로 변환합니다. 2-2. 그렇지 않을 경우는 소문자로 변환합니다. 소스코드 작성 class Solution { public String so..

프로그래머스 43238번 - 입국심사 요구사항 1. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 2. 모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 반환하라. 요구사항 분석 및 풀이과정 이 문제는 전형적인 최적화 문제입니다. 대부분 최적화 문제는 그냥 문제대로는 풀기가 어렵기 때문에 결정문제로 변경될 여지가 있는지 확인을 해봐야 합니다. 최적화 문제는 최솟값 중 최댓값, 최댓값 중 최솟값과 같은 유형의 문제를 말합니다. 결정 문제는 가능한지, 불가능한지 2가지로 결과가 정해지는 문제를 말합니다. 최적화 문제를 결정문제로 변경한 후, 결정 문제를 이분 탐색을 이용하여 해결하는 방법을 파라메트릭 서치(Parametric Search)라고 합니다. 1. 우리는 위 문제에서 구하고자 하는 걸리..