Problem solving
-
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 괄호 회전을 쉽게 하기 위해서 deque.rotate를 활용했다. 올바른 괄호 쌍인지 확인하기 위해서 stack을 활용했다. # 괄호 회전 -> deque.rotate로 구현 # 올바른 괄호 여부 확인 : stack으로! from collections import deque def solution(s): # 올바른 괄호 문자열의 수 answer = 0 # 올바른 괄호 쌍 match = {"[" : "]", "(" : ")", "{" : "}"} # i 만큼 회전 for i in range..
[파이썬] 프로그래머스 괄호 회전하기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 괄호 회전을 쉽게 하기 위해서 deque.rotate를 활용했다. 올바른 괄호 쌍인지 확인하기 위해서 stack을 활용했다. # 괄호 회전 -> deque.rotate로 구현 # 올바른 괄호 여부 확인 : stack으로! from collections import deque def solution(s): # 올바른 괄호 문자열의 수 answer = 0 # 올바른 괄호 쌍 match = {"[" : "]", "(" : ")", "{" : "}"} # i 만큼 회전 for i in range..
2023.02.07 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 LRU : 가장 오랫 동안 참고되지 않은 캐시부터 제거하는 알고리즘 LRU를 사용하려면 사용 순 → 입력 순으로 정렬하는 캐시가 필요하다. # LRU : 최근에 사용되지 않은 캐시부터 교체 # 사용 순 -> 입력 순으로 정렬 필요 from collections import deque def solution(cacheSize, cities): # 실행 시간 answer = 0 cache = deque() for city in cities: # 대소문자 구분 X city = city.lowe..
[파이썬] 프로그래머스 [1차] 캐시 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 LRU : 가장 오랫 동안 참고되지 않은 캐시부터 제거하는 알고리즘 LRU를 사용하려면 사용 순 → 입력 순으로 정렬하는 캐시가 필요하다. # LRU : 최근에 사용되지 않은 캐시부터 교체 # 사용 순 -> 입력 순으로 정렬 필요 from collections import deque def solution(cacheSize, cities): # 실행 시간 answer = 0 cache = deque() for city in cities: # 대소문자 구분 X city = city.lowe..
2023.02.06 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 항상 1칸 또는 2칸만 뛸 수 있기 때문에, 가능한 모든 방법의 수는 $a[n] = a[n - 1] + a[n - 2]$로 표현할 수 있다. 현재 칸에 도달 = 1 칸 전에서 뛴 경우 + 2 칸 전에서 뛴 경우 # 가능한 모든 방법의 수 # a1 = 1 # an = a(n - 1) + a(n - 2) def solution(n): answer = [i for i in range(n + 1)] for i in range(3, n + 1): answer[i] = answer[i - 1] + ..
[파이썬] 프로그래머스 멀리 뛰기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 항상 1칸 또는 2칸만 뛸 수 있기 때문에, 가능한 모든 방법의 수는 $a[n] = a[n - 1] + a[n - 2]$로 표현할 수 있다. 현재 칸에 도달 = 1 칸 전에서 뛴 경우 + 2 칸 전에서 뛴 경우 # 가능한 모든 방법의 수 # a1 = 1 # an = a(n - 1) + a(n - 2) def solution(n): answer = [i for i in range(n + 1)] for i in range(3, n + 1): answer[i] = answer[i - 1] + ..
2023.02.06 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 나머지를 활용한 풀이 비용을 줄이려면 가능하면 항상 순간 이동을 해야 한다. $n$ 번째 위치는 $n // 2$에서 순간 이동해서 바로 가거나, 순간 이동 후 1 만큼 점프하여 갈 수 있다. 따라서 매번 2 로 나눴을 때, 나머지가 1인 경우에만 비용을 추가하면 된다. def solution(n): answer = 0 while n: q,r = divmod(n, 2) # 점프가 필요할 때 비용 추가 if r == 1: answer += 1 n = q return answer DP를 활용한..
[파이썬] 프로그래머스 점프와 순간 이동 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 나머지를 활용한 풀이 비용을 줄이려면 가능하면 항상 순간 이동을 해야 한다. $n$ 번째 위치는 $n // 2$에서 순간 이동해서 바로 가거나, 순간 이동 후 1 만큼 점프하여 갈 수 있다. 따라서 매번 2 로 나눴을 때, 나머지가 1인 경우에만 비용을 추가하면 된다. def solution(n): answer = 0 while n: q,r = divmod(n, 2) # 점프가 필요할 때 비용 추가 if r == 1: answer += 1 n = q return answer DP를 활용한..
2023.02.04 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 전체 대진표는 대결하는 두 쌍($0, 1$)과 순서로 표현할 수 있다. 순서는 숫자를 2 로 나눴을 때 몫으로 표현할 수 있기 때문에, $a$와 $b$가 몫이 같을 때 까지 라운드를 반복하면 된다. # 0 1 2 3 4 5 6 7 # 0 1 2 3 # 0 1 def solution(n,a,b): # 1 라운드부터 시작하기 때문에 answer = 1 # 몫 정보로 대결 여부 파악할 수 있도록 변경 # 몫이 같다면 둘이 매칭된 것 a, b = a - 1, b - 1 while a // 2 !..
[파이썬] 프로그래머스 예상 대진표 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 전체 대진표는 대결하는 두 쌍($0, 1$)과 순서로 표현할 수 있다. 순서는 숫자를 2 로 나눴을 때 몫으로 표현할 수 있기 때문에, $a$와 $b$가 몫이 같을 때 까지 라운드를 반복하면 된다. # 0 1 2 3 4 5 6 7 # 0 1 2 3 # 0 1 def solution(n,a,b): # 1 라운드부터 시작하기 때문에 answer = 1 # 몫 정보로 대결 여부 파악할 수 있도록 변경 # 몫이 같다면 둘이 매칭된 것 a, b = a - 1, b - 1 while a // 2 !..
2023.02.03 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 N개 수의 최소 공배수를 구하기 위해선, 두 정수 사이 최소 공배수를 구한 다음, 그 최소 공배수와 다음 정수 사이 최소 공배수를 구하면 된다. 기존 최소 공배수가 다른 정수에도 적용 되기 위해선, (최소 공배수 * 상수 배) 형식이어야 하기 때문에 각각 최소 공배수를 구하는 과정에서 최악의 경우, 대략 $(100^2)**14$ 정도의 시간 복잡도가 발생하기 때문에, 유클리드 호제법을 활용해 최소 공배수를 찾았다. 유클리드 호제법을 활용한 최소 공배수, 최대 공약수 구하는 방법은 포스팅에..
[파이썬] 프로그래머스 N개의 최소공배수 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 N개 수의 최소 공배수를 구하기 위해선, 두 정수 사이 최소 공배수를 구한 다음, 그 최소 공배수와 다음 정수 사이 최소 공배수를 구하면 된다. 기존 최소 공배수가 다른 정수에도 적용 되기 위해선, (최소 공배수 * 상수 배) 형식이어야 하기 때문에 각각 최소 공배수를 구하는 과정에서 최악의 경우, 대략 $(100^2)**14$ 정도의 시간 복잡도가 발생하기 때문에, 유클리드 호제법을 활용해 최소 공배수를 찾았다. 유클리드 호제법을 활용한 최소 공배수, 최대 공약수 구하는 방법은 포스팅에..
2023.02.03 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다. 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다. 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다. # 한 번에 최대 2명 # 최적 -> 무거운 사람 + 가벼운 사람 def solution(people, limit): people.sort() answer = 0 # 투포인터 시작 - 끝 점 start,..
[파이썬] 프로그래머스 구명보트 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다. 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다. 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다. # 한 번에 최대 2명 # 최적 -> 무거운 사람 + 가벼운 사람 def solution(people, limit): people.sort() answer = 0 # 투포인터 시작 - 끝 점 start,..
2023.02.02 -
모든 사진과 내용은 강의를 참고 했습니다. 투포인터 2 가지 점(시작, 끝점)의 위치를 기록해서, 순차 접근을 빠르게 할 수 있도록 도와주는 알고리즘이다. 투포인터를 사용하면 기존 $O(N^2)$에서 $O(N)$로 시간 복잡도를 줄일 수 있다는 장점이 있다. 매 시행 마다 투 포인터의 시작, 끝 점은 1개 씩 움직이고, 각 점이 마지막 성분에 도달하면 끝나게 되기 때문에 $O(N)$ 임 활용 1 : 부분 합 구하기 투포인터는 수열의 부분 합을 구하는데 활용될 수 있고, 수열의 모든 수가 양수인 경우에만 가능하다. 모든 수가 양수여야 시작점을 오른쪽으로 옮길 때, 합을 구성하는 성분 수가 줄어 합이 줄어 들고, 끝점을 오른쪽으로 옮겨 부분 합을 구성하는 성분 수가 늘어 합이 늘기 때문이다. 투포인터를 활용..
[파이썬] 순차 접근을 빠르게 : 투 포인터 활용하기모든 사진과 내용은 강의를 참고 했습니다. 투포인터 2 가지 점(시작, 끝점)의 위치를 기록해서, 순차 접근을 빠르게 할 수 있도록 도와주는 알고리즘이다. 투포인터를 사용하면 기존 $O(N^2)$에서 $O(N)$로 시간 복잡도를 줄일 수 있다는 장점이 있다. 매 시행 마다 투 포인터의 시작, 끝 점은 1개 씩 움직이고, 각 점이 마지막 성분에 도달하면 끝나게 되기 때문에 $O(N)$ 임 활용 1 : 부분 합 구하기 투포인터는 수열의 부분 합을 구하는데 활용될 수 있고, 수열의 모든 수가 양수인 경우에만 가능하다. 모든 수가 양수여야 시작점을 오른쪽으로 옮길 때, 합을 구성하는 성분 수가 줄어 합이 줄어 들고, 끝점을 오른쪽으로 옮겨 부분 합을 구성하는 성분 수가 늘어 합이 늘기 때문이다. 투포인터를 활용..
2023.02.01 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 노란 박스의 가로, 세로 정보에 따라서 갈색 박스의 정보가 결정 된다. 노란 박스의 가로, 세로는 박스 수의 약수이고, 가로는 그 중에서 큰 값이다. 따라서 노란 박스의 약수를 큰 수 부터 역으로 완전 탐색하면 문제를 풀 수 있다. 탐색 범위에 대해선, 가로의 길이가 세로 길이 보다 크거나 같기 때문에 제곱근 범위 까지만 찾으면 된다. # 노란 박스 정보 : 가로 x 세로 # brown = ((가로 + 2) * 2 + 세로 * 2) def solution(brown, yellow): an..
[파이썬] 프로그래머스 카펫 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 노란 박스의 가로, 세로 정보에 따라서 갈색 박스의 정보가 결정 된다. 노란 박스의 가로, 세로는 박스 수의 약수이고, 가로는 그 중에서 큰 값이다. 따라서 노란 박스의 약수를 큰 수 부터 역으로 완전 탐색하면 문제를 풀 수 있다. 탐색 범위에 대해선, 가로의 길이가 세로 길이 보다 크거나 같기 때문에 제곱근 범위 까지만 찾으면 된다. # 노란 박스 정보 : 가로 x 세로 # brown = ((가로 + 2) * 2 + 세로 * 2) def solution(brown, yellow): an..
2023.02.01 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 중복 여부를 확인하기 위해서 set()을 사용했고, 그에 따라 마지막 단어를 확인하는 변수도 활용했다. words의 길이가 50 정도로 작은 편이기 때문에, 리스트를 사용해서 마지막 단어, 중복 여부 확인을 동시에 하는 것이 더 좋았을 거 같다. # 정답 : (먼저 탈락하는 사람의 번호, 몇 번째 차례에 탈락) def solution(n, words): answer = [0, 0] # 중복 단어 체크 word_set = set() last_word = "" # 끝말잇기 시작 for idx..
[파이썬] 프로그래머스 영어 끝말잇기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 중복 여부를 확인하기 위해서 set()을 사용했고, 그에 따라 마지막 단어를 확인하는 변수도 활용했다. words의 길이가 50 정도로 작은 편이기 때문에, 리스트를 사용해서 마지막 단어, 중복 여부 확인을 동시에 하는 것이 더 좋았을 거 같다. # 정답 : (먼저 탈락하는 사람의 번호, 몇 번째 차례에 탈락) def solution(n, words): answer = [0, 0] # 중복 단어 체크 word_set = set() last_word = "" # 끝말잇기 시작 for idx..
2023.01.31 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색을 활용해서 풀었다. 이 경우 시간 복잡도는 $N$ * $((\log C + C)) \times C$이다. $C$가 대략 $\log_{2}{10^6} = 20$ 정도라서 시간 초과가 발생하진 않는다. # 다음 큰 숫자 : 'n보다 크고, 2 진수 표현에서 1의 갯수가 같은 수' 중에서 가장 작은 숫자 # 시간 복잡도 : n * ((logc + c) * c) def solution(n): n_cnt = bin(n)[2:].count("1") check = n + 1 while Tr..
[파이썬] 프로그래머스 다음 큰 숫자 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색을 활용해서 풀었다. 이 경우 시간 복잡도는 $N$ * $((\log C + C)) \times C$이다. $C$가 대략 $\log_{2}{10^6} = 20$ 정도라서 시간 초과가 발생하진 않는다. # 다음 큰 숫자 : 'n보다 크고, 2 진수 표현에서 1의 갯수가 같은 수' 중에서 가장 작은 숫자 # 시간 복잡도 : n * ((logc + c) * c) def solution(n): n_cnt = bin(n)[2:].count("1") check = n + 1 while Tr..
2023.01.30 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 i, j를 각각 연속된 수의 시작과 끝으로 생각하면, 각 i 마다의 j를 찾으면 문제를 풀 수 있다. 합을 구하는 과정에서 동일한 연산이 계속 반복되기 때문에, 누적합을 미리 계산했다. def solution(n): answer = 0 # 누적합 cum_sum = [] for i in range(10001): cum_sum.append((i * (i + 1) // 2)) # 확인 for i in range(10001): for j in range(i + 1, 10001): if cum_s..
[파이썬] 프로그래머스 숫자의 표현 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 i, j를 각각 연속된 수의 시작과 끝으로 생각하면, 각 i 마다의 j를 찾으면 문제를 풀 수 있다. 합을 구하는 과정에서 동일한 연산이 계속 반복되기 때문에, 누적합을 미리 계산했다. def solution(n): answer = 0 # 누적합 cum_sum = [] for i in range(10001): cum_sum.append((i * (i + 1) // 2)) # 확인 for i in range(10001): for j in range(i + 1, 10001): if cum_s..
2023.01.29