기록

문제https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]programmers.co.kr풀이Two Pointer Algorithmstart pointer, end pointer 두 개를 설정해 조건에 따라 늘려간다. 간단하게 적어보면 아래와 같다. 1. start~end 구간 내 모든 보석이 포함되어 있다면start pointer를 오른쪽으로 1칸 옮겨 구간을 좁힌다.2. 아니라면end pointer를  오른쪽으로 1칸 옮겨 구간을 넓힌다.더보기더보기결과 > 시간초과def solution(gems)..

문제https://programmers.co.kr/learn/courses/30/lessons/87377 코딩테스트 연습 - 교점에 별 만들기[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, -programmers.co.kr풀이1. 교점 구하기참고로 주어진 식을 이용한다. 2. 교점의 가장 큰/작은 x, ..

문제https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후,programmers.co.kr풀이1. 서로소 집합 자료 구조 (Disjoint-set data structure)tree 구조이므로 서로소 집합 자료 구조 (Disjoint-set data structure) 또는 Union-Find 알고리즘을 응용하여 사용한다.2. 시간초과case11, csae12, case13에서 시간초과가 발생했다. 남은 이익이 0이 될때 탐색을 멈추도록 하면 해..

문제 https://programmers.co.kr/learn/courses/30/lessons/87946?language=python3 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 풀이 깊이 탐색 root_node = [지나간 던전들의 index, 잔여 mp, 지나간적 없는 던전들의 index] stack = [root_node] 1) answer에 지금까지 지나온 던전 수의 최대값을 저장한다. 2) 모든 던전을 다 지났다면, 탐색을 종료한다. 3) 지나간적 없는 던전 중 조건에 맞는 던전이 있다..

문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 이 문제는 DFS와 BFS 2가지 방법으로 모두 풀이 가능하다. 그래프의 크기가..

문제 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 풀이 Linked List 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당 # Linked List nodes = {i:[(i+n-1)%n, (i+1)%n] for i in range(n)} 삽입 Z 삭제 C 어려웠던 부분 1. 되돌리기 되돌리기를 할 때 링크드 리스트 전체를 stack에 저장했다. 그..

보호되어 있는 글입니다.

문제 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 풀이 N개의 스티커가 원형으로 연결되어 있으므로 (1) 첫번째 스티커가 쓰이는 경우와 (2) 첫번째 스티커가 쓰이지 않는 경우로 나누어서 생각해야 한다. (1) 첫번째 스티커가 쓰이는 경우 dp에는 0번째 스티커를 사용하고 1번째 스티커를 사용하지 않은 경우 i까지의 최대 값을 저장한다. dp[i-1] : i번째 스티커를 사용하지 않음 dp..