최장증가 부분수열 - LIS(Longest Increasing Subsequendce) 주어진 수열에서 일부 원소를 골라내어 만든 부분 수열 중, 오름차순으로 정렬된 가장 긴 부분수열을 의미한다. 이때 핵심은 부분수열이 반드시 연속될 필요는 없다는 것이다. 즉 몇 개의 원소를 건너뛰어도 해당 연속으로 정렬만 되면 된다는 것이다. 예를 들어 {2, 3, 8, 6, 4, 5, 9, 1}의 경우 가장 긴 증가 부분수열은 {2, 3, 4, 5, 9}이 됨 특징부분수열의 각 원소는 원래 수열에서 순서를 지켜야 함, 연속적일 필요는 없음오름차순이므로 앞의 원소보다 뒤의 원소가 크거나 같아야 함한 수열에는 여러 개의 최장 증가 부분 수열이 존재할 수 있음 구하는 방법동적계획법 - DP각 인덱스에서 끝나느 LIS의 길..

[Python] 프로그래머스 lv1 - 과일장수 코딩테스트 연습 - 과일 장수 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 제대로 읽자.... 점수 따로 과일 따로인 줄 알았지만 실제로는 과일이 score로 주어질 때 해당 score를 그대로 사용하면 되는 문제 즉 사과의 score가 실제 각 사과의 점수이자 가격 상자에 들어가는 사과 = m 가격은 상자의 들어가는 사과의 점수 p * 사과의 개수 m 사과의 상자 세트 갯수 만들기 접근 방법 주어진 과일 - score를 내림차순으로 정렬 주..

[Python] 프로그래머스 lv2 - 숫자의 표현 코딩테스트 연습 - 숫자의 표현 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 것 숫자 n 구해야 하는 것 n이하의 자연수들의 합으로 n을 만들 수 있는 경우의 수 선택한 접근방법 - 투 포인터 선택 사유 - 숫자들을 더하고 빼면서 n이 가능한 개수 파악에 적합하다고 생각 먼저 start, end, s(sum) 지정 만약 s < n일 경우 합이 n이 되기전까지 end를 덧셈 end+=1 만약 s == n인 경우 answer +=1..

[Python] 프로그래머스 lv2 - JadenCase 문자열 만들기 코딩테스트 연습 - JadenCase 문자열 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 것 문제에 필요한 문자열 조건 모든 단어의 첫 문자 대문자로 변환 나머지 문자는 소문자 공백은 여러 개 가능 - 주의할 점 문제 풀이 주어진 문자열을 리스트로 변환 변환하는 과정에서 모든 문자 소문자 화 공백을 기준으로 공백 다음 문자를 대문자로 변환 예정 첫번째첫 번째 단어 첫 번째 문자의 경우 앞에 공백이 없으..

[Python] 프로그래머스 lv2 - 게임 맵 최단거리 코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 것 게임 맵의 모양이 maps 이차원 리스트로 주어진다 이때 maps의 모양은 n*m의 형태이며 n과 m은 같을 수도 다를 수도 있다 mpas는 정사각형일수도 직사각형의 형태를 가질 수도 있다 maps에서 벽은 0이고 길은 1이다 시작점은 항상 0,0 이다 문제에서 구하라는 것은 목적지까지의 최단거리이며 목적지는 맵의 끝에 존재한다. 문제 풀..

[Python] 프로그래머스 lv2 - [1차] 캐시 코딩테스트 연습 - [1차] 캐시 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 문제에서 주어진 것 cacheSize : 도시이름을 저장할 수 있는 공간의 용량 cities : 도시의 이름이 담긴 배열, 대소문자 구분 x 시간 : cache에 해당 도시가 있을 경우 +1 / 존재하지 않을 경우 +5 LRU : Least Recently Used - 캐시 알고리즘 캐시에 공간이 부족할 때 가장 오랫동안 사용하지않은 항목을 제거하고 새로운..