알고리즘

[python] 프로그래머스 Lv1 - 공원 산책

🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📁 분류 자료구조 완전탐색 💡풀이 start point를 찾아서 route의 방향대로 장애물이 없고, len을 벗어나지 않는다면 이동시켜 최종 이동한 좌표를 구하는 문제이다. 문제는 매우 심플했는데 코드의 길이가 너무 길어서 다른 사람의 풀이를 보았더니 for-else문과 dictionary를 이용한 풀이도 있었다. 언어는 배우기 정말 쉬우나 그 언어답게 쓰는건 어려운 것 같다. 💻 코드 # 내 풀이 def get_start_point(park): for i in range(len(park)):..

[Python] 프로그래머스 Lv1 - 달리기 경주

🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📂 분류 구현, 자료구조 💡 풀이 제한사항을 고려하지 않고 list의 index 와 swap을 이용해서 문제를 해결했으나 시간초과가 발생했다. 시간초과 이유는 최대 1,000,000 * 50,000 = 500억 이므로 O(N^2)의 시간복잡도를 가지는 알고리즘은 사용할 수 없었다. player의 순위를 dictionary에 저장하여 swap을 사용했다. 💻 코드 def solution(players, callings): rank = {key : i for i, key in enumerate(pl..

[Python] 프로그래머스 Lv2 - JadenCase 문자열 만들기

🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📂 분류 문자열 💡 풀이 문자열을 소문자로 바꾸고, 공백을 기준으로 분리한다. ⚠️ 문제 설명을 보면 공백 문자가 연속적으로 나올 수 있다고 나와있다. 따라서 split()을 사용하면 연속된 공백을 하나로 취급하기 때문에 split(' ')을 사용해야 한다. 그리고 분리된 문자열이 비어있지 않을 때 capitalize()라는 첫 문자를 대문자로 바꾸어주는 내장 함수를 사용한다. 💻 코드 def solution(s): s = s.lower() answer = '' split = s.split(' ..

[Python] 프로그래머스 Lv2 - 피보나치 수

🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📂 분류 DP 💡 풀이 피보나치 수는 DP의 대표적인 문제이다. 피보나치 수는 DP를 사용하지 않고 재귀 함수로 풀 경우 이미 계산된 값을 또 계산하기 때문에 스택 버퍼오버플로우가 발생할 수 있다. 때문에 DP를 사용하여 값을 구한다. 점화식은 다음과 같다 f[i] = f[i - 1] + f[i - 2] 위 점화식을 이용해 구현하면 문제를 해결할 수 있다. 💻 코드 MOD = 1234567 def solution(n): global MOD fibo = [0] * (n + 1) fibo[1] = ..

[Python] 프로그래머스 Lv2 - 최솟값 만들기

🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📂 분류 그리디 💡 풀이 주어진 배열 2개의 원소를 곱한 값을 더하여 최솟값을 구하는 문제이다. 접근 방식 하나의 원소는 최솟값, 다른 원소는 최댓값을 곱해서 더하면 최솟값을 구할 수 있다. a 배열은 오름차순, b 배열은 내림차순으로 정렬한다. 💻 코드 def solution(a, b): answer = 0 a.sort() b.sort(reverse=True) for i in range(len(a)): answer += (a[i] * b[i]) return answer

[Python] 프로그래머스 Lv2 - 최댓값과 최솟값

🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📂 분류 문자열 구현 💡 풀이 문자열에 포함된 수들의 최댓값과 최솟값을 찾아내는 구현 문제이다. 파이썬으로 푼다면 매우 간단하게 해결할 수 있다. 💻 코드 def solution(s): s = list(map(int, s.split())) return str(min(s)) + ' ' + str(max(s))