케이스윔의 개발 블로그

문제 상근이는 20병의 맥주를 가지고 있고 50미터에 한 병씩 마시며 목적지에 도착해야한다. 출발지와 목적지 사이에 맥주를 파는 편의점이 주어질 때 상근이가 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9205) 풀이처음에 문제를 봤을 때는 주어지는 좌표도 너무 넓어서 50으로 나눠서 관리를 해줄지.. 등의 생각이 많이 드는 문제였는데 하나의 힌트로 쉽게 해결할 수 있는 문제였습니다. 편의점을 통해서 그래프를 그리는 것입니다. 처음에 20병으로 시작하게되고 어느 편의점을 들리던지 먹은만큼 맥주를 살 수 있기 때문에 편의점에 들리게 되면 20병으로 다시 채워집니다. 남은 병수와 관계없이 20병안으로 편의점을 ..

문제2차원 배열로 빙산이 주어졌을 때, 1년이 지날 때마다 0인 바닷물과 인접한 만큼 빙산의 높이가 줄어든다. 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2573) 풀이정답율이 낮은 문제여서 어려울 줄 알았는데 빙산을 녹이는 부분, BFS(또는 DFS)를 통해서 빙산의 덩어리가 두덩어리로 나누어질 때를 확인해주면 되는 문제입니다. 처음엔 이중 for문을 통해서 각 칸에서 빙산이라면 얼마나 녹아야하는지를 탐색하려했는데 빙산이 아닌 부분(0인 곳)이 많을 경우에는 시간이 많이 걸릴 것 같아서 처음 입력을 받을 때 queue를 통해서 따로 빙산을 저장해줬습니다. 그 다..

문제 케빈 베이컨의 법칙은 모든 사람들이 서로 아는 사람 6단계 이내로 거쳐서 연결될 수 있다는 법칙입니다. N명의 사람이 주어졌을 때 자신을 제외한 모든 사람 각각과 연결된 합을 구한 것을 케빈 베이컨의 합이라고 하는데 최소 합을 가지는 사람의 번호를 출력하면 됩니다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1389) 풀이간단하게 BFS를 통해 풀 수 있는 문제입니다. 무조건 6단계 이내로 연결되기 때문에 BFS 탐색을 위한 큐가 비었을 때는 다른 사람과 몇단계를 거쳐서 연결되었는지 알 수 있게 됩니다. BFS를 사람수만큼 반복해주면 각 사람마다 연결된 합을 구할 수 있습니다. 코드https://github.com/kswim/Algorithm/blob/ma..

문제 0은 비어있는 칸을 의미하고, 1~9까지 적힌 3*3 배열이 들어왔을 때 비어있는 칸으로 인접한 숫자들을 이동시키며 1, 2, 3, 4, 5, 6, 7, 8, 0 과 같은 정렬된 상태를 만드시오. 이 때 최소한의 이동횟수를 출력하고 만약 불가능하면 -1을 출력하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1525) 풀이최소한의 이동횟수를 구해야하므로 큐를 사용해서 BFS를 써야겠다고 생각했습니다. 그런데 한번 큐를 pop했을 때 가능한 이동이 최대 4번인데 이 때 모든 이동했을 때마다 각 배열을 어떻게 저장해둬야할지 고민됐습니다. 일단 문제를 풀어보고자 struct 에서 3*3 배열을 선언해주어서 큐에 넣어봤습니다. 수행하다보니 큐사이즈가 엄청 커지게 ..

문제숫자 A, B가 주어질 때 주어진 4개의 명령을 최소한으로 적용시켜 A를 B로 변환해야합니다. 최소한으로 필요한 명령어 나열을 출력해야합니다. 문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9019) 풀이최소한의 명령을 통해 변환해야하므로 BFS를 통해서 큐에 넣으면서 한단계동안 수행할 수 있는 숫자를 만들어봅니다. D, S, L, R 각 명령어를 수행하는 함수를 만들었고, 큐에서 pop한 값을 차례대로 넣으면서 새로운 숫자가 만들어지면 해당하는 숫자를 또 큐에 넣습니다. 만약 최소한의 명령개수를 구하는 거라면 더 쉽게 생각할 수 있었을텐데 해당 명령어를 나열하는 것이 답이기 때문에 조금 고민을 했습니다. 큐에서 pop한 수를 4개의 명령어를 다 수행시켜보고 변..

문제아기 상어와 물고기들이 존재하는 공간이 주어지고, 아기 상어는 물고기를 먹으며 크기를 증가시키는데 조건에 맞춰서 먹을 수 있는 물고기가 있고 커지는 조건이 있다. 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하는 문제이다.출처: 백준 온라인 저지 https://www.acmicpc.net/problem/16236 풀이아무리 풀어봤더라도 잘 이해하고 넘어갔는지가 중요한 거니까 오랜만에 풀이를 남긴다. 이 문제 처음에 봤을 때는 당황스러웠다. 꽤 복잡해 보였고, 이렇게 풀어도 되나? 하는 몇 가지 방법만 떠올랐는데 그 방법을 정리해서 푸니 풀렸다. 우선 아기 상어는 처음 크기가 2이고, 자신보다 작은 크기의 물고기만 먹을 수 있다. 그리고..

문제 정의로봇 청소기의 주어진 작동방법을 통해서 청소하는 영역의 개수를 구하는 프로그램을 작성하는 것이다.로봇 청소기는 다음과 같이 작동한다.현재 위치를 청소한다.현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며,..

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이 때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이 때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 및 출력첫째 줄에 N(1≤N≤1,000), M(1≤M≤1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0..