본문 바로가기
반응형

전체 글123

백준 14503번 : 로봇 청소기 java 이 문제는 주어진 조건에 맞게 코드를 만드는 문제입니다. 그림을 통해서 이 문제에 대한 설명을 드리도록 하겠습니다. 위의 그림과 같이 자료가 주어졌다고 가정해보도록 하겠습니다. 또한 로봇 청소기가 있는 위치는(1, 2)로 주어졌고, 방향은 2인 남쪽이 주어졌다고 하겠습니다. 이를 지도 위에 나타내 보겠습니다. 그럼 위의 그림과 같은 모양이 됩니다. 이때 문제의 1번 작업을 해줍니다. 청소한 위치는 빨간색으로 표시하겠습니다. 1번 작업을 하였으니 이제 2번 작업을 실행시켜 줍니다. 로봇은 남쪽을 바라보고 있었으니 이 로봇의 왼쪽은 동쪽이 됩니다. 로봇의 동쪽에는 청소하지 않은 구역이 있고 벽이 아니니 이 방향으로 이동시켜줍니다. 위와 같은 그림이 됩니다. 1번 작업을 통해 현재 있는 칸을 청소해준 다음 2.. 2022. 6. 16.
백준 2294번 동전 2 java 이 문제는 다이나믹 프로그래밍을 이용하여 동전과 가치의 합이 주어질 때 동전의 개수가 최소가 될 때를 찾는 문제입니다. 이 문제는 아래의 문제와 비슷한 풀이로 풀 수 있으니 아래의 문제를 보고 오시는 것을 추천드립니다. 백준 2293번 : 동전 1 java 이 문제는 다이나믹 프로그래밍을 이용하여 N개의 동전을 이용하여 K원이 되게 하는 경우의 수를 구하는 문제입니다. 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 dy-coding.tistory.com 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 동전의 수부터 N원을 만들 때의 동전의 수를 저장해가며 해결하였습니다. 예제 1번을 이용하여 문제를 해결하는 과정을 설명드리겠습니다. cnt[i]는 동.. 2022. 6. 15.
백준 2293번 : 동전 1 java 이 문제는 다이나믹 프로그래밍을 이용하여 N개의 동전을 이용하여 K원이 되게 하는 경우의 수를 구하는 문제입니다. 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 경우의 수부터 N원을 만들 때의 경우의 수를 각각의 동전을 사용할 수 있을 때로 나누어 구해주었습니다. 이에 대해서 예제 1번을 이용하여 자세히 설명드리겠습니다. 위의 예제 1번을 보시면 3개의 동전을 사용하여 가치의 합이 10이 될 때를 구해야 합니다. 우선 cnt 배열의 위에 있는 수는 각 셀에 들어갈 수 있는 가치의 최댓값을 나타낸 것입니다. 이제 코인의 가치 중 가장 가치가 낮은 1원짜리 동전으로만 cnt 배열을 채워보겠습니다. cnt 배열을 채우는 점화식은 cnt[i] = cnt[i] + cnt[i-coin[.. 2022. 6. 15.
백준 1021번 : 회전하는 큐 java 이 문제는 덱 자료구조를 이용하여 어떤 방향으로 연산을 해야 더 효율적으로 자료들을 찾을 수 있는지를 구현하는 문제입니다. 위의 문제에서 1 2 3번 연산을 각각 설명해드리도록 하겠습니다. 위와 같은 덱이 있다고 가정해보겠습니다. 만약 제가 찾아야 하는 수가 2라면 표를 왼쪽으로 한번 움직이는 것이 오른쪽으로 5번 움직이는 것보다 적게 움직입니다. 따라서 위 문제에서 2번 연산을 해줍니다. 2번 연산을 해줭 왼쪽으로 표를 한번 움직여주면 다음과 같은 표가 나옵니다. 덱의 맨 앞에 찾고자하는 수인 2가 왔으므로 1번 연산을 해서 2를 덱에서 제거해주도록 하겠습니다. 그럼 다음과 같은 그림이 나옵니다. 이제 6을 찾아보도록 하겠습니다. 6이 현재 있는 인덱스는 3번입니다. 3번에 있는 값을 0번으로 가져오기.. 2022. 6. 15.
백준 1158번 : 요세푸스 문제 java 이 문제는 자료 구조의 일종인 큐를 이용해서 요세푸스 순열을 구하는 문제입니다. 요세푸스 순열이란 K번째 사람을 제거해주면서 제거된 순서대로 출력하는 문제입니다. 이를 표로 조금 더 이해하기 쉽게 나타내겠습니다. 위 표를 보시면 어떤 순서로 사람이 제거되고 제거된 다음에는 배열이 어떻게 남아 있는지를 확인하실 수 있습니다. 저는 이 문제를 해결하기 위해서 큐를 사용하였습니다. 우선 큐에 사람들을 순서대로 넣습니다. 그리고 K번 만큼 뒷사람을 찾아갑니다. 뒷사람을 찾아가면서 지나친 사람들은 pop한 후 다시 offer해서 맨 뒤로 보내줍니다. 찾아간 인덱스에 있는 사람을 pop해서 answer배열에 넣습니다. 이 과정은 N번 반복하면 위의 Output처럼 결과가 나옵니다. 이를 코드로 보여드리겠습니다. i.. 2022. 6. 14.
백준 1197번 : 최소 스패닝 트리 java 이 문제는 최소 비용 신장 트리를 만드는 문제입니다. 최소 비용 신장 트리를 만들기 위한 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 간단히 말해서 전체의 간선 중에서 가장 가중치가 낮은 간선들을 선택해서 최소 비용 신장 트리를 만드는 알고리즘입니다. 그리고 프림 알고리즘은 임의의 정점을 고른 후 그 정점에서 연결된 간선 중에서 가장 가중치가 낮은 간선을 선택하여 최소 비용 신장 트리를 만드는 알고리즘입니다. 저는 이 중에서 크루스칼 알고리즘을 이용하여 이 문제를 푸는 것을 선택하였습니다. 프림 알고리즘에 대한 설명은 아래의 링크에서 확인하실 수 있습니다. 프림 알고리즘 - 위키백과, 우리 모두의 백과사전 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연.. 2022. 6. 14.
백준 17299번 : 오등큰수 java 이 문제는 스택 구조를 이용한 문제로 아래의 문제인 오큰수와 유사한 문제입니다. 이 문제를 풀기 전에 아래의 문제를 보고 오시는게 좋을 겁니다. 백준 17298번 : 오큰수 java 이 문제는 자료구조 중에서 스택을 이용하여 푸는 문제입니다. 이 문제를 풀 때 해당 인덱스의 수보다 오른쪽에 있으면서 해당 수보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾으면 됩니다. 이를 dy-coding.tistory.com 이 문제에서는 수가 배열에 몇 개가 들어있냐를 기준으로 수를 집어넣습니다. 입력된 자료들을 순회하며 데이터들이 몇 개씩 있는지를 확인한 후 조건에 맞게 정답 배열을 채웁니다. 위의 그림은 위 문제의 예제 1번을 나타낸 그림입니다. data의 개수들은 count배열에 넣었습니다. 이제 stack에 da.. 2022. 6. 14.
백준 11052번 : 카드 구매하기 java 이 문제를 처음 봤을 때 저는 어떤 방식으로 문제를 해결해야 할까가 의문이었습니다. 1장짜리 카드팩으로만 N개를 살 수도 있고 1장짜리 카드팩에 2장짜리 카드팩을 몇 개 섞을 수도 있습니다. 이 모든 상황들을 백트래킹으로 풀기에는 너무 많은 시간이 걸리기 때문에 시도하기 어려웠습니다. 그래서 이 문제의 분류를 보니 다이나믹 프로그래밍이였습니다. 이렇게 경우의 수가 많아 보이는데 어떻게 다이나믹 프로그래밍으로 문제를 해결해야 하나 고민을 하다가 살 수 있는 카드의 개수에 따라서 dp를 만들면 되지 않을까 생각하였습니다. 그래서 dp[1]은 카드 1개를 살 때로 정하였고 dp[2]는 카드 2개를 살 때의 최대 비용으로 정하였습니다. dp[2]을 정하기 위해서는 2장이 들어있는 카드팩 1개와 dp[1]과 1장.. 2022. 6. 14.
반응형

티스토리툴바