Algorithm/PTUStudy
12주차. 해시 테이블(중복 문자 없는 가장 긴 부분 문자열)
30. 중복 문자 없는 가장 긴 부분 문자열 https://leetcode.com/problems/longest-substring-without-repeating-characters/
알고리즘
Algorithm/PTUStudy
12주차. 해시 테이블(보석과 돌)
29. 보석과 돌 https://leetcode.com/problems/jewels-and-stones/ Merge k Sorted Lists - LeetCode Can you solve this real interview question? Merge k Sorted Lists - You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example 1: Input: lis leetcode.com 📌문제 J는 보석이며 S는 갖고있는 돌이다. S에는 보석이 몇 개나 있을..
Algorithm/PTUStudy
11주차. 후위표기식2
1935. 후위표기식2 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 📌문제 - 예제1 📝입력 5 ABC*+DE/- 1 2 3 4 5 💻출력 6.20 📌풀이 알파벳이 들어왔을 때, Stack에 push해주고 연산자를 만나면 2번 pop해서 연산을 해주면 되는데 이때 중요한 점이 2번째 pop해서 얻어온 값을 앞에 배치하여 연산해야 한다는 점이다.(코드를 보면 이해가 쉬울 것입니다.) 이 점만 파해했다면 어렵지 않게 풀 수 있는 문제..
Algorithm/PTUStudy
11주차. 오등큰수
17299. 오등큰수 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 📌문제 - 예제1 📝입력 7 1 1 2 3 4 2 1 💻출력 -1 -1 1 2 2 1 -1 📌풀이 풀이 법은 오큰수와 비슷하다. 다만 각 숫자가 수열에서 몇번 나오는지 체크해줘야 했기때문에 Map을 활용했다. 원래는 Map에 저장한 등장 횟수를 토대로 다시 배열을 만들 생각이었는데, 다시 생각해보니까 그럴 필요가 없었다. map에서 바로 get 해오면 되니까 말이다. 마찬가지로 스택에는 ..
Algorithm/알고리즘 개념
[알고리즘] 최소 신장 트리 - Prim, Kruskal Algorithm(프림, 크루스칼 알고리즘)
최소 신장 트리(Minimum Spanning Tree)란? 💡최소 신장 트리: 그래프에서 모든 정점에 대해 최소한의 연결만을 남긴 그래프이다. 즉 간선의 가중치 합이 가장 작은 트리를 뜻한다. 사이클이 존재하지 않아야 한다. 최소 신장 트리를 찾는 알고리즘으론 크루스칼 알고리즘, 프림 알고리즘이 있다. 이 알고리즘은 그리디 알고리즘 기법을 활용한 알고리즘이다. 프림 알고리즘은 바이너리 힙을 이용하는 경우 O(E+VlogV)의 시간 복잡도를 가지며, 크루스칼 알고리즘은 경로 최적화를 이용하지 않는 경우 O(ElogV), 경로 최적화를 이용하는 경우 O(Elog∗V)의 시간 복잡도를 가지기 때문에, 그래프의 간선 밀도를 고려하여 최적의 알고리즘을 선택하는 것이 필요하다. 크루스칼 알고리즘(Kruskal A..
Algorithm/알고리즘 개념
[알고리즘] Union-Find Algorithm (유니온 파인드 알고리즘)
유니온 파인드 알고리즘이란? 💡유니온 파인드 알고리즘: 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 왜 이름이 유니온 파인드인가? 유니온 파인드 알고리즘은 두가지의 연산을 진행한다. 이 연산 과정을 Union, Find라고 부른다. Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다. Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다. 크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다. 유니..
Algorithm/알고리즘 개념
[알고리즘] Dijkstra Algorithm (다익스트라 알고리즘)
다익스트라 알고리즘이란? 💡다익스트라 알고리즘: 데이크스트라 또는 다익스트라 알고리즘이라 불리는 이 알고리즘은 음의 가중치가 없는 그래프에서 최단 경로 및 최단 거리를 찾는 알고리즘이다. 매번 최단 경로의 정점을 선택하기 때문에 그리디 알고리즘 기법을 활용한 예라고 볼 수 있다. 중요한 점은 음의 가중치가 없을 때만 사용이 가능하다는 점이다. 인접행렬을 사용하는 경우 O(n^2)의 시간복잡도를 가지지만, 우선순위 큐(=힙 트리)등을 이용한다면 O((v+e)logV)(V는 정점의 개수, E는 한 정점의 주변노드)의 시간복잡도를 가진다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는..
Algorithm/알고리즘 개념
[알고리즘] Greedy Algorithm(탐욕 알고리즘)
탐욕 알고리즘이란? Greedy Algorithm: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘인 것이다. 탐욕 알고리즘은 일정 공식없이 창의력을 요구하는 문제 유형이다. 때문에 문제를 풀기위한 최소한의 아이디어를 떠올려야 할 것이다. 물론 모든 경우에서 그리디 알고리즘이 통하는 것은 아니다. 예를 들어 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로우를 1..
Algorithm/PTUStudy
10주차. 오큰수
17298. 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 📌문제 - 예제1 📝입력 4 3 5 2 7 💻출력 5 7 7 -1 📌풀이 992ms 147952kb import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public clas..
Algorithm/PTUStudy
10주차. 쇠막대기
10799. 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 📌문제 - 예제1 📝입력 ()(((()())(())()))(()) 💻출력 17 📌풀이 180ms 16472kb import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { public static void..
