본문 바로가기

알고리즘

 (13)
삼성 SDS 2022 동계 대학생 알고리즘 특강 백준 문제 알고리즘 특강을 진행하면서 풀었던 문제와 같이 추천해줬던 문제이다. 알고리즘 기초 3425 - 고스택 3055 - 탈출 1065 - 한수 1713 - 후보 추천하기 1103 - 게임 1039 - 교환 1920 - 수 찾기 9663 - N-Queen 1759 - 암호 만들기 2580 - 스도쿠 1339 - 단어 수학 15686 - 치킨 배달 시간복잡도 2003 - 수들의 합 2805 - 나무 자르기 2748 - 피보나치 수 2 2517 - 달리기 1806 - 부분합 2096 - 내려가기 2143 - 두 배열의 합 1072 - 게임 7453 - 합이 0인 네 정수 2842 - 집배원 한상덕 11003 - 최솟값 찾기 자료구조 10828 - 스택 10845 - 큐 1991 - 트리 순회 2042 - 구간 합 ..
[백준 - 14476] 최대공약수 하나 빼기 - Java https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 누적합 문제이다. 0번째부터 시작해 n번째까지의 누적 최대공약수를 기록해두는 배열과, n번째부터 0번째까지 누적 최대공약수를 기록해두는 배열을 사용한다. 첫 번째 수인 8을 뺐을 때 0번째까지의 최대공약수는 없고, 48부터 12까지의 최대 공약수는 12이다. 따라서 8을 뺐을 때 최대공약수는 8이다. 두 번째 수인 12를 뺐을 때, 1번째까지의 최대공약수는 8, 48에서 24까지의 최대공약수는 12이다. 8..
[백준 - 9202] Boggle - Java https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net Trie를 사용해서 푸는 문제이다. 트라이는 문자열을 빠르게 검색할 수 있는 자료구조이다. // Trie 노드 설계 class Node { Object data; Node[] child; // a~z까지 담을 수 있도록 26크기의 배열 } add, ade, car, dad가 insert된 트라이는 아래와 같다. 트라이를 이용하여 검색할 때 - 루트부터 시작하여 검색할 단어의 첫글..
[백준 - 7578] 공장 - Java https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 이해하고 나면 플레치고 굉장히 단순한 인덱스트리 응용문제이다. A를 도는 인덱스를 a, B의 인덱스를 b라고 할 때, a = 1 일 때 b = 3이다. update를 한 후 b+1부터 끝까지의 부분합을 구하면 크로스 되어있는 선의 개수를 알 수 있다. a = 1, b = 3 일때는 첫 연결선이기 때문에 아무것도 겹치는 선이 없다. a = 2, b = 1 일 때는 query가 1을 return ..
[백준 - 1644] 소수의 연속합 - Java https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체를 사용해서 푼 간단한 문제이다. 에라토스테네스의 체를 사용해서 2부터 입력된 숫자까지의 소수를 구하여 새로운 Array에 저장하고, 찾은 소수와 합해서 입력된 숫자가 되는 다른 소수가 있는지 찾는다. public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.p..
[백준 - 2243] 사탕상자 - Java https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net n번째 맛의 사탕을 꺼내거나, 넣는 경우이다. n번째 맛의 사탕의 개수는 변동된다. 사탕의 맛은 최대 1,000,000까지 있고, 사탕상자에는 최대 100,000번 손을 대고, 사탕의 최대 개수는 2,000,000,000이다. 인덱스 트리로 응용하면 아주 쉬운 문제이다. 첫 번째로 맛있는 사탕이 2개, 세 번째로 맛있는 사탕이 3개 들어있을 때, 사탕상자에서 네 번째로 ..
[백준 - 2042] 구간 합 구하기 - Java https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 인덱스 트리를 구현하는 문제이다. 인덱스 트리의 method는 init, query, update가 있으며, bottom-up, top-down으로 모두 구현할 수 있다. 개념자체는 어렵지 않다. Bottom-up으로 풀리지 않는 문제를 Top-down으로 풀 수 있기 때문에 두가지 approach를 모두 익힐 시간이 없다면 top-dow..
[백준 - 1202] 보석 도둑 - Java https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 우선순위 큐를 활용한 그리디 문제이다. Jewel은 무게와 가격 정보를 갖고있다. 맨 처음 입력받은 Jewel과 가방을 무게 오름차순으로 정렬한다. 들어갈 수 있는 무게가 작은 가방에 들어갈 수 있는 보석은 들어갈 수 있는 무게가 큰 가방에도 들어갈 수 있기 때문에 작은 가방에 넣는 것을 우선시한다. 우선순위 큐는 가방이 수용할 수 있는..

티스토리툴바