자료구조

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(연습)] [BJ17299] 오등큰수
🚩 문제 설명 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 ⏱️ 시간 복잡도 ▪ 수열의 크기가 100만에 해당한다. ▪ O(N^2)이 되면 시간초과가 된다. ▪ 따라서 O(N)의 시간복잡도로 문제를 해결해야 한다. ◾ 오등큰수 해당 수의 오른쪽에 있다. 해당 수의 등장횟수보다 큰 수 중에서 가장 왼쪽에 있는 수 ◾ 오큰수 문제 처럼 수열의 오등큰수를 구해 출력하는 문제 ✅ 입출력 1) 수열 A의 수 N이 주어진다. 2) 오등큰수를 구해야하는 수열 A가 ..
→2021.11.28
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(연습)] [BJ10799] 쇠막대기
🚩 문제 설명 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 괄호 문자의 개수는 최대 10만이다. ▪ 그러므로 O(N^2)의 시간복잡도를 가지면 안되고 O(N)이나 O(NlogN)의 시간복잡도를 가져야한다. ▪ 괄호 문자를 훑으며 잘려진 쇠막대기의 개수를 구해야한다. ▪ 시간복잡도는 O(N)이라고 할 수 있다. ◾ 괄호 표현 구분 레이저 ➡ () 쇠막대기 ➡ ( ~~ ) ◾ 문제의 이해는 다음과 같다. Algorithm 1. ( 을..
→2021.11.28
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(연습)] [BJ17298] 오큰수
🚩 문제 설명 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 ⏱️ 시간 복잡도 ▪ 수열의 크기를 보면 100만이다 ~= 10^6 ▪ 따라서 해당 문제는 O(100 x N)을 넘어가서는 안된다. ◾ A의 각 원소 A(i) 에 대한 오큰수 NGE(i) A(i)의 오른쪽에 있으면서 A(i) 보다 큰 수 중에서 제일 왼쪽에 있는 수 ◾ 만약 오큰수가 없다면 -1 을 출력한다. ◾ 주어진 수열에 대한 오큰수를 출력하는 문제 ✅ 입출력 1) N : 주어지는 수열의..
→2021.11.25
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(연습)] [BJ17413] 단어 뒤집기 2
🚩 문제 설명 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 주어진 문자열의 길이는 S이다. ▪ 문자열 하나하나 당 따져보므로 따라서 O(S) 라고 할 수 있다. ◾ 문장들이 주어질 때 각 문장의 단어만을 거꾸로 뒤집어 출력하는 문제 ◾ 몇가지의 규칙을 지켜야 한다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과..
→2021.11.25
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조] [BJ10866] 덱
🚩 문제 설명 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 총 명령어의 수는 N개 이다. ▪ 시간복잡도는 대략적으로 O(N)이라고 할 수 있다. ◾ 스택이나 큐 문제 처럼 덱을 구현해서 명령을 처리하여 결과값을 출력하는 문제 ◾ 명령어 8가지 push_front X : 정수 X를 덱의 앞에 넣는다. push_back X : 정수 X를 덱의 뒤에 넣는다. pop_front : 덱의 가장 앞에 있는 수를 빼..
→2021.11.25
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조] [BJ1158] 요세푸스 문제
🚩 문제 설명 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net ⏱️ 시간 복잡도 ▪ 총 N명의 사람을 제거해야한다. ▪ 시간 복잡도는 O(N)이라고 볼 수 있다. ◾ 원을 그리고 있는 사람들을 스텝 순서 대로 없애는 문제 ◾ 제거되는 값을 반환한다. ✅ 입출력 N: 원을 이루고 있는 사람의 수 K: 제거되는 스텝의 수 return ➡️ 제거되는 사람의 인덱스 수를 순서대로 반환 ✔️ 예시 📑 문제 풀이 with 파이썬 (Python) import sys from collections import deque N, K = map(int, ..
→2021.11.24

• 이전
• 1
• 2
• 3
• 4
• 다음