코딩 테스트17 [DFS/BFS] 아이템 줍기 (파이썬) - 진행 중 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 gr에는 직사각형들의 변에 해당하는 좌표들에 넘버를 달아줌. (0번째 rec면 그 변 좌표들에 gr[x][y].append(0) ) inner 라는 그래프를 따로 만들어서 해당 직사각형안에 있는 모든 좌표들에 True값을 부여해줌 현재 위치 x,y 의 직사각형 넘버를 따온다. 다음으로 이동 할 수 있는 nx,ny 의 gr값(직사각형 넘버)이 이전 x,y에서의 넘버와 같고 gr.. 2023. 6. 13. [탐색] 퍼즐 조각 채우기 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 읽어보면 table에 있는 퍼즐 조각을 하나하나 옮겨보고 gb( game_board) 빈 공간에 딱 들어 맞는지 알아보는 문제 같다. 나 같은 경우는 gb에서 0으로 쭉 이어진 조각들을 구한 뒤 table을 탐색하면서 해당 조각이 table과 딱 들어맞는지 계산 함.(회전 포함) gb에서 0으로 쭉 이어진 각 조각들을 구해서 peace 라는 리스트에 담아줌( 이 때 각.. 2023. 6. 2. [탐색] 미로 탈출 명령어 ( 파이썬 ) 문제 설명 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/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/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. [이분탐색] 입국심사 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 시간부터 사람까지 값의 범위가 10억으로 굉장히 광범위함. 걸리는 시간의 최솟값을 구하는 것이므로 특정 시간대에서의 행할 수 총 사람 수를 구해본다. 사람 수가 n 이상이라면 해당 시간대에서는 모두 처리 할 수 있다는 것이므로 시간의 줄여본다.(end를 mid-1 로) 사람 수가 n 미만이라면 해당 시간대에서는 처리 불가이므로 시간대를 늘려봄(start를 mid+1로) 소스 .. 2023. 4. 22. [힙] 디스크 컨트롤러 (파이썬) 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 현재 시점(time)에서 처리 할 수 있는 작업들을 힙에 모두 넣어줌 현재 시점에서 작업이 가능한 것들이 있다면(len(q)>0) 끄집어내서 처리해줌. 이 때 힙에 넣어준 것이므로 pop을 해준다면 가장 소요되는 작업량이 작은 값이 나올 것. (이 때 나오는 것은 작업량 기준으로 힙에 넣은 것이므로 node[0]은 소요시간, node[1]은 작업 시작 시간임) 그럼 이후의 작.. 2023. 4. 21. 이전 1 2 다음