문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 부위의 옷은 입거나, 안 입은 경우 2 가지만 존재한다. 입을 경우, 현재 부위에 속하는 옷 개수 만큼의 경우가 가능하고, 입지 않는 경우는 1 가지만 있다. 따라서 (현재 부위 옷의 개수 + 1)을 통해서, 모든 위장 경우의 수를 표현할 수 있다. 최소 1 개의 의상은 입어야 하기 때문에, 마지막에 1을 빼주면 전체 경우의 수를 얻을 수 있다. # n, m, k, l # nC1, mC1, kC1, lC1 -> n, m, k에 대한 선택 # 종류가 많은 경우 -> 시간 초과가 발생할 ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 행렬의 곱을 얻기 위해선 arr1의 행과 arr2 열 사이의 연산이 필요하다. arr2의 열 성분을 얻기 위해서 zip(*arr2)를 활용했다. *arr2를 통해 unpacking을 하면 각 행 별 리스트([] [] [])를 얻을 수 있고, zip을 사용하면 리스트의 n 번째 항 끼리 묶을 수 있다. 각 행의 n 번째 항 끼리 묶은 것은 결국 행렬의 열과 동일하다. # (a x b) * (b x a) = (a x a) # 행 - 열 성분 사이 곱 def solution(arr1, arr2..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 괄호 회전을 쉽게 하기 위해서 deque.rotate를 활용했다. 올바른 괄호 쌍인지 확인하기 위해서 stack을 활용했다. # 괄호 회전 -> deque.rotate로 구현 # 올바른 괄호 여부 확인 : stack으로! from collections import deque def solution(s): # 올바른 괄호 문자열의 수 answer = 0 # 올바른 괄호 쌍 match = {"[" : "]", "(" : ")", "{" : "}"} # i 만큼 회전 for i in range..

사용 방법 deque 선언 시 maxlen 파라미터에 인자를 전달한다. from collections import deque deque(maxlen = n)

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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 나의 풀이 나머지를 활용한 풀이 비용을 줄이려면 가능하면 항상 순간 이동을 해야 한다. $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 나의 풀이 전체 대진표는 대결하는 두 쌍($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 나의 풀이 N개 수의 최소 공배수를 구하기 위해선, 두 정수 사이 최소 공배수를 구한 다음, 그 최소 공배수와 다음 정수 사이 최소 공배수를 구하면 된다. 기존 최소 공배수가 다른 정수에도 적용 되기 위해선, (최소 공배수 * 상수 배) 형식이어야 하기 때문에 각각 최소 공배수를 구하는 과정에서 최악의 경우, 대략 $(100^2)**14$ 정도의 시간 복잡도가 발생하기 때문에, 유클리드 호제법을 활용해 최소 공배수를 찾았다. 유클리드 호제법을 활용한 최소 공배수, 최대 공약수 구하는 방법은 포스팅에..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다. 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다. 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다. # 한 번에 최대 2명 # 최적 -> 무거운 사람 + 가벼운 사람 def solution(people, limit): people.sort() answer = 0 # 투포인터 시작 - 끝 점 start,..

모든 사진과 내용은 강의를 참고 했습니다. 투포인터 2 가지 점(시작, 끝점)의 위치를 기록해서, 순차 접근을 빠르게 할 수 있도록 도와주는 알고리즘이다. 투포인터를 사용하면 기존 $O(N^2)$에서 $O(N)$로 시간 복잡도를 줄일 수 있다는 장점이 있다. 매 시행 마다 투 포인터의 시작, 끝 점은 1개 씩 움직이고, 각 점이 마지막 성분에 도달하면 끝나게 되기 때문에 $O(N)$ 임 활용 1 : 부분 합 구하기 투포인터는 수열의 부분 합을 구하는데 활용될 수 있고, 수열의 모든 수가 양수인 경우에만 가능하다. 모든 수가 양수여야 시작점을 오른쪽으로 옮길 때, 합을 구성하는 성분 수가 줄어 합이 줄어 들고, 끝점을 오른쪽으로 옮겨 부분 합을 구성하는 성분 수가 늘어 합이 늘기 때문이다. 투포인터를 활용..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 노란 박스의 가로, 세로 정보에 따라서 갈색 박스의 정보가 결정 된다. 노란 박스의 가로, 세로는 박스 수의 약수이고, 가로는 그 중에서 큰 값이다. 따라서 노란 박스의 약수를 큰 수 부터 역으로 완전 탐색하면 문제를 풀 수 있다. 탐색 범위에 대해선, 가로의 길이가 세로 길이 보다 크거나 같기 때문에 제곱근 범위 까지만 찾으면 된다. # 노란 박스 정보 : 가로 x 세로 # brown = ((가로 + 2) * 2 + 세로 * 2) def solution(brown, yellow): an..