데이터의 바다에서 수영하기

Intro 백준 온라인 저지 사이트에서 문제를 풀다보면 기상천외한 개념들을 배우는 경우가 허다하다. solved.ac에서 class별 제시되는 대표 문제 중 CLASS 6으로 분류된 문제를 보면 세그먼트 트리를 활용해 푸는 문제가 잘 나온다. 따라서 여기선 구체적인 문제를 푼다기 보다는 세그먼트 트리가 무엇인지를 개념적으로 기술할 생각이다. 코드는 조금만 검색하면 거의 정형화된 형태로 나와있어서 굳이 여기선 작성하지 않아도 될 것 같다. 행여나 필요하면 차후에 관련 문제들 리마인드용 해설을 적으면서 코드를 기술하려 한다. 대표 문제 2042번 - 구간 합 구하기 https://www.acmicpc.net/problem/2042 11505번 - 구간 곱 구하기 https://www.acmicpc.net/p..

원본 링크 https://programmers.co.kr/learn/courses/30/lessons/42626 Intro 이번 문제에선 힙(Heap)이라는 자료구조를 활용해서 문제를 풀게 된다. 자료구조 관련 강의를 들으면 Tree를 배우면서 후반부에 배우게 되는 구조이다. 뭔가 내용도 복잡해서 잘 안 쓸 것 같아 보이나, 지금과 같이 최대/최소 연산을 주로 하는 경우 효율을 내기 좋다. 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지..

원본 링크 https://www.acmicpc.net/problem/1644 Intro 사실 이 문제는 아래의 두 가지 문제를 풀어봤다면 바로 짜깁기해서 풀 수 있는 문제이다. (우려먹기) 에라토스테네스의 체 소수 구하기: https://www.acmicpc.net/problem/1929 두 포인터 수들의 합 2: https://www.acmicpc.net/problem/2003 이 중 두 포인터문제는 예전에 한 번 다뤄 본 적이 있다. 혹시 풀이가 궁금하다면 하단의 링크를 참고하면 될 것 같다. [백준 2003번] 수들의 합 2 풀이: https://rubpcase.tistory.com/32 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음..

원본 링크 https://www.acmicpc.net/problem/12852 Intro 문제 제목을 보면 알겠지만, 2 이전에 1이라는 문제가 있었다. 해당 문제를 잠깐 언급해보도록 하겠다. 참고: https://www.acmicpc.net/problem/1463 위 문제에선 지금 설명할 문제와 조건은 동일하나, 출력에서 차이가 있다. 해당 문제는 단순히 횟수만 출력한다면, 여기선 횟수와 방법까지 다 출력해야 한다. 따라서 메모이제이션이 하나 더 필요하다. 즉, 앞선 문제를 포괄하는 문제라서 이 2번 문제만 포스팅하게 되었다. 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N..

원본 링크 https://www.acmicpc.net/problem/11725 Intro 이번 문제는 사실 코드를 짜면서 한 7번 정도 튕겼던 문제였다. 처음에 6번 정도는 같은 알고리즘 하에 재귀 깊이만 조정해서 제출하였다. Linked list개념을 활용해서 구현하려 했으나, n*n 크기의 리스트를 활용해서 연결 여부를 저장하니까 메모리 초과 오류가 났나 보다. (지금 보니 n이 100000까지 갈 수 있다고 나와있었다. (10^10;;;)) 따라서 재귀 깊이를 아무리 조정해도 실패로 뜨길래 출발을 잘못했다 판단하고 아예 코드를 다시 짰다. 막판에 실패를 먹은 코드는 Recursion 오류 때문에 그러했고, 재귀 깊이를 조정하니 통과가 되었다. 알고리즘 문제에서도 종종 나오는 (까다로운) 그래프 탐색..

원본 링크 https://www.acmicpc.net/problem/1013 Intro 이 문제는 읽어보면 알겠지만 정규식을 활용하게 된다. 프로그램별 언어를 배울 때 나온 와일드카드 문자와 같은 요소를 사용한다 생각하면 된다. 혹은 이산수학에서 배우는 String이나 Language에서 나오는 +, *를 사용한다고 보면 되겠다. (말이 더 어렵나..) 언어마다 차이가 있겠지만, 파이썬에선 별도로 정규식을 활용하는 라이브러리가 있으므로 이 문제를 위한 코드를 짜기가 쉽다. 문제 “무한히 넓은 저 우주에 인류만이 홀로 존재한다면, 그건 정말 슬픈 일이 아닐까요” 푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으..

원본 링크 https://www.acmicpc.net/problem/2003 Intro 이번 문제는 두 개의 포인터를 이용해서 푸는 문제이다. 뭐 가령 퀵 정렬과 같이 두 개의 포인터가 왔다갔다 하면서 값을 조정하고 계산한다고 보면 된다. 문제는 단순하지만 처음 접해보면 어렵다고 느낄 수 있는 문제였다. 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 ..

원본 링크 가장 긴 증가하는 부분 수열: https://www.acmicpc.net/problem/11053 가장 긴 바이토닉 부분 수열: https://www.acmicpc.net/problem/11054 Intro 이번에도 다시 돌아온 다이나믹 프로그래밍문제이다. 재밌는 것은, 11053번 문제를 풀게 되면, 약간의 눈칫밥(?)으로 11054번도 풀 수 있다는 것이다! 따라서, 여기서 두 개의 문제를 묶어서 소개하려 한다. 11053번; 가장 긴 증가하는 부분 수열 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30,..

원본 링크 https://www.acmicpc.net/problem/1237 Intro 번외로 분류되어있는 특이한 문제이다. 문제를 읽어보면 알겠지만 꽤나 신선했다. 따라서 나도 이번 문제는 독특하게 코드를 구성했다. 문제 이 문제를 푸는 자 우주를 정ㅋ벅ㅋ한다. 입력 우주를 정ㅋ벅ㅋ하는 자에겐 입력 따위 필요 없다. 출력 첫째 줄에 문제의 정답을 출력한다. 예제 예제 입력 1 (입력 모름)예제 출력 1 (출력 모름)힌트 우주를 정ㅋ벅ㅋ할 사람에게는 예제 입력과 예제 출력이 필요하지 않다. 주 알고리즘 분류 구현(?) 나만의 풀이 이게 무슨 문제냐고? 나도 문제 읽어보면서 당황했다. (이번 게시물은 사실 쉬어가는 포스트라는 학계의 정설) 예제의 입력과 출력이 주어지지 않았지만, 문제를 잘 읽으면 풀 수 ..

원본 링크 https://www.acmicpc.net/problem/10830 Intro 오랜만에 보는 분할 정복 기법문제이다. Divide & Conquer라고도 불리는 분할 정복 기법은 말 그대로 작게 문제를 분할해서 풀어나가고 합치는 방식이다. 여기서도 이 방법을 쓰는데, 나중에 과정을 보면 알겠지만 거듭 제곱을 활용해서 푼다. 이와 비슷한 문제도 찾아보면 나오는데, 심심하면 풀어보기 바란다. 유사 문제 - 1629 곱셈: https://www.acmicpc.net/problem/1629 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N..