본문 바로가기

분류 전체보기234

[탐색] 미로 탈출 명령어 ( 파이썬 ) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방문했던 곳을 다시 가는 것이 허용되는 문제이므로 방문을 최소화하면서 최적의 길을 찾아야 함 방향 ( down,up, left,right ) 에 대해 알파벳 순서는 d, l, r, u이다. 방문을 최소화 하기 위해 최소 힙을 사용함. 알파벳 순서는 dlru 이므로 이것을 반대로 뒤집은 u, r, l d 로 탐색을 진행하면서 각 dist에 (-1 * dir) 을 더할 것 아래.. 2023. 5. 14.
거스름돈 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 n이 10만이하, money 갯수는 100 이하 이므로 O(N^2)이 되더라도 1000만 이하라 효율성 테스트도 통과 가능 행을 money 요소로 열을 0~n 까지로 2차원 리스트를 생성 화폐 money[i]로 금액 j 를 만드는 방법은 아래와 같음 이전까지 사용한 화폐들로 금액 j를 만든 방법 => dp[i-1][j] 현재 금액 - 현재 화폐를 사용한 방법 => dp [i].. 2023. 5. 13.
[이분 검색] 외벽 점검 (파이썬, 카카오) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 원형 레스토랑을 일직선으로 생각해서 기존 weak을 두배로 늘려줌 eg) weak = (1,3,5,7) 이라면 각 원소에 n(12이라고 가정)을 더해줌 weak = [1,3,5,7,13,15,17,19] 처음에는 가장 긴 dist 원소부터 출발 지점에만 넣고 이후 짧은 dist들을 차례로 넣으면 되는 줄 알았는데 그럴 경우 예외가 생김 ( eg. 짧은 간격에 있는 weak을 .. 2023. 5. 12.
[파이썬] 인사고과 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/152995 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 원호가 높은 점수에서부터 몇 등인지 구하는 문제이니 원호보다 같거나 낮은 점수는 구할 필요 없음 x+y wx and y>wy: return -1 if x+yy: continue else: py = y px = x answer+=1 return answer print(solution([[2,2],[1,4],[3,2],[3,2],[2,1]])) # 어떤 사원이 다른 임의의 사원.. 2023. 5. 11.
[파이썬] 가장 긴 팰린드롬 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음에는 이분 탐색으로 풀려고 했는데 생각해보니 결국 모든 지점에서 다 따져봐야함 특정 지점을 mid라고 두고 [0]부터 [n-1]까지 탐색 팰린드롬이 mid를 중심으로 좌우가 같은 경우 (팰린드롬 길이가 홀수인 경우) mid와 그 오른쪽 값이 같은 경우 이 두가지로 나눠서 품 (팰린드롬 길이가 짝수인 경우) 소스 코드 def solution(se): answer = 0 n .. 2023. 5. 8.
[최단거리] 부대 복귀 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 주어진 양방향 그래프 경로들을 통해 source에 담겨진 원소들이 destination에 도착하는 최단 경로를 각각 구하는 문제 양방향 그래프이므로 source에서 출발한 점들이 des에 도착하는 거리나 des에서 각 점들에 도착하는 거리나 똑같음. start를 des로 두고 경로들을 탐색하면 됨 소스 코드 import heapq def solution(n, roads, s.. 2023. 5. 6.
[링크드리스트] 표 편집 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 주어진 규칙에 따라 위치를 이동하고, 해당 위치 요소를 삭제하거나 가장 최근에 삭제 된 요소를 복구하는 문제 해당 문제의 조건이 아래와 같으므로 삭제나 복구 수행시 리스트를 직접적으로 순회하며 추가 삭제를 하면 시간 초과가 됨 5 ≤ n ≤ 1,000,000 0 ≤ k 2023. 5. 6.
[파이썬] 풍선 터트리기 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 규칙에 따라 최종적으로 남을 수 있는 1개의 풍선은 몇 개 가능한 지 출력하는 문제 인접한 두 풍선을 고른 뒤, 하나를 터트림 번호가 작은 풍선을 1번만 터트리기 가능 이후에는 큰 풍선만 터트림 cur 기준으로 왼쪽에서의 최솟값과 오른쪽에서의 최솟값을 구함 배열의 길이가 1백만이므로 n^2으로 구할 시 시간 초과가 뜸 오른쪽에서의 최솟값은 반대 방향으로 일직선 탐색 cur 기.. 2023. 5. 3.
[데브 매칭] 다단계 칫솔 판매 ( 파이썬 ) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 tree 라는 자식노드: 부모노드 딕셔너리를 이용해서 문제 품 tree에는 center를 따로 기입해서 최종 부모를 넣음 seller를 순회하면서 이익금을 계산 seller[i]의 총 판매액(money)은 amount[i] * 100 이 때 seller[i]의 추천인이 있다면 money의 90%를 seller[i] 의 이익금(profit) 에 담아주고 10%는 추천인 이익금의.. 2023. 4. 26.

티스토리툴바