Dot Dot Line Dot

title: Programmers - 카드 짝 맞추기 date: 2022-11-01 tags: Algorithm DFS BFS https://school.programmers.co.kr/learn/courses/30/lessons/72415 문제 요약 4x4 격자에 쌍을 이루는 카드가 배치되며, 초기 위치가 주어진다. 카드 선택과 한 칸 이동, 한 방향으로 카드 혹은 격자 끝에 도달하는 행동은 조작 횟수 1회로 판단한다. 카드 쌍이 선택이 되면 해당 쌍이 삭제가 된다. 모든 카드 쌍을 지우기 위한 최소 조작 횟수를 return한다. 문제 풀이 솔직히 어렵지는 않고, 많이 귀찮은 문제였다. 격자의 크기는 4x4, 카드는 최대 12개가 주어진다. 2개가 하나의 쌍이기에 최대 6! * 2^6으로 약 46K의 ..

title: Programmers - 금과 은 운반하기 date: 2022-10-30 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/86053 문제 요약 각 도시에 금과 은, 트럭이 존재한다. 각 트럭 운행에 소요되는 시간은 편도이며, 최대 하중만큼만 실을 수 있다. 요구하는 금과 은을 모두 운반할 때 걸리는 최소의 시간을 return한다. 문제 풀이 1-2개월전에 풀어보려고 하였으나, 알고리즘을 구상할 수 없어 계속 미루다 드디어 문제에 도전하였다. 처음에는 DP 혹은 구현 문제인줄 알았으나, 문제를 잘 파악하면 다른 방식으로 풀어야 하는 것을 알 수 있다. 트럭의 개수가 정해져있다면 효율적으로 운용해야 하기에 앞의 ..

title: Programmers - 등대 date: 2022-10-29 tags: Algorithm DP https://school.programmers.co.kr/learn/courses/30/lessons/133500 문제 요약 Cycle이 없는 Graph가 주어진다. 각 Edge의 끝 Vertex중 하나는 불이 켜져있어야 할 때, 최소로 불을 킬 경우에 켜진 Vertex의 수를 return한다. 문제 풀이 최대 Vertex는 100K이며, Edge의 개수는 Vertex - 1 이다. Adjacent Matrix를 사용할 수 없는 문제이다. 처음에는 한 쪽에 불이 켜져있다면 다른 쪽은 무조건 꺼져있으면 되는 줄 알았으나, 예시에 나온것만 봐도 양쪽 모두 불이 켜져있을 수 있다. 한 쪽의 불이 꺼져있..

title: Programmers - 2차원 동전 뒤집기 date: 2022-10-28 tags: Algorithm Greedy https://school.programmers.co.kr/learn/courses/30/lessons/131703 문제 요약 2차원의 직사각형 체스판이 주어지며, 각 칸은 앞면과 뒷면이 다른 동전으로 채워져있다. 열 혹은 행 단위로 뒤집을 수 있을 때, 주어진 동전을 뒤집어 목표 상태를 만들어야 한다. 만들 수 있을 때 최소 뒤집는 횟수를, 못 만들면 -1을 return한다. 문제 풀이 처음에 문제를 봤을 때는 Brute Force 혹은 DFS 등의 방식으로 풀어야 하는줄 알았다. 하지만 각 Row와 Column을 기준으로 뒤집는다는 것에서 풀이 방안을 쉽게 떠올릴 수 있었다..

title: Programmers - 부대복귀 date: 2022-10-25 tags: Algorithm Graph Dijkstra https://school.programmers.co.kr/learn/courses/30/lessons/132266 문제 요약 그래프가 주어지며, 출발 지점의 리스트와 하나의 도착 지점이 주어진다. 각 출발 지점에서 도착 지점까지 가는 경로의 최소 길이를 vector에 넣어 return한다. 경로가 없다면 -1을 넣는다. 문제 풀이 Node의 개수는 최대 100K이며, O(n^2) 이상이라면 TLE가 발생할 것이다. 출발 지점이 모두 달라 Bellman Ford Algorithm을 사용할 수 없다. 하지만 도착 지점이 하나이기에, 이를 역으로 생각하면 도착 지점에서 각 지점..

title: Programmers - 파괴되지 않은 건물 date: 2022-10-18 tags: Algorithm DP https://school.programmers.co.kr/learn/courses/30/lessons/92344 문제 요약 2차원의 행렬에 주어진 명령을 수행하여 값을 변경한다. 명령은 작은 직사각형 구간이 주어지며, 해당 구간의 값을 일정 수치만큼 내리거나 높인다. 모든 명령을 시행한 후, 값이 1 이상이 되는 것들의 개수를 구하여 return한다. 문제 풀이 행렬이 최대 크기일 때 1M개의 셀이 존재하며, 명령은 최대 250K이다. 최대 크기만큼의 명령이 최대 개수만큼 주어질 경우, 모든 셀에 작업을 해준다면 250G라는 말도 안 되는 수치가 나온다. 처음에는 이 부분을 신경쓰지..

title: Programmers - 표 편집 date: 2022-10-17 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/81303 문제 요약 표의 크기와 현재 위치가 주어지며, 주어진 명령을 수행한다. 각 명령의 수행은 문제를 직접 확인하는 것이 빠르다. 주어진 명령을 전부 수행했을 때, 그대로 남아있는 row는 O, 삭제된 row는 X로 문자열을 구성하여 return한다. 문제 풀이 표의 순서가 정해져 있으며, 비어있는 row는 탐색하지 않는 조건 등이 존재하는 문제이다. 적절한 자료구조를 이용하여 표를 구성하는 문제임을 바로 파악할 수 있었다. 처음에는 vector를 이용하였지만, 예상대로 탐색 속도는 빠르더라도..

title: Programmers - 보석 쇼핑 date: 2022-10-13 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/67258 문제 요약 진열대에 있는 보석의 특정 구간을 구매하여 모든 종류의 보석을 구매하려고 한다. 가장 적게 구매할 수 있는 구간을 찾아 시작 번호와 끝 번호만 vector에 넣어 return한다. 문제 풀이 최대 100K이며, 보석의 종류의 개수 제한이 없다. O(n^2)의 경우 최적화를 해야 하는데, 카카오의 문제이기에 O(n) 혹은 O(nlogn)을 의도한 문제라고 판단하였다. 보석을 종류별로 분류한 후, 이 분류한 것들을 순서대로 확인하는 방식으로 문제를 해결하였다. 각 보석을 종류별로..

title: Programmers - 최고의 집합 date: 2022-10-12 tags: Algorithm https://school.programmers.co.kr/learn/courses/30/lessons/12938 문제 요약 자연수 n개로 구성 가능한 모든 집합 중 합이 s가 되며, 그 중 각 원소의 곱이 가장 큰 집합을 구한다. 해당 집합을 오름차순으로 정렬하거나, 만들 수 없다면 -1을 넣어 return한다. 문제 풀이 Level 설정이 잘못된 문제인 것 같다. 우선 n개의 자연수이기에 n solution ( int n , int s ) { vector answer ; if ( s < n ) // Can&#39;t make set return { -1 } ; int iLow =..

title: Programmers - 카운트 다운 date: 2022-10-09 tags: Algorithm DP https://school.programmers.co.kr/learn/courses/30/lessons/131129# 문제 요약 다트의 점수는 1~20과 각 점수는 1배(Single), 2배(Double), 3배(Triple), 50점(Bull)이 존재한다. 점수의 합을 target으로 만들어야 하며, 던진 다트의 수가 제일 적은 것이 best이며, 같은 개수라면 Single + Bull의 값이 가장 큰 것이 좋다. 맞춘 점수의 합을 target으로 만들 때, 가장 적게 던진 다트의 수와 그 때 가장 큰 Single과 Bull의 합을 return한다. 문제 풀이 간단하게 과거의 케이스를 이용..