케이스윔의 개발 블로그

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

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

문제정수 N이 주어졌을 때 M이 정수자릿수라면 1

문제 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개의 명령어를 다 수행시켜보고 변..

문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들의..

DFS는 vector로 구현도 해보고 문제도 몇개풀어봤으니 이제는 queue로 BFS를 구현해보려한다 DFS는 한 우물만 계속해서 파니까 쭉쭉 들어가기위해서 스택이 필요했고, BFS는 짧게짧게 갈 수 있는 모든 곳을 들러야하니까 FIFO(선입선출)인 큐가 필요하다 1. queue의 사용 #include을 해줘야한다queue Q; : int형으로 Q라는 이름의 큐 선언Q.push(값) : 해당값을 큐 Q에 넣는다Q.pop() : 큐 Q의 front를 삭제한다Q.front() : 큐의 제일 앞 값을 리턴한다(삭제되지않음)Q.back() : 큐의 제일 마지막 값을 리턴한다(삭제되지않음)Q.size() : 큐 Q의 원소 개수를 리턴한다 Q.empty() : 큐가 비어있는지를 확인한다. 비어있으면 1 비어있지않으..