코딩개발로 물장구치는 개발자

안녕하세요 Dibrary입니다. 이번에는 이분탐색을 사용해야 풀 수 있는 문제를 정리해보겠습니다. 저에게 이 문제는 처음에 이해하는데 굉장히 시간이 오래 걸린 문제여서.... 정리를 꼭 해둬야겠다 생각했죠. 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 먼저 문제를 보고 어떤 방법으로 이분탐색을 해야 하는지 감을 잡지 못했습니다. 정확히는 '다른 풀이를 보고서도 이해가 안되었다' 가 더 맞는 표현같네요. 지금은 다른 풀이를 이해한 부분만 정리해보면 아래와 같습니다. 1. 대부분..

안녕하세요 Dibrary입니다. 이번에 정리할 문제는 백트래킹을 사용해서 풀어야 하는? (백트래킹을 쓰기 좋은) 문제입니다. 개인적으로 백트래킹을 좀 어려워해서 정리해두고자 합니다. 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제를 보자마자 처음 든 생각은 '사용한 숫자를 또 쓸 수 있다니' 였습니다. 즉, 사용한 숫자와 사용하지 않은 숫자의 구별을 할 필요가 없는 셈이죠. 이 문제를 풀 때 중요한 것은 '길이를 맞추는 것'과 '만들 수 있는 모든 경우'를 구해야 하는 것이죠. 길이 맞추는거야 갯수 ..

안녕하세요 Dibrary입니다. 이번에는 시간초과때문에 온갖 머리를 쥐어짰던 문제를 정리해보고자 합니다. 어휴 =_=;; (뭐 덕분에 Counter를 알게 되었으니까 다행이죠) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제는 간단합니다. 그저 평균, 중앙값, 최빈값, 범위 만 구하면 됩니다. 그 와중에 혹시라도 시간초과 걸릴까봐 (너무 쉬운거 같은 문제는 꼭 이런게 걸려있곤 해서 말이죠) 미리 아이디어를 좀 짰었습니다. 값 받으면서 미리 정할 수 있는게 뭐 없을까? 최대값, 최소값은 값을 받으면서 미리 확인해 나갈 ..

안녕하세요 Dibrary입니다. 문제를 풀 때 알고리즘을 잘 알고 있는 것도 중요하지만, 아이디어의 중요성? 을 다시 한 번 깨닫게 된 문제가 있어서 가져와봤습니다. 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 딱 보면 엄청 간단해 보이죠. 네 알고리즘 풀이에 어느정도 익숙한 분이라면 바로 풀 아이디어가 떠오르실 겁니다. (전 아니지만요... ㅠ.ㅜ) 제가 생각한 아이디어는 아래와 같습니다. 모든 점을 지나면서 행과 열을 확인하고, 둘 중에 X가 하나도 없는 지점에서 X를 추가한다. 모든 점을 ..

안녕하세요 Dibrary입니다. 이번에는 흔히 '투 포인터' 를 써서 풀어야 하는 문제를 정리해보겠습니다. 이번 문제는 단순히 합을 구하는 것입니다. 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 우선 이 문제를 처음 보았을 때, '투 포인터'라는 개념 자체도 몰랐었습니다. 그래서, 가장 먼저 떠오른 생각은 '완전 탐색'이었죠. 문제는, N이 1000만까지 주어질 수 있는데, 그러면 1개씩 전부 끝까지 진행해보고, 2개씩 전부 끝까지 진행해보고, 3개씩 ... N-1개는 안되겠지만 이런..

안녕하세요 Dibrary입니다. 이번에는 위상정렬을 사용해야 하는 문제를 정리해보겠습니다. 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 예제 입력을 먼저 확인해보겠습니다. 1번째는 10 -1 즉, 10이라는 시간이 소요되고 1번째 노드로 들어오는 노드(먼저 지어져야 하는 건물)는 없다는 것입니다. 2번째는 10 1 -1 즉, 10이라는 시간이 소요되고 2번째 노드로 들어오는 노드는 1노드만 있다는 것입니다. 3번째는 2번째와 같고, 4번째는 4 3 1 -1인데 4라는 시간이 소요되고 4번째 노드..

안녕하세요 Dibrary입니다. 이번에는 백준의 12891번 문제를 통해 '슬라이딩 윈도우'방법을 알아보겠습니다. 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 위 문제는 사실 모든 경우의 수를 따져보아도 구할 수 있습니다. 문제는, 주어진 문자열의 길이가 100만까지 가능하니까 해당 방법은 쓸 수 없다는 것이죠. 그러면 '모든 경우의 수를 따지지 않아도 될까?' 라는 생각이 떠오르실텐데, 네. 가능합니다. 문제에 이런 조건이 있기 때문이죠, 위 예시를 통해 뽑을 때, 항상 '순서대로 ..

안녕하세요 Dibrary입니다. 알고리즘을 풀다보면 꼭 마주하는 문제들이 몇 개 있습니다. 소수, 최소공배수, 최대공약수 등등... 중고등학교때는 그저 술술 풀었지만, 코딩으로 하자니 막상 숨이 턱. 막히는 그런 개념들이죠. 그 중에 이번에는 '소수'를 구하는 코드를 정리해보겠습니다. 대표적인 문제로는 아래 문제가 있습니다. 대놓고 소수 구하기 라고 하죠 . 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 우선, 소수란 '자기 자신과 1만을 약수로 갖는 수' 입니다. 예를 들어보죠, 2는 1과 2만을 약수로 가집니다. 소수죠. 3도 1과 3..

안녕하세요 Dibrary입니다. 이번에는 이진탐색을 사용해서 풀어야 하는 문제를 정리해보겠습니다. 처음에 나름 알머리 굴리다가 시간초과로 실패를 겪은 문제입니다. 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제를 처음 보자마자 떠오른 생각은 아래와 같습니다. M만큼만 자르면 된다. (이걸 반복문에서 캐치해야 할 것 같다.) M만큼 자르는 M-1 포인터를 for문으로 돌리면 어떨까. 근데 2번에서 생각해보니 거의 100000! 번에 가까운 연산이 이뤄질 수도 있다는 생각이 들어서 위 방법은 곧바로 포기 했습니다...

안녕하세요 Dibrary입니다. 이번에는 제가 BFS/DFS에 아주 약간? 자신감이 생겨서 도전했다가 몇 시간을 .. 날려버린 문제를 정리해보겠습니다. 알고보니 BFS/DFS같은 그래프 풀이방법 만 쓰는 게 아니라, 여기에 모든 경우의 수 까지 같이 확인해야 하는 문제였어서 처음 접한 저는 매우 어려웠었습니다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음에 문제를 보고 곧바로 "BFS를 쓰믄 되겠다! " 라는 생각이 제일 먼저 떠올랐습니다. 왜냐하면, 문제에서 "바이러스는 퍼져나갈 수 있다" 라고 나왔기 때문이죠...