프로그래머스

[프로그래머스 Lv.3] 보석 쇼핑 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이투포인터를 사용한 풀이이다. 시작 포인터와 끝 포인터를 두고, 그 포인터 사이에 위치한 보석들의 종류가 주어진 조건을 만족하는지 확인하며 두 개의 포인터를 조절해 가며 최소 길이의 범위를 찾으면 되는 문제이다. 두 개의 포인터 모두 인덱스 0에서 시작한다. 만약 두 포인터 사이에 위치한 보석의 종류가 모든 보석의 종류보다 적다면, 끝 포인터를 1 증가시켜 사이에 위치한 보석의 수를 증가..

[프로그래머스 Lv.3] 디스크 컨트롤러 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선순위 큐를 활용하여 풀이한 문제이다. 현재 시간에서 처리할 수 있는 가장 소요시간이 적은 작업부터 우선적으로 우선순위 큐에서 꺼내 처리하게 하면, 최소의 평균 시간으로 전체 작업들을 처리할 수 있다. 먼저, 현재 시간까지 요청된 모든 작업들을 우선순위 큐에 넣는다. 다음으로 소요 시간이 가장 적은 작업부터 우선순위 큐에서 꺼내 처리를 진행한다. 만약 처리할 수 있는 작업이 없다면, ..

[프로그래머스 Lv.2] 할인 행사 (Python)

문제 풀이: https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이파이썬의 dictionary를 사용해서 쉽게 풀 수 있는 문제이다.먼저 required라는 딕셔너리에 구매해야 할 상품들을 key로, 구매해야 할 개수를 value로 해서 저장을 한다. 다음으로 첫날부터 마지막날 - 10일까지 시작 날짜로 잡아두고, 다음 10일간의 상품들을 required와 마찬가지로 상품들을 key로 구매할 수 있는 개수를 value로 저장한다.각 날짜별로 requ..

[프로그래머스 Lv.2] 피로도 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 순열을 사용하여 모든 가능한 던전의 조합을 구하고, 각 조합들을 주어진 피로도 이내에 모두 탐험할 수 있는지 체크함으로써 해결할 수 있다. 즉, 일반적인 완전 탐색 방식으로 풀 수 있는 것이다.from itertools import permutationsdef check(k, permutation): # permutation에 들어있는 던전의 순열을 k의 피로도로 모두 통과할..

[프로그래머스 Lv.3] 길 찾기 게임 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이진트리, 전위 순회, 후위 순회를 사용한 문제로 알고리즘 문제 풀이를 하다 보면 종종 나타나기에 구현을 해본 경험이 있어 레벨 3 문제치고는 쉽게 풀 수 있었다. 그렇지만 좌표를 사용해서 트리를 그려야 한다는 점, 좌표뿐만 아니라 nodeinfo 내에서 위치한 번호도 알고 있어야 한다는 점이 기존의 이진트리를 사용한 문제가 달랐다고 할 수 있겠다. 우선, 트리의 레벨은 y좌표에 의해 ..

[프로그래머스 Lv.3] 순위 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선 경기 결과 results를 토대로 승리한 사람들과 패배한 사람들을 파악하여 그래프를 그린다.모순이 없고 실력이 뛰어난 선수가 항상 이긴다는 보장이 있으므로 만약 B가 A에게 졌다면, A가 진 모든 사람들에게 B도 모두 지게 된다. 같은 맥락으로 A가 B에게 이겼으므로, A는 B가 이긴 모든 사람들에게 이기게 된다.위와 같은 과정을 반복하여서 모든 선수들의 승/패 관계를 모두 그래프..

[프로그래머스 Lv.3] 가장 먼 노드 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이3단계 치고 BFS를 사용하는 문제이기 때문에, 풀이 방법이 익숙해 쉽게 풀 수 있었던 것 같다. BFS처럼 큐를 사용해 그래프를 순회하면서 시작 정점(1번 정점)에서부터의 거리를 계산하고, 이 중 거리가 가장 먼 정점들의 수를 세는 방식으로 간단하게 풀이할 수 있다.from collections import defaultdict, dequedef solution(n, edges): ..

[프로그래머스 Lv.2] 기능개발 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제 유형이 스택/큐 문제라고 지정되어 있긴 하지만, 스택이나 큐를 사용하지 않고 풀이하였다. 문제 풀이 아이디어는 아래와 같다.우선 ceil 내장 함수를 사용해 완료되기까지 걸리는 날짜를 새로운 배열 rests에 저장한다.rests 배열을 순회하며, 현재 인덱스의 이전까지의 최대값(max_time)보다 큰 값이 나타날 때까지의 누적값(cnt)를 키워간다.max_time은 아직까지 ..

[프로그래머스 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를 차근차근 풀어가보자. 첫 번째 집부터 도둑질을 해보겠다. 그러면 그때까지의 최댓값은 첫 번째 집의 돈과 같다.두..