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-08-30 tags: Algorithm DP BFS https://school.programmers.co.kr/learn/courses/30/lessons/67259 문제 요약 2차원 정사각형의 도면이 주어진다. 직선 도로는 100원, 90도로 꺾이는 도로는 500원이 추가로 든다. 길이 N일 때, (0,0)에서 (N-1,N-1) 까지 가는 도로를 설치할 때 최소 비용을 return한다. 문제 풀이 옛날에 시도하였다 실패한 문제이다. Level 3의 문제를 많이 풀었으며, 남은 문제들 풀이에 실패할 경우 어느정도의 텀을 두고 다시 풀어야 하며, 지금이 실패한 문제를 풀기 적절한 시기라고 판단하였다. 과거의 풀이에 문제가 있어 실패를 하..

title: Programmers - 블록 이동하기 date: 2022-08-11 tags: Algorithm BFS https://school.programmers.co.kr/learn/courses/30/lessons/60063 문제 요약 2 x 1 크기의 로봇을 좌상단에서 우하단까지 이동한다. 상하좌우 이동이 가능하며, 차지하는 한 위치를 중심으로 90도 회전이 가능하다. 회전시 벽에 부딪히면 안 되기에 빈 공간이 있어야 한다. 각 행동이 전부 1초가 소모되며 우하단에 반드시 도착할 때, 우하단에 도착하는 최소한의 시간을 return한다. 문제 풀이 일반적인 BFS 문제에서 1 x 1을 차지하던 노드가 2 x 1로 증가, 회전이라는 기능이 추가된 문제이다. 어렵지는 않다. 단지 회전 처리가 많이 귀..

title: Programmers - 퍼즐 조각 채우기 date: 2022-08-04 tags: Algorithm BFS https://school.programmers.co.kr/learn/courses/30/lessons/84021 문제 요약 퍼즐 조각을 보드의 빈 공간에 딱 맞게 집어넣어야 한다. 조각은 회전만 가능하며, 뒤집을 수 없다. 조각을 최대한 넣었을 때, 몇 픽셀이 채워지는지 return한다. 문제 풀이 난이도가 높은 구현 문제이다. 생각해야 하는 부분이 많았으며, 적절한 알고리즘을 생각하더라도 구현에서 꽤 시간이 걸렸다. 개인적으로 정말 재밌게 푼 문제이다. 보드판과 퍼즐은 서로 다른 구역에 존재하나, 구역의 크기와 형태는 동일하다. 이는 보드판의 빈 자리, 혹은 퍼즐을 찾는 알고리즘은..

title: Programmers - 경주로 건설 - 포기 date: 2022-07-24 tags: Algorithm DP DFS BFS https://school.programmers.co.kr/learn/courses/30/lessons/67259# 문제 요약 2차원 정사각형의 도면이 주어진다. 직선 도로는 100원, 90도로 꺾이는 도로는 500원이 추가로 든다. 길이 N일 때, (0,0)에서 (N-1,N-1) 까지 가는 도로를 설치할 때 최소 비용을 return한다. 문제 풀이 이틀간 이 문제만 계속 시도하였다. 계속하여 정확성 56점에서 실패하며, 테스트 케이스 및 여러 AC 프로그램을 살펴보았으나 도대체 뭐가 문제인지 알아낼 수 없었다. 포기하고 나중에 다시 풀 계획이다. DFS 시도 - BF..

title: Programmers - 전력망을 둘로 나누기 date: 2022-06-26 tags: Algorithm BFS https://programmers.co.kr/learn/courses/30/lessons/86971 문제 요약 Tree 구조로 이루어진 전력망이 존재한다. 전선을 하나 끊어 두 전력망으로 나누는데, 두 전력망의 개수가 가장 비슷하도록 나누었을 때의 개수 차이를 return한다. 문제 풀이 송전탑의 개수는 100개가 최대이다. Tree 구조이기에 전선의 개수는 99개가 최대이며, 최악의 경우 전선 99개 * 송전탑 전체 탐색 100회 = 9900회의 탐색이 이루어진다. 횟수가 별로 많지 않으므로 주어진 데이터를 그대로 이용한다. 만약 n의 최대치가 100이 아닌 10k, 100k ..