본문 바로가기

코딩 테스트107

[우선순위 큐] 야근 지수 *** 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 큰 값을 모두 처리하는 것보다 큰 값들을 모두 균등하게 처리해야 제곱값들의 합이 최소가 나옴 a^2 + b^2 2023. 4. 3.
[그리디] 단속 카메라 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 routes에 대한 정렬을 진입,진출 중 어떤 것으로 할 지 선택해야함 진출로 잡아야 해당 차량이 이동하는 구간에서의 카메라 위치를 잡을 수 있음. 현재 차량의 진입 시점이 카메라보다 크다면 그 카메라는 지금의 차량을 잡을 수 없으므로 카메라를 하나 더 추가해야함 그 카메라의 위치는 현재 차량의 진입,진출을 모두 커버 가능해지므로 최대 범위인 진출로 일단 잡아둠. 3,4번 논.. 2023. 4. 3.
[동적 계획법] 등굣길 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 좌표 (1,1)에서 출발 해서 (n,m)으로 도착하는 최단 경로의 개수를 구하는 문제(문제에서는 m,n 이라 했는데 평소 n,m으로 습관이 되어있어서 n,m으로 도착하는 걸로 설정해서 품) 최단 경로로 도착하는 거리가 아닌 경로의 개수를 구하는거임 visited 그래프에서 웅덩이인 부분은 -1로 미리 표시 (못 건넘) 오른쪽과 아래로만 이동 하니 이전 경로로 빠질 경우 x 1.. 2023. 3. 31.
[DFS/BFS] 단어 변환 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 begin 에 담긴 단어를 알파벳 하나씩 바꿔가며 target에 담긴 단어로 변환하는 과정 규칙은 words 리스트에 담긴 단어들로만 변환 할 수 있음. 딕셔너리를 이용해서 풀 수도 있겠지만 그냥 인덱스로 계산해서 코드를 짬 begin이 변할 수 있는 것들도 찾기 위해 일단 words에 담음 words에 담긴 각각의 단어들에 대해 자신이 변할 수 있는 모든 경로를 찾아서 그래.. 2023. 3. 30.
[DFS/BFS] 네트워크 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 연결된 노드들을 확인한 후 0번 노드부터 BFS 방식으로 탐색하면서 한번에 연결지을 수 있는 것들 모두 연결 0번 노드로부터의 탐색이 끝나면 1,2,3,4,5,...n-1번 노드 순서대로 탐색하는데 이미 탐색했던 거라면 continue 탐색하지 않았더라면 새로운 네트워크의 발견이므로 answer+1 소스 코드 from collections import deque def sol.. 2023. 3. 30.
[연습 문제] 최고의 집합 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 주어진 S라는 숫자에 대해 n가지로 표현 한 뒤 각각의 표현들에 대해 곱한 값이 최댓값인걸 찾는 문제 중간 값에서 최댓값이 나온다는 걸 알게 됨 S를 n으로 나눈 몫을 a, 나머지를 b라고 선언 a가 n개가 있고, 그 중에서 b개 만큼 +1 을 하면 그 집합이 최댓값이 됨 s=9,n=2 이면 a=4,b=1 => 2,2,2,2 => 3,2,2,2 => 24 소스 코드 def s.. 2023. 3. 29.
[힙] 이중 우선순위 큐 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 operation에 따라 삽입/ 최댓값 pop/ 최솟값 pop을 하는 문제 각 op에 따라 split로 나눠 준 뒤 각 연산을 수행 우선순위 큐로 짬 heapq 는 push와 동시에 정렬을 수행함 (기본적으로 최대 정렬-최솟값이 맨 앞으로) 파이썬에서 제공하는 heapq의 기본은 최소 힙을 기반으로 하고 있어서 pop을 할 시 최솟값이 나옴 최댓값은 큐의 맨 뒤에 있으므로 D.. 2023. 3. 29.
[동적 계획법] 정수 삼각형 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 다이나믹 프로그래밍 문제 점화식: dp(i,j) = dp(i,j) + max( dp(i-1,j) , dp(i-1,j-1) ) i,j의 기준을 아랫줄로 잡고 윗 줄에서 내려온 두 값 중 최댓값을 현재 위치에 더함 소스 코드(python) def solution(triangle): answer = 0 n = len(triangle) for i in range(n): #밑에서 점화.. 2023. 3. 29.

티스토리툴바