케이스윔의 개발 블로그

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

문제서쪽의 N개의 사이트, 동쪽의 M개의 사이트가 주어질 때 다리를 놓을 수 있는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1010) 풀이꽤 간단한 문제인데 (혼자) 함정아닌 함정에 빠져서 1시간정도 걸린 문제입니다. 동쪽에 M개의 사이트로 N개의 다리를 놓는 경우의 수이고 모든 다리는 똑같이 생겼을 것이기 때문에 조합의 수와 같다고 할 수 있습니다. 처음에 생각을 하지 않고 풀었는지 이 문제가 dp일까? 하면서 조합을 구하는 공식 n!/k!(n-k)! 을 바로 적용해버렸습니다. 테스트케이스는 올바르게 나왔지만 신중히 제출하기 위해 질문검색을 찾아보니 바로 오버플로우가 나는 것을 알 수 있었습니다. N, M이 30이하이지만 30!만 해도 ..

문제N개의 원소를 가지는 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 크기를 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/11053) 풀이DP를 통해 풀 수 있는 문제입니다. DP문제는 생각이나 구현면에서 다른 알고리즘에 비해 시간이 적게 걸린다는 장점이 있어서 요즘 공부를 하다가 집중이 안될 때 풀고 있는 중입니다! 풀이를 안적어도 될 정도로 간단한 문제들이 많지만 오랜만에 적어보겠습니다. 이 문제에서는 수열이 주어지고 가장 긴 증가하는 부분 수열을 구해야하기 때문에 두조건을 만족하는 경우 큰수가 dp배열에 저장될 수 있도록 했습니다. nums[i], dp[i] 라는 배열을 만들었고 nums에는 입력받은 값이 들어가있습니다. dp[i]의 값은 n..

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

문제K개의 랜선을 잘라서 N개의 같은 길이의 랜선을 만드시오. 이 때 만들 수 있는 최대 랜선의 길이를 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1654) 풀이 이분탐색의 감을 익혔다고 생각하고 더 어려운 문제를 골랐더니 잘 못풀겠어서 한번 더 복습하기 위해 이 문제를 골랐습니다. 여느 이분탐색 문제처럼 보였고 앞에서 풀던대로 틀었더니 너무 틀렸습니다를 많이 받았습니다. 이분탐색을 하며 mid 값으로 랜선을 잘랐을 때 같은 길이의 랜선이 몇개가 되는지 확인을 하고, N개보다 많다면 더 길게 잘라주도록 범위를 수정하고 더 적다면 더 짧게 잘라주도록 합니다. 알고리즘 자체는 이분탐색을 써주면 되는데 입력되는 범위가 크다보니 오버플로우를 잘 체크해줘야합니..

문제 다람쥐가 도토리를 뺏기지 않기 위해 숨기는 문제입니다.(귀여워) N개의 상자가 있을 때 임의의 규칙에 의해서 차례대로 도토리를 상자에 채워나가야하는데 마지막 도토리가 들어가는 상자의 번호를 출력합니다.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/15732) 풀이저는 이 문제가 이분탐색로 접근해야한다는 것을 알고 푼 문제인데 아니라면 처음 접근하기가 어려웠을 것 같습니다. 문제의 규칙은 어렵지 않아서 하나씩 다 해보면 되지않을까하는 생각도 들지만 개수의 범위가 매우 크기때문에 도토리 하나씩 넣기에는 힘들거라 생각이 들었습니다. (범위가 크기 때문에 long long 타입을 써야합니다.) 이분탐색을 어떻게 적용해볼 수 있을까? 고민을 해보고 줄여나가는 범위가 상..