Python
-
[Python] Programmers 다단계 칫솔 판매카테고리 없음 2021. 7. 31. 18:32
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 2. 문제 요약 부모 노드에게 10% 수익을 배분하여 판매원들의 이익금을 구하는 문제 3. 아이디어 정리 판매자 별 부모에게 칫솔 수익을 나눠준다. 부모가 있는 경우 부모에게 수익 배분 & 자신의 수익에서 배분한 금액만큼 빼기 내 부모가 부모의 부모에게 수익 배분하기 위해 재귀 호출 부모가 없는 경우고 센터한테만 수익 배분하고 끝 4. 문제..
-
[Python] 백준 10159 저울알고리즘/문제풀이 2021. 7. 31. 18:31
1. 문제 링크 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 문제 요약 비교 결과를 알 수 없는 물건의 개수 구하기 3. 아이디어 정리 플로이드와샬을 이용해 모든 노드에서 다른 노드 경로 구하기 a > b 가는 경로가 없는 경우(비교 결과를 알 수 없는 경우), count + 1 해주기 플로이드와샬 개념 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 2차원..
-
[Python] 백준 14466 소가 길을 건너간 이유 6알고리즘/문제풀이 2021. 7. 24. 19:32
1. 문제 링크 14466번: 소가 길을 건너간 이유 6 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 2. 문제 요약 길을 이용해야 하는 소들 쌍을 구하는 문제 예제 문제를 그려보면 아래와 같다. 소의 위치와 길의 위치가 주어지고, 두 소가 쌍을 지어 서로 길 없이 만날 수 있는지 확인을 해야 한다. 3. 아이디어 정리 소를 한 마리씩 돌려주면서(소 1) 정해진 길 없이 길을 건널 때 방문 여부를 모두 체크 ⇒ bfs 1에서 구한 소 1의 방문 여부 결과에서 소 2..
-
[Python] Programmers 행렬 테두리 회전하기알고리즘/문제풀이 2021. 7. 24. 19:24
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 2. 문제 요약 해당 위치를 시계 방향 회전한다. 회전에 의해 바뀐 숫자 중 가장 작은 숫자를 배열에 담아 리턴한다. 3. 아이디어 정리 시계 방향으로 회전하기 아래 그림과 같은 로직으로 진행된다. 왼쪽 > 오른쪽, 위 > 아래, 오른쪽 > 왼쪽, 아래 > 위 순서로 swap 하면서 진행한다. 회전한 숫자 중 최소값 찾기 4. ..
-
[Python] 백준 16236 아기 상어알고리즘/문제풀이 2021. 7. 24. 19:20
1. 문제 링크 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 문제 요약 아기 상어가 물고기를 먹으러 가는데 걸리는 최단 거리 구하기 3. 아이디어 정리 bfs로 현재 상어 위치에서 갈 수 있는 최단 거리를 찾는다. ⇒ bfs 예외처리 필요: 큰 상어는 못 지나간다. 1 결과를 이용하여 가장 가까운 물고기 위치를 얻는다. 예외 처리: 아기 상어보다 작은 물고기만 먹을 수 있다. 2에서 진행한 결과가 있는 경우 아기 상어 위치와 크..
-
[Python] 백준 15961, 2531 회전 초밥알고리즘/문제풀이 2021. 7. 17. 21:27
1. 문제 링크 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmi..
-
[Python] Programmers 순위 검색알고리즘/문제풀이 2021. 7. 17. 21:23
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/72412 총 16가지 종류 for i in info: i = i.split() case = get_combinations(i) for c in case: all_info[c].append(int(i[-1])) # 2. dict에 있는 리스트 점수를 이분 탐색해서 구하기 위해 sorting for k in all_info.keys(): all_info[k].sort() # 3. 쿼리 하나씩 돌려 해당 조건에 있는 dict를 찾아 이분탐색으로 점수에 맞는 사람 찾기 for q in query: q = q.replace("and","").split() score = int(q.pop()) q = ""...
-
[Python] Programmers 광고 삽입알고리즘/문제풀이 2021. 7. 17. 21:17
1. 문제 링크 코딩테스트 연습 - 광고 삽입 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 2. 문제 요약 시청자들의 누적 재생시간이 가장 많은 곳 찾기 ⇒ 누적합으로 구하기 [입력값] play_time: 동영상 끝나는 시간 adv_time: 공익광고 재생 시간 logs: 시청자들 시청하는 구간 [리턴 값] 광고 삽입할 시작 시간 - HH:MM:SS (str) 3. 아이디어 정리 누적합으로 해당 구간에 몇 명이 시청하는지 구한다. 초 ..