✅ 문제https://www.acmicpc.net/problem/2805✅ 이진 탐색이진 탐색 문제의 특징이진 탐색 문제는 대부분 데이터가 굉장히 많아서, 탐색에 시간이 굉장히 오래걸릴 거 같은 느낌이 드는 문제이다.이 문제 역시도 데이터(나무의 높이)가 최대 1000000000 일 수 있어, 1씩 높여가면서 탐색을 하려고 할 때 시간 초과가 날 거라는 건 쉽게 짐작할 수 있다.참고로 이 자료를 저장할 수 있을 만한 자료형에 적절히 저장해야 한다. (long long 등)이진 탐색 문제를 풀려면?이진 탐색 문제에서는 정렬을 하거나, 최대 최소 값을 아는 것이 중요하다.중간값을 적절히 찾아야하고, start지점과 end지점을 적절히 업데이트 해야 한다.종료 조건도 중요하다. 언제까지 이 탐색을 계속할 것인..

문제https://www.acmicpc.net/problem/24444BFS와 DFS?그래프 탐색 알고리즘으로는 흔히 아는 BFS와 DFS가 있다.BFS는 너비 우선 탐색이고, DFS는 깊이 우선 탐색이다.1번과 연결된 노드가 2, 3이고 2와 연결된 노드가 4이라고 가정해 보자. BFS로 탐색하면 1 -> 2 -> 3 -> 4의 경로로 탐색할 것이다. DFS로 탐색하면 1 -> 2 -> 3 -> 4의 경로로 탐색할 것이다. (오름차순으로 방문한다고 가정했을 때) BFS는 같은 깊이의 노드를 모두 탐색하고 난 다음에 더 깊은 노드로 들어간다. DFS는 연결된 가장 깊은 노드로 먼저 이동한다.BFS는 어떻게 구현되는가?BFS는 주로 deque로 구현한다. 왜냐하면, deque는 push_back(), po..

1620 - 나는야 포켓몬 마스터 이다솜https://www.acmicpc.net/problem/1620새롭게 알게된 자료형 - unordered_map특징- 해시 기반으로 검색하는 자로형 (검색이 빠름 O(1)의 복잡도)- 삽입된 순서를 기억하지 않음- 메모리 사용량 많음- 자체적으로 정렬할 수 없음. 정렬하고 싶을 때는 vector 등의 자료형으로 변환한 후에 정렬해야 함. std::vector> sortingArray(entryRecord.begin(), entryRecord.end()); std::sort(sortingArray.begin(), sortingArray.end(), [](std::pair& a, std::pair& b) { retu..

💻 문제 - 2480 번 조건문https://www.acmicpc.net/problem/2480✅ 관련 이론vector 자료형vector::iterator type으로 요소에 접근한다.vector.begin(), vector.end()로 처음과 끝의 포인터를 확인한다.원하는 index의 값을 얻으려면 vector.begin() - iter로 접근한다. vector.at(index)로 원하는 index에 접근한다. (index 범위가 유효하지 않을 때 out_of_range 오류가 발생한다.)reverse로 접근하고 싶을 때는 vector::reverse_iterator로 접근한다.vector.rbegin(), vector.rend()로 처음과 끝의 포인터를 확인한다.이때, 접근하는 iterator는 처..

💻 문제 - 11382 번 입출력https://www.acmicpc.net/problem/11382 ✅ 관련 이론int 자료형 크기short: 2 bytes 이상int: 2 bytes 이상long: 4 bytes 이상long long: 8 bytes 이상(자료형 크기는 운영체제에 따라 다르기 때문에 sizeof를 통해 확인해야 한다.)signed와 unsignedsigned는 음수, 양수를 저장할 수 있는 타입이다. (ex. 1 bytes면 -128~127 저장)unsigned는 양수만 저장할 수 있는 타입이다. (ex.1 bytes면 0~255저장)문제에 적용한 이론문제에서 필요한 a,b,c는 1~10^12의 값을 가질 수 있음.(최대 13자리)각각의 변수는 최소 8 bytes를 저장할 수 있어야 함..

# 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net # 시도 1 (실패 - 시간초과) number = int(input()) array = [i+1 for i in range(number)] length = number while (len(array) != 1): del array[0] item = array.pop(0) array.append(item) print(array) print(array[0]) array의 pop 연산자와 de..

# 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net # 코드 풀이 def solve(): n, m = map(int, input().split()) input_list = [] sum_list = [] input_list = list(map(int, input().split())) for i in range(2, n): for j in range(1, i): for k in range(0, j): sum =..

# 문제 - 팰린드롬수 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net # 접근 팰린드롬수 - 뒤에서부터 읽어도 똑같은 단어 앞에서 넣고 뒤부터 뺐을 때 원래 string과 같으면 팰린드롬수라고 할 수 있겠다. # 코드 while(True): list = [] pop_string = '' string = input() if (string == '0'): break for ch in string: list.append(ch) for _ in range(len(l..

# 문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net # 접근 list에 넣고 빼는 것을 조건에 따라 반복 # 작성 코드 num = int(input()) num_list = [] sum = 0 for _ in range(num): input_num = int(input()) if (input_num == 0): del num_list[-1] else: num_list.append(input_num) for..

# 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net # 고민 ()는 VPS. ( 를 +1 이라 했을 때 ) -1이라 하고 총 합이 0이 되면 되지 않을까? 또, 전체 count 값이 음수가 되면 VPS가 될 수 없다 -> break하고 False 출력 # 작성 코드 num = int(input()) for _ in range(num): string = input() split_list = list(string..