알고리즘/알고리즘 문제 풀이

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

[프로그래머스 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] == ..