기록

문제https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4programmers.co.kr풀이간단한 다익스트라dfs & bfs 방식으로 각 노드를 탐색한다.중복을 체크하는 방식dfs & bfs 방식과 이 부분만 다르다지금의 방식이 이전보다 비용이 적게 들때만 탐색을 계속한다.개선된 다익스트라간단한 다익스트라에 탐색할 노드를 선정하는 방식이 개선되었다.최소 heap을 사용하여 가장 적은 비용이 드는 노드부터 검증한다.플로이드 워..

문제https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한programmers.co.kr풀이각 leaf node에서 가중치를 부모 노드로 옮긴다.이 과정을 leaf 노드가 사라질 때까지 반복한다. 시간초과dfs 나 bfs를 이용해서 모든 노드를 탐색하도록 했으나, 시간초과로 대부분의 테스트 케이스에서 통과하지 못했다. leaf node를 제거하면, 그 부모가 leaf node 후보가 되므로, 부모가 가진 간선개수를 이용해서 다음에 ..

문제 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 풀이 직전 노드의 방향 저장 자동차의 방향이 변경되지 않으면 100원, 자동차의 ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 1) two pointer 리스트를 직접 뒤집거나, 특정 원소를 제거하면 수행 시간이 오래 걸리므로 다른 방법을 생각했다. 리스트 뒤집기 리스트가 뒤집어 졌는지 여부를 저장하는 변수를 하나 두어, R이 나올 때 마다 이 값만 갱신했다. 원소 제거하기 리스트가 뒤집어지지 않았다면 왼쪽에서 원소를 꺼내고 리스트가 뒤집어졌다면 오른쪽에서 원소를 꺼낸다. (deque를 활용해도 된다.) 직접 리스트를 수정하지 않고, start point와 end p..

문제https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0programmers.co.kr풀이문제 풀이 방식을 간단하게 표현하면 아래와 같다.1. table에서 모든 퍼즐조각을 찾는다.2. game_board에서 모든 퍼즐..

문제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이 될때 탐색을 멈추도록 하면 해..