알고리즘

[프로그래머스 Lv.2] 주식가격 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이사실 이 문제는 스택 문제라고 표현되어 있긴 하나, 이중 for문으로 풀어도 제한 시간 내에 통과할 수 있는 문제이다. 스택을 사용한 풀이는 스택을 더 싼 가격이 나타낼 때까지 가격의 위치(인덱스)를 보관하고 있는 통으로 사용한다는 아이디어로 풀면 된다. 레벨 2 문제치고는 스택을 저런 아이디어를 가지고 사용한다는 것이 조금 어려웠던 것 같다. def solution(prices): ..

[프로그래머스 Lv.4] 도둑질 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이무려 레벨 4의 문제이다. 문제만 보면 쉽게 갈피가 잡히지 않는다. 선형적으로 배치된 집들도 아니고, 원형으로 배치되어 있기에 더욱 느껴지는 난도가 높았던 것 같다.DP 문제가 늘 그렇듯 구현 자체는 어렵지 않은데, 문제 해결을 위한 점화식을 찾는 것이 어려웠다. 우선 DP를 차근차근 풀어가보자. 첫 번째 집부터 도둑질을 해보겠다. 그러면 그때까지의 최댓값은 첫 번째 집의 돈과 같다.두..

[프로그래머스 Lv.3] 등굣길 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이최단거리만 세면 되기에, 특정 칸에 진입할 수 있는 방법은 왼쪽 또는 위쪽으로 한정된다. 그렇기에 현재 칸에 도달할 수 있는 방법의 수는 현재의 왼쪽에 위치한 칸까지 도달할 수 있는 방법의 수와 현재의 위쪽에 위치한 칸까지 도달할 수 있는 방법의 수를 더한 값이다.결론적으로 이전 값을 기반으로 하여 현재 값을 갱신해나가는 풀이가 진행되기에 DP로 이 문제를 풀이할 수 있다.def sol..

[프로그래머스 Lv.3] 정수 삼각형 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이삼각형 꼭대기부터 최하단까지 내려가면서 거쳐간 수의 합이 최대인 경우를 뽑아내는 문제이다. DP를 사용해서 각 층에서의 최댓값을 저장하며 내려오는 하향식 방법으로 풀이해도 되고, 같은 방식으로 진행하되 상향식으로 가장 아래층부터 각 층의 최댓값을 저장하는 방식으로 풀이해도 된다. 하향식에 비해 코드가 더 간단하게 나오는 상향식으로 풀이해 보았다.def solution(triangle):..

[프로그래머스 Lv.2] 후보키 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이후보키의 조건은 유일성과 최소성을 만족하는 것이다. 그렇기에 주어진 데이터들을 적절한 형태로 가공하고, 유일성과 최소성이 만족되는지 확인하면 된다. 우선 유일성을 만족하는지 확인하는 작업은 set 자료구조를 사용하여 비교적 쉽게 생각할 수 있었다. 만약 유일성을 만족한다면 set에서 중복으로 걸러지는 요소가 없기 때문에, set의 크기와 전체 row의 크기가 동일할 것이다. 이 점을 사..

[프로그래머스 Lv.3] N으로 표현 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이number를 만들기 위해 필요한 N의 수를 구하는 문제이다. 하지만 문제의 조건을 살짝 다르게 생각하여 풀이하면 쉽게 해당 문제를 풀이할 수 있다.N을 i개 사용해서 만들 수 있는 숫자들을 알아내고, 만약 원하는 숫자가 알아낸 숫자들 안에 있는지를 확인하면 된다. 또한 N을 i개 사용해서 만들 수 있는 숫자는 (N을 i-j개 사용하여 만들 수 있는 숫자)(사칙연산)(N을 j개를 사용해..

[프로그래머스 Lv.2] 피보나치 수 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이피보나치 문제는 전형적인 DP(Dynamic Programming) 문제이다. DP의 메모이제이션을 활용하여 재귀함수 속에서 이미 계산된 n에서의 피보나치를 저장해두고, n에서의 피보나치 재귀 함수를 호출하면 재귀함수 없이 즉각적으로 저장이 된 해당 수를 반환하도록 하여 재귀함수의 호출 수를 줄임으로써 시간 초과 없이 문제를 해결할 수 있다. import syssys.setrecursi..

[프로그래머스 Lv.3] 베스트앨범 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이장르별 플레이 누적 합을 담고 있는 딕셔너리와 장르별 음악 각각의 플레이 수를 담고 있는 딕셔너리 2개를 활용하여 문제를 풀이하면 쉽게 풀이할 수 있다. 레벨 3 문제치고 어렵지 않은 문제라고 생각한다.from collections import defaultdictfrom functools import cmp_to_keydef cmp(x, y): # 비교 함수 if x[1] == ..

[프로그래머스 Lv.2] 오픈채팅방 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이회원의 uid와 회원의 닉네임을 항상 매핑하고 있는 딕셔너리를 관리하면서, 닉네임 변경이나 채팅방을 들어오고 나가는 내역을 로그로 쌓아놓고, 이를 닉네임과 매칭하여 출력하면 되는 간단한 문제이다.def solution(records): logs = [] # 닉네임 변경이나 채팅방을 들어오고 나가는 내역을 저장할 배열 members = {} # {회원id: 닉네임}을 저장할 딕..

[프로그래머스 Lv.3] 징검다리 건너기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이문제를 풀기 위한 가장 단순한 방법을 생각해 보면, 단순히 사람이 한 명씩 지나갈 때마다 돌의 밟을 수 있는 횟수를 1 줄이고, 더 이상 밟을 수 없는 돌이 연속적인지 체크하면서 더 이상 지나갈 수 없을 때까지 반복하였을 때 최댓값을 알아내는 방법이다. 하지만 이는 데이터의 수 때문에 불가능하다. 만약 20만 개의 돌을 2억 번까지 밟을 수 있다고 하면 반복문의 수가 20만 * 2억 =..