Coding Test/programmers
[프로그래머스] 숫자 타자 대회 (재귀)
https://school.programmers.co.kr/learn/courses/30/lessons/136797 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 2023.06.27 - [programmers/KAKAO] - 양과 늑대 (DFS)
[프로그래머스] 아방가르드 타일링 (DP)
https://school.programmers.co.kr/learn/courses/30/lessons/181186 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 2를 표현하는 방법 3을 표현하는 방법 DP(10) = DP(9) + 2*DP(8) + 5*DP(7) + 2*DP(6) + 2*DP(5) + 4*DP(4) + 2*DP(3) + 2*DP(2) + 4*DP(1) + 2 DP(n)을 구하는데 DP(n-4)부터는 반복되는 구간이 나타나므로 DP(n+3)에서 DP(n)을 빼서 하위 구간을 삭제 DP(13) - DP(10) = DP(12) + 2*D..
[프로그래머스] 등대 (트리, DP)
https://school.programmers.co.kr/learn/courses/30/lessons/133500 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 트리 DP : DFS 풀이 dp[i][j] : i는 노드번호, j는 등대를 켠 경우와 아닌 경우로 1이면 켠 경우 현재 노드가 안켜져 있다면 자식 노드가 켜져있어야 함 현재 노드가 켜져 있다면 자식 노드의 값은 상관 없으므로 최솟값을 취함 더보기 유사문제 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리..
[프로그래머스] 억억단을 외우자
https://school.programmers.co.kr/learn/courses/30/lessons/138475 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 억억단에서 1 ~ 8이 등장하는 횟수는 다음과 같습니다. 1번 등장 : 1 2번 등장 : 2, 3, 5, 7 3번 등장 : 4 4번 등장 : 6, 8 1 2 3 4 5 6 7 8 2 4 6 8 3 6 4 8 5 6 7 8 ➔ 8이 억억단에 등장하는 횟수는 1*8, 2*4, 4*2, 8*1 에 의해 등장할 수 있으므로 8의 약수의 개수인 4 ➔ 숫자의 등장 횟수는 약수 개수와 동일 약수의 개..
[프로그래머스] 금과 은 운반하기 (이분 탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 최솟값(0)과 최댓값(가장 오래 걸리는 도시 트럭으로 금과 은 전체 운반) 사이를 이분 탐색을 통해 최적값 찾아내기 a : 필요한 금의 무게 b : 필요한 은의 무게 g : 각 도시의 금의 양 s : 각 도시의 은의 양 w : 각 도시의 트럭이 운반할 수 있는 최대 무게 t : 도시에서 이동하는 편도 시간 a b g s w t result 90 50 [70, 70, 0] [0, 0, 500]..
[프로그래머스] 로또의 최고 순위와 최저 순위
https://school.programmers.co.kr/learn/courses/30/lessons/77484 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 최대한 맞추는 경우 : 0의 개수 + 일치 개수 최소한 맞추는 경우 : 일치 개수 당첨 번호 31 10 45 1 6 19 결과 최고 순위 번호 31 0→10 44 1 0→6 25 4개 번호 일치, 3등 최저 순위 번호 31 0→11 44 1 0→7 25 2개 번호 일치, 5등 풀이 def solution(lottos, win_nums): c = 0 for i in lottos: if i in..
[프로그래머스] 공 이동 시뮬레이션
https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 1 ≤ n ≤ 109, 1 ≤ m ≤ 109 ➔ 문제대로 시뮬레이션 하면 시간초과 쿼리를 역순으로 돌면서 반대 방향으로 시작점 찾아가기 공들이 쿼리를 진행한 후에 모여 있을 수 있는 영역은 연속한 직사각형 command dx sr sc er ec 2 (행감소 → 행증가) 1 0 0 1 0 0 (열감소 → 열증가) 1 0 0 1 1 1 (열증가 → 열감소) 1 0 0 1 1 0 (열감소 → 열..
[프로그래머스] 고고학 최고의 발견
https://school.programmers.co.kr/learn/courses/30/lessons/131702 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 1. 시곗바늘은 시계방향으로만 돌릴 수 있고 한 번의 조작으로 90도씩 돌릴 수 있습니다. 2. 시계들은 기계장치에 의해 연결되어 있어 어떤 시계의 시곗바늘을 돌리면 그 시계의 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다. 3. 각 시계는 12시, 3시, 6시, 9시 방향 중의 한 방향을 가리키고 있습니다. 4. 각 시계의 시곗바늘을 적절히 조작하여 모든 시곗바늘이 12시 방향을 ..
[프로그래머스] 시험장 나누기 (이분탐색)
ttps://school.programmers.co.kr/learn/courses/30/lessons/81305 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 인원이 가장 많은 그룹의 인원이 최소화되도록 k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 return ➔ 한 그룹당 몇명으로 잡아야 k개의 그룹으로 나눴을때 최대 인원인지 구하기 최대 노드 수: 10000개 그룹을 최대 몇 개까지 나눌 수 있는지: 10000개 완전 탐색 시: 조합(10000!) * 탐색(10000^2) ➔ 이분탐색 k : 그룹의 수를 나타내는 정수 num : 각..
[프로그래머스] 코딩 테스트 공부 (DP, 다익스트라)
https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. DP INF=float('inf') def solution(alp, cop, problems): max_alp=0 # 알고력 max_cop=0 # 코딩력 for a,b,c,d,e in problems: max_alp=max(max_alp, a) max_cop=max(max_cop, b) alp = min(alp, max_alp) cop = min(cop, max_cop) # dp[i][j]..