TEN BILLION

유니온-파인드란?유니온-파인드는 여러 원소들을 그룹, 즉 집합으로 나누었을 때 두 가지 연산을 효율적으로 처리하는 자료구조 알고리즘입니다.Union (합치기): 두 원소가 속한 집합을 하나로 합치는 연산Find (찾기): 특정 원소가 속한 집합의 대표 원소(루트)를 찾는 연산이 두 가지 연산을 어떻게 구현하는지에 따라 알고리즘의 효율성이 크게 달라져요. 백준 1717번 문제는 이 두 연산을 직접 구현해봐야 합니다. 문제 해결을 위한 핵심 로직문제를 풀기 위해선 먼저 각 원소의 '부모' 정보를 담는 배열 parent를 만들어야 합니다. 이 배열 하나로 모든 것을 해결할 수 있어요.초기화처음에는 모든 원소가 각자 하나의 독립적인 집합을 이룹니다. 따라서 parent[i]의 값은 자기 자신인 i로 초기화합니..

문제를 처음 접했을 때, 떠올릴 수 있는 접근법은 '모든 경우의 수를 다 해보는 것'입니다. 10x10 격자의 모든 칸을 탐색하면서 1을 발견하면, 그 위치에 붙일 수 있는 색종이의 모든 경우를 시도하는 거죠. 이때, 가장 큰 색종이부터 붙여보는 게 효율적입니다. 왜냐하면 큰 색종이일수록 한 번에 덮는 면적이 넓어서 색종이 개수를 줄일 수 있는 가능성이 크기 때문이죠.이런 유형의 문제는 전형적인 백트래킹(Backtracking) 문제입니다. 특정 위치에 색종이를 붙인 다음, 다음 탐색을 진행하고, 만약 원하는 결과를 얻지 못하면 다시 색종이를 떼어내고 다른 경우를 시도해야 합니다. 재귀(DFS) 함수로 구현하기dfs(row, col, count)라는 재귀 함수를 만들어서 문제를 풀었습니다. // dfs..

문제 설명프로그래머스의 땅따먹기 문제(레벨 2) 는 다음과 같은 조건을 가진다:2차원 배열 land가 주어진다.각 행에서 하나의 열(0~3)을 선택해서 아래로 내려간다.단, 바로 전 행에서 선택한 열과 같은 열은 선택할 수 없다.마지막 행까지 내려갔을 때 얻을 수 있는 점수의 최댓값을 구해야 한다.int[][] land = { {1, 2, 3, 5}, {5, 6, 7, 8}, {4, 3, 2, 1}};​이 경우 가능한 모든 경로 중 최댓값 경로의 합을 찾아야 한다. 처음 생각한 풀이: DFS (깊이 우선 탐색)처음에는 다음과 같은 생각을 했다."각 행마다 4개 중 하나를 선택하되, 바로 위 열만 피하면 되니까 DFS로 모든 경우를 탐색하면 되겠네?"그래서 다음과 같이 DFS로 구현하였다..

문제 설명2차원 세계에 벽이 쌓여있을 때, 빗물이 고일 수 있는 총량을 계산하는 문제입니다. 여기서 H는 높이, W는 너비를 의미합니다. 문제는 각 칸의 높이가 주어지며, 빗물은 양쪽의 벽이 높아야 고일 수 있습니다. 즉, 어떤 한 지점에 빗물이 고이려면 그 지점의 왼쪽에서 가장 높은 벽과 오른쪽에서 가장 높은 벽 중 더 낮은 벽의 높이보다 현재 지점의 높이가 낮아야 합니다. 고이는 빗물의 양은 min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 높이로 계산됩니다. 예를 들어, 높이 배열이 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]이라면, 각 위치마다 왼쪽과 오른쪽의 최대 높이를 확인하여 빗물이 고이는지 판단하고 그 양을 합산해야 합니다. 자바코드import java.io.Buf..

문제 설명이 문제에서 주어지는 괄호 문자열은 다음과 같은 규칙을 가집니다.()는 2의 값을 가집니다.[]는 3의 값을 가집니다.(와 ) 사이에 유효한 괄호 문자열 X가 있다면, (X)는 2timesX의 값을 가집니다.[와 ] 사이에 유효한 괄호 문자열 X가 있다면, [X]는 3timesX의 값을 가집니다.유효한 괄호 문자열 X와 Y가 연결되어 있다면, XY는 X+Y의 값을 가집니다.예를 들어, (()[[]])([])와 같은 문자열이 주어졌을 때, 이 규칙에 따라 최종 값을 계산해야 합니다. 만약 올바르지 않은 괄호 문자열이거나 괄호의 짝이 맞지 않는다면 0을 출력해야 합니다. 스택(Stack) 사용이 문제를 해결하기 위해 스택(Stack) 자료구조를 선택한 이유는 괄호 문자열의 본질적인 특성 때문입니다...

'제곱수 찾기' 문제 설명'제곱수 찾기' 문제는 N*M 크기의 숫자판이 주어지면, 이 숫자판에서 시작 위치와 행/열의 등차를 정하여 숫자를 이어 붙였을 때 만들 수 있는 숫자 중 가장 큰 완전 제곱수를 찾는 문제입니다. 등차는 양수, 음수, 그리고 0도 가능하지만, 등차가 동시에 0인 경우는 제외됩니다. 즉, 같은 자리에서 움직이지 않는 경우는 고려하지 않습니다.예를 들어, 다음과 같은 숫자판이 있다고 가정해 봅시다.123456789만약 시작 위치가 (0,0)이고 행 등차가 1, 열 등차가 1이라면, 다음과 같은 숫자를 만들 수 있습니다.1 (1)15 (1, 5)159 (1, 5, 9)이 중에서 완전 제곱수를 찾아야 합니다. 자바코드import java.io.BufferedReader;import jav..

문제이 문제는 단순히 수의 크고 작음을 비교하는 것이 아니라, 부등호 조건을 만족하며 중복 없는 숫자 조합을 만드는 과정이 핵심이다.숫자의 위치마다 조건이 다르기 때문에, **완전탐색(백트래킹)**을 통해 가능한 조합을 모두 탐색하고 조건에 맞는 값을 찾아야 한다.또한, 숫자를 문자열로 다루는 경우 "10" 사전순 비교 문제가 발생할 수 있으므로, 숫자 타입으로 변환하거나 자릿수를 맞춰야 한다. DFS + 백트래킹0부터 9까지의 숫자 중 중복 없이 k + 1개의 숫자를 고른다.각 자릿수마다 이전 숫자와 현재 숫자의 부등호 조건을 검사한다.조건을 만족하면 재귀 호출을 통해 다음 숫자를 이어붙인다.모든 수가 완성되면 최대값과 최소값을 갱신한다. 자바코드import java.io.BufferedReader..

문제문제 링크: https://www.acmicpc.net/problem/4673관련 개념: 구현, 브루트포스난이도: 하 설명셀프 넘버란 어떤 수 n에 대해 n + n의 각 자리수의 합으로 생성할 수 없는 수를 의미한다.예를 들어 33은 24 + 2 + 4 = 30, 30 + 3 + 0 = 33으로 생성되므로 셀프 넘버가 아니다.하지만 1, 3, 5 등은 어떤 수로도 생성되지 않기 때문에 셀프 넘버이다.이 문제는 10,000 이하의 셀프 넘버들을 모두 구하여 출력하는 것이다. 구상생성자는 n + '각 자리수의 합'으로 표현된다.어떤 수 i가 생성자가 아닌 경우, 1부터 i까지 중에서 j + 각 자리수의 합 == i인 j가 존재하는지 확인한다.효율성을 위해 j는 i - 36부터 시작한다. → 9 + 9 +..

fibonacci(n)을 호출할 때, 재귀적으로 fibonacci(0)과 fibonacci(1)이 얼마나 호출되는지를 구하는 문제입니다.예를 들어, fibonacci(3)을 호출하면 내부적으로 다음과 같은 호출이 일어납니다:fibonacci(3) → fibonacci(2), fibonacci(1)fibonacci(2) → fibonacci(1), fibonacci(0)이 과정을 통해 fibonacci(0)은 1회, fibonacci(1)은 2회 호출됩니다.문제 접근처음에는 재귀로 직접 구현할 수도 있지만, 시간 초과가 발생할 수 있으므로, DP(동적 프로그래밍) 을 이용해 해결합니다.fibonacci(0)과 fibonacci(1)의 호출 횟수를 각각 기록fibonacci(n) 호출 시:fibonacci(..

문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다. 알고리즘: LIS (Longest Increasing Subsequence)접근 방식: 시간 초..