https://www.acmicpc.net/problem/1717알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find의 기초 문제이다. Union 연산은 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산이다.먼저 두 원소가 같은 집합인지 확인하고 같은 집합이 아니라면 하나로 합친다. 보통 같은 집합을 확인하는 과정은 부모의 번호를 기재하여 확인한다.Find 연산은 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환한다. 문제의 예시를 아래와 같이 가정한다.//input7 40 1 31 1 70 7 61 1 3 1. 7 4n개의 집합을 생성한다. 각 집합의 부모는 자신을 가르키고있다. 2. 0 1 3union1과 3에 대해 parent를 확인하고 같..
https://www.acmicpc.net/problem/1202알고리즘 분류 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 ❓문제🔅해석조건이 2개 이상이므로 우선순위 큐(PQ)를 사용하여 문제를 풀이한다. 보석의 속성이 2가지 있으므로 객체로 생성하여 짝을 이룰 수 있게한다. 가방에 넣을 수 있는 보석을 PQ에 담기 위해 가방과 보석의 무게를 오름차순 정렬한다. 이후 반복문을 돌면서 정답을 계산한다.1. 가방을 하나 고른다.2. 무게순으로 정렬한 보석을 해당 가방에 들어갈 수 있는지 비교하고 들어갈 수 있다면 해당 보석을 PQ에 넣는다.3. 한 가방에 다 넣었으면 PQ에서 보석을 꺼내어 해당 보석의 가격을 정답에 더한다. ⭕정답 코드import java.io.BufferedReader;impo..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
https://www.acmicpc.net/problem/2243알고리즘 분류 : 자료 구조, 세그먼트 트리, 이분 탐색 ❓문제🔅해석 세그먼트 트리에서 구간의 정보를 조회하는 query는 총 다섯가지 정보를 넘긴다.query(int left, int right, int node, int queryLeft, int queryRight) 현재 문제에서는 해당 순위의 정보만 필요하므로 query(int left, int right, int node, int query) 으로 넘긴다. 문제의 입력을 보자면, 레벨 1 사탕 2개, 레벨 3 사탕 3개가 존재하고 여기서 2번째로 맛있는 사탕을 꺼내준다고 할 때, 답은 레벨 1이다. 위 그림을 볼 때, 노드를 탐색하면서 해당 노드의 값이 B보다 크거나 같을 때 왼쪽..
https://www.acmicpc.net/problem/2042알고리즘 분류 : 자료 구조, 세그먼트 트리 ❓문제🔅해석세그먼트 트리를 이용하는 가장 기본적인 문제이다.인덱스 트리 생성 - init인덱스 트리의 리프 노드에 배열을 담아야 하므로 리프 노드가 시작하는 인덱스 번호를 알아야한다.리프 노드의 개수를 S로 표현하고 S는 N 이상의 2^n으로 표현 가능한 수여야 한다.따라서 S 는 아래와 같이 구한다. (N은 주어진 배열의 크기)S = 1;while (S 리프 노드에 배열에 적혀있는 수를 넣기위해 S번째부터 넣는다.그 외 내부 노드는 S - 1번째부터 자식 노드(왼쪽, 오른쪽) 합을 대입한다.private static void init() { // leaf노드 채우기 for (in..
https://www.acmicpc.net/problem/1927알고리즘 분류 : 자료 구조, 우선순위 큐직접 힙을 구현하여 풀이하였습니다. ❓문제🔅해석직접 힙을 구현하여 풀어본 문제이다. 최소 힙은 ' 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.'는 힙 조건을 가진다.힙 조건에 맞춰 삽입과 삭제 연산을 진행한다. 삽입 연산트리의 가장 마지막 위치에 노드를 삽입한다.추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.만족하지 않는다면 부모와 자식의 키 값을 바꾼다.조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3을 반복한다. 입력을 받다가 '0'을 만나게 되면 삭제 연산을 수행한다. 삭제 연산힙의 삭제 연산은 항상 루트 노드를 삭제한다.트리의 가장 마지막 노드를 루..
https://www.acmicpc.net/problem/2805알고리즘 분류 : 이분 탐색, 매개 변수 탐색 ❓문제🔅해석투포인터와 비슷하게 세개의 포인터로 문제를 푼다.1 ~ 트리의 최대값까지의 배열을 만들어 start = 1, end = 트리의 최대값, mid = (start / end) / 2 로 초기화한다.mid 값을 현재 절단기 높이라고 생각하고, 입력받은 트리의 순회하면서 mid 값을 각각 빼주고 sum에 더한다. sum이 목표값보다 크다면 나무를 더 많이 잘랐다는 뜻으로 절단기 높이를 높이기 위해 start 값을 mid + 1로 설정한다.반대의 경우, end = mid - 1로 설정한다. 다시 mid = (start + end) / 2로 설정해고 위와 같이 트리를 순회하면서 절단된 나무들..
https://www.acmicpc.net/problem/2003 알고리즘 분류 : 브루트포스 알고리즘, 누적합, 투포인터❓문제🔅해석두 수의 합이 특정 값이 되는 경우를 찾는 문제로 투포인터를 이용한다.입력받은 숫자를 배열에 넣고 low pointer와 high pointer로 합을 구한다. //입력10 51 2 3 4 2 5 3 1 1 2 1) 초기화 및 sum 두개의 포인터 모두 0번째 인덱스부터 출발하고 sum은 0번째 인덱스 값으로 초기화해준다.sum이 특정 값(M) 5보다 작으므로 high pointer를 +1 해준다. 그리고 sum에 증가된 high 번째의 값을 더한다. 2) sum == M sum == M 이 될 때, cnt++ 해주고 low 또는 high을 +1 해준다. 그리고 su..
https://www.acmicpc.net/problem/1713알고리즘 분류 : 구현, 시뮬레이션❓문제🔅해석학생 객체에 학생 번호, 추천 수, 타임스탬프를 저장하여 조건에 맞게 정렬을 한다. Student[] students = new Student[101]; //학생 번호는 1부터 100까지의 자연수이다.학생 객체를 담는 배열을 만들어 학생 번호와 배열 인덱스를 맞춰 저장한다.예를 들어, 2번 학생이 추천을 받았을 때 배열 2번째에 학생 객체가 존재한다면 이미 추천받아 저장되어 있다는 것이다.이 때는 해당 객체의 추천수를 증가시킨다. List photos = new ArrayList(); // 사진틀의 개수 N를 저장한다.배열이 비어있다면 사진틀 리스트에 추가해준다.이 때 사진 틀이 꽉 찼을 때, ..
https://www.acmicpc.net/problem/1256알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론❓문제🔅해석'a'와 'z'의 조합으로 n번째 단어를 출력하는 문제이다.사전에는 알파벳 순서대로 수록되어 있으므로 'a'로 시작하는 문자의 조합으로 계산해본다.입력 : 2 2 6 1. a_ _ _ 'a'로 시작하는 문자의 조합 개수는 남은 3자리수와 남은 'z'의 갯수 3C2이다. 3C2 = 3이므로 'a'로 시작했을 때 3가지의 조합을 만들 수 있다.우리는 6번째(K) 순서를 원하므로 'z'로 시작한다는 것을 알 수 있다. (3C2 1) 결과값을 담는 sb에 'z'를 추가하고2) 'z' 카운트를 하나 감소시킨다.3) K의 값을 조합 수 만큼 감소시킨다. 2. z a _ _위에서 'z'로 ..
