상상쓰

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr DFS 알고리즘을 구현하여 가장 하위에 있는 판매원부터 추천인한테 이득을 분배하고 계산된 값을 가지고 더 상위의 추천인한테 이득을 분배하면 된다. 예를 들어 center - S - A (a원), B (b원) 로 나타냈을 때 S 는 (a // 10 + b // 10) 이다. 여기서 center 는 ((a // 10) // 10 + (b // 10) // 10..

https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀 programmers.co.kr 정규식을 어느 정도 다룰 줄 알면 크게 어려운 문제는 아니었다. 1. word 와 page 를 소문자로 통일시킨 뒤 page 에서 조건에 맞는 word 를 찾는다. 2. 웹페이지의 url 과 외부링크를 찾는다. 3. dic 을 이용하여 각 url 의 점수를 계산한 값을 넣어준다. 외부링크에는 있으나 page 의 url 이 아닌 경우와 index 를 구분하기 위해 ..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제의 알고리즘 분류가 정렬 또는 우선순위 큐가 있어서 heapq 와 sort() 로 오름차순으로 정렬하였다. 작은 가방에 들어갈 수 있는 보석은 큰 가방에 당연히 들어가기 때문이다. 오름차순으로 가방에 넣을 수 있는 보석의 가격을 price 에 놓고 heapq 와 '-' 부호를 이용하여 절댓값이 가장 큰 가격을 answer 에 더한..

https://programmers.co.kr/learn/courses/30/lessons/70130 코딩테스트 연습 - 스타 수열 programmers.co.kr 교집합이 될 수 있는 원소의 index 를 가지고 스타 수열의 길이를 구한다. 스타 수열의 최대 길이를 구하려고 한다면 우선 교집합의 원소가 오른쪽에 오는 것을 우선으로 한다. 또한, 스타 수열의 항에서 교집합의 원소랑 아닌 원소랑은 가장 근접한 것을 우선으로 한다. 조건에 맞는 항을 구한 후, 항의 각 원소가 다르면 스타 수열의 길이가 2씩 늘어난다. from collections import defaultdict def solution(a): answer = 0 dic = defaultdict(list) N = len(a) for i in..

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 프로그래머스 4단계 문제치고는 쉬운 문제였다. 원형이라 처음과 끝은 인접하므로 경우를 나눠서 생각했다. 1. 끝을 생각하지 않는 경우 : 1 번 부터 차례대로 인접하지 않고 N-1 번으로 갈 때 훔칠 수 있는 돈의 최댓값 2. 처음을 생각하지 않는 경우 : 2 번 부터 차례대로 인접하지 않고 N 번으로 갈 때 훔칠 수 있는 돈의 최댓값 동적 계획법으로 구현하여 1..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 저번에 풀었던 '배달' 문제랑 비슷하다. 다익스트라 알고리즘을 이용하여 (s, 도작..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net '0' 또는 '1' 이 연속되는 집단의 개수 중 작은 것을 반환하면 된다. 얼마 전에 정규식을 배웠기에 한 번 써봤다. import sys, re S = sys.stdin.readline() answer = min(len(re.findall(r'1+', S)), len(re.findall(r'0+', S))) print(answer)

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr BFS 알고리즘으로 일어날 수 있는 조건을 주어 구현하였다. 각 조건마다 코딩하여서 조금 길다. 한 칸 이동이 예를 들면 가로로 긴 블록일 때 좌우로 한 칸의 움직임만 허용되는 건 줄 알았는데 문제를 자세히 읽어보니 위아래로 가능하여서 틀리는 이유를 찾는데 조금 애먹었던 문제였다. from collections import defaultdict, deque def solution(board)..

https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 토너먼트이므로 n 과 상관없이 a 와 b 는 만난다. 1부터 두 명씩 그룹을 만들고 a 와 b 가 같은 그룹일 때 answer 을 return 해주면 된다. def solution(n, a, b): answer = 0 while True: answer += 1 a = int(a / 2 + 0.5) b = int(b / 2 + 0.5) i..

https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 풀면서 while, for 가 많이 나와서 복잡하기도 하고, 이렇게 푸는 게 아닌가 싶기도 하여 다른 방법을 생각해보려고 하였으나 배열의 길이도 짧고 해서 한 번 시도해봤다. 다행히 통과되었다. 접근 방법은 [1, 5, 6, 10] -> [1, 5, 6, 10, 1+12, 5+12, 6+12, 10+12] 설정하여 반시계방향은 +12 해서 한 방향으로만 생각하도..