전체 글

백준🔗 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 간단 풀이 간단한 1차원 dp 문제이다. dp[i] : i원을 만들 때 사용하는 동전의 개수 위와 같이 정의하고, 주어진 n가지 동전 각각을 쓰거나 or 쓰지 않거나의 경우를 모두 비교해서 최소 개수로 k원을 만드는 경우를 찾는다. 한 가지 주의해야 할 점은, 처음에 dp배열을 Integer.MAX_VALUE로 초기화 했는데, 계산 과정에서 dp[i - coin[j]] + 1 이렇게 1을 더하게 되기 때문에 Integ..

백준🔗 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 간단 풀이 요새 백준 문제집 '삼성 SW 역량 테스트 기출 문제'에 있는 문제들을 푸는 중이다. 아무래도 구현 문제가 많은 것 같은데, 오늘 문제도 문제에서 주어진 조건에 따라 차근차근 구현해 나가니 쉽게 풀 수 있었다. 그래서 따로 풀이를 적을 내용은 없는 것 같지만, 한 가지만 얘기해보자면 문제에서 입력 부분에 '방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 ..

백준🔗 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 간단 풀이 문제 상황 자체는 쉬웠는데 안쪽에 있는 공간과 바깥에 있는 공간을 어떻게 구분해야 할 지 고민이 됐다. 그래서 생각해낸 풀이는 1) BFS를 수행하며 치즈 바깥 공간을 -1로 바꾼다. 2) 가장자리에 있는 치즈를 찾아서 2로 바꾼다. (2차원 배열을 전부 탐색하며 상하좌우로 -1이 하나라도 있으면 가장자리 치즈라고 판단) 3) 다시 한 번 전체 탐색을 하며 2를 -1로 바꾸면서(가장자리에 있는 치즈 녹이기) 1인 개수를 세서 남은 치즈 조각을 카운트한다. 4..

백준🔗 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 간단 풀이 오랜만에 구현 문제를 풀어봤다!! 문제를 읽어보니 (1) 회전 (톱니바퀴 상태 값들 전부 한 칸씩 이동시키기) (2) 인덱스로 접근 (맞닿은 톱니바퀴 값 비교 & 마지막에 점수 계산) 이렇게 2가지 연산이 주로 필요해 보였다. 톱니바퀴 개수가 4개이고, 톱니바퀴 당 값이 8개씩이기 때문에 자료구조로 배열을 사용해도 1번이 O(8), 2번이 O(1)로 둘 다 상수 시간만큼 소요될 것이라고 생각했다. 리스트도 고려해 봤지만, 인덱스로 접근해..

백준🔗 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 간단 풀이 흐어 요새 싸피가 2학기 개강을 앞두면서 프로젝트 마무리, 2학기 준비 등등 이래저래 정신없이 바빠져가지구 며칠 포스팅을 못했다ㅠㅠ 오늘도 부랴부랴 간단한 트리 BFS 문제로 가져와봤다..!! 맥주 한 병에 50m씩 갈 수 있고, 한 박스에는 맥주가 20개 있기 때문에 다음 경유지까지의 거리가 1000m 이내이면 이동이 가능하다. 따라서 집에서부터 페스티벌까지 가는 길에 거리가 1000m 이하인 편의점들을 선택했을 때 페스티벌에 도착..

백준🔗 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 간단 풀이 DFS를 할 때 방문처리를 하기 위한 boolean배열 하나와 사이클이 형성되는지 여부를 체크하는 boolean 배열을 하나 더 만드는 것이 이 문제의 핵심이라고 할 수 있다. 문제에서 학생들의 선택에서 사이클이 발생하게 되면 그 사이클에 포함되는 학생들은 한 팀으로 배정된다. 따라서 모든 경우에 대해 DFS를 수행할 필요 없이, 진행 경로에 사이클이 있음을 알 수 있다면 더이상..

백준🔗 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 간단 풀이 아주아주 오래만에 풀어보는.. 백트래킹!! 그래서 백트래킹 개념을 일단 정리하고 가보자. 백트래킹 여러 가지 선택지 옵션들이 존재하는 상황에서 한 가지를 선택한다. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다. 이런 선택을 반복하다 보면 최종 상태에 도달한다. 즉, 해결책으로 이어질 것 같지 않으면 더이상 그 경로를 따라가지 않음으로써 시도 횟수를 줄여나가는 방식 (가지치기) 백트래킹 vs DFS DFS는 모든 경로를추적하고,..

백준🔗 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 간단 풀이 별들을 최소 비용으로 모두 잇는 문제이기 때문에 최소 스패닝 트리(MST)로 생각하고 접근하면 된다. 다만, 간선이 미리 주어지는 것이 아니라 어떤 정점이든 모두 이을 수 있다는 것이 이전에 풀었던 문제들과 다른 포인트인 것 같다. 따라서 크루스칼과 프림 중 프림 방식을 선택했다. 이전 포스팅 (👉 2023.06.16 - [알고리즘/백준] - [백준/JAVA] 1197_최소 스패닝 트리) 에서도 얘기했듯이 크루스칼은 최소 비용의 '간선'을 ..