오뚝이개발자

문제 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 나의 풀이 뭔가 그래프 문제라서 복잡한 알고리즘을 써야할 줄 알았는데 생각보다 간단하게 해결했다. 자식-부모의 pair로 이루어진 dictionary를 활용해 반복적으로 돈을 분배하면 된다. 이 때 반복문의 종료 조건은 center까지 도달해 분배가 끝나거나 혹은 나눌 돈의 10%가 1원 미만(문제에서 주어진 종료조건)이다. 문제의 조건에서 10%를 ..

문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 나의 풀이 위상 정렬을 사용해 푸는 대표적인 문제이다. 위상 정렬의 개념을 모르겠으면 이 글을 참조하기 바란다. 코드 # https://www.acmicpc.net/problem/2252 n, m = list(map(int, input().split())) # adjacent list adj_list = [[] for _ in range(n+1)] ..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 나의 풀이 DFS와 DP가 합쳐진 유형의 문제이다. 시작지점이 정해진 것이 아니므로 각 지점을 시작지점으로 했을 때 최장거리를 계산해 이들 중 다시 가장 큰 값을 답으로 출력하는 문제이다. 그냥 단순히 모든 지점을 시작점으로 해서 DFS로 탐색해도 되지만 이미 했던 연산을 중복해서 계산하므로 시간초과가 난다. 따라서 DP를 사용해 해당 지점을 시작점으로 했을 때 갈 수 있는 최장경로..

문제 https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 나의 풀이 브루트 포스 문제이다. 생각보다 어려웠던 것 같다. 중요하게 고려해야 할 것은 크게 두 가지이다. 1. 외벽은 원형으로 이루어져 있는데 주어진 weak 리스트가 그것을 반영하지 못한다. -> weak 리스트 배열의 길이를 2배로 늘려서 해결. 예컨대, weak = [1,5,6,10], n=12라면 weak_point = [1,5,6,10,13,1..

문제 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 나의 풀이 dp를 사용하면 되는 문제이다. 케이스는 두 가지이다. 첫 번째 스티커를 사용하는 경우와 사용하지 않는 경우이다. 따라서 dp1,dp2 두 개의 dp 배열을 만들어 저장하면 된다. dp1의 경우 첫 번째 스티커를 사용하므로 dp1[0] = sticker[0], dp1[1] = dp1[0]이다. dp2의 경우 첫 번째 스티커를 사용..

문제 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 나의 풀이 플로이드 와샬 알고리즘을 사용해 중간에 k 지점을 통과할 때 비용을..

문제 https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 나의 풀이 처음엔 2차원 배열을 사용해 문제를 풀려고 했지만 생각해보면 각 상..

문제 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 나의 풀이 그냥 문제에서 주어진 대로 1명이 지나갈 때마다 디딤돌의 수에서 -1 해주면 O(n^2)으로 시간초과가 난다. 문제의 주어진 조건에서 보면 디딤돌의 수는 1이상 200000000이하의 자연수이므로 정답의 범위는 1이상 200000000이하라는걸 알 수 있다. (모든 디딤돌 수가 200000000이면 200000000명이 건널 수 있으니까) 이처럼 선형자료의 탐색을 할 때는 시간을 줄이기 위해 이분탐색을 사용하면 좋다. l, r 을 각각 1과 200000000으..