오뚝이개발자

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

문제 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으..

문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 나의 풀이 최단 경로를 찾는 BFS와 DP가 합쳐진 유형의 문제이다. 처음엔 DF..

문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 나의 풀이 처음엔 그냥 2중 for문을 써서 각 시작점마다 보석 종류를 모두 포함하는 끝지점을 검출하면 break하고 다음 시작점부터 탐색하는 알고리즘을 짰는데 역시나 시간초과에 걸렸다. 개선한 풀이는 다음과 같다. start, end의 투포인터를 사용한다. 처음엔 둘다 0번째 인덱스로 초기화 한다. start부터 end까지의 보석이 전체 보석 종류를 포함하면 start를 증가시키고, 모자라면 end를 증..