[C++] 백준 2343번 Binary Search 안녕하세요 오랜만에 하는 블로깅이네요! 시험기간이라 바쁘다는 핑계로 블로그를 좀 소홀하게 한 것 같아요 이제라도 다시 정신차리고 해야겠다는 생각을 하는 요즘입니다. 학교에서 자료구조를 배우면서 자료구조에 관련한 백준 문제를 요즘 풀고 있습니다. 그래서 오늘 가지고 온 문제는 Binary Search (이분 탐색)에 관련한 백준 2343번 "기타 레슨" 문제입니다. https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분 탐색 문제를 세 개 정도 풀어보고 .. 누적합, 구간합 누적합과 구간합이란? 누적합은 배열의 각 원소까지의 합을 계산한 배열을 말합니다. 구간 합은 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘입니다 합 배열은 보통 S라고 표현합니다. 합 배열과 누적합은 개념적으로는 비슷하지만 합 배열은 누적합과 달리, 0부터 i까지의 합을 나타내는 것이 아니라 1부터 i까지의 합을 나타냅니다. 하지만 알고리즘을 푸는데 있어서는 두 개념을 혼용해서 사용하여도 크게 문제는 없을 것 같습니다. 배열 A가 있을 때 합 배열 S는 이렇게 표현합니다. S[i] = A[0] + A[1] + A[2] ......+..... A[i - 1] + A[ i ] 그러면 합배열을 사용하는 이유는 뭘까요? => 합 배열을 미리 구해놓게 되면 기존 배열의 일정 범위의 합을 구하는 .. 알고리즘에서 흔한 오류 1. 변수 초기화 오류 코딩 테스트의 두 번째 테스트 케이스부터 통과되지 않을 때는 모든 변수가 정상적으로 초기화 되고 있는지 디버깅을 이용해 확인해보면 문제 해결에 도움이 된다. 2. 배열 인덱스 오류 배열 인덱스가 0부터 시작한다는 사실을 간과하거나 반복문을 N까지 반복해야하는데 N-1까지 반복하게 하는 등의 인덱스 오류가 있을 수 있다 (i를 0부터 시작하는지/1부터 시작하는지, 비교연산자를 잘 못 사용했다던지) 3. 잘못된 변수 사용 오류 변수를 착각하고 다른 변수를 사용한다면 찾기 힘들 수도 있다. 4. 자료형 범위 오류 음수가 나올 수 없는데 음수가 나왔다면 변수 범위 초과를 의심하며 자료형을 우선 확인해보기 범위를 넘어가면 long long을 사용하여야 한다. (int : -214748364.. C++에서의 시간 복잡도 C++에서는 1억번의 연산을 1초로 계산한다. 따라서 자료의 개수와 시간복잡도를 파악하고 시간제한에 맞게 코드를 작성한다. [C++] 후위 표기식과 string stack을 사용하여 후위 표기식을 표현하였다. #include using namespace std; int main() { string postfix = ""; cin >> postfix; string stack[100]; int top = -1; for (int i = 0; i = 'A' && alphabet doubly linked list (이중 연결 리스트) 구현한 코드 #include using namespace std; struct node { node* next; node* prev; int data; }; class linkedList { public: linkedList(); void append(int inputValue); void deletion(int idx); void insertion(int idx, int inputValue); void print(); void at(int idx); bool isEmpty(); private: node* header; node* trailer; int listSize; }; linkedList::linkedList() { header = new node; trailer = new node; header.. [C++] 백준 1158번 동적 배열 할당과 linkedlist c6001 경고 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 나의 풀이 #include using namespace std; struct Node { int data; struct Node* next; }; class circleList { public: circleList(); void append(int data); void deletion(int n, int k); private: Node* head; Node* tail; int listSize; }; circleList::circleList() { head = NULL; tail = .. 백준 문제를 풀며 정리하는 C++ 함수 계속 추가할 예정입니다! #include count 함수 배열, 벡터 등 원하는 값의 개수를 찾아준다. string, char, int 모두 가능하다 ex) count(시작점, 끝점, 찾을 값) int array[3] = {1,3,5}; cout 백준 1927번 최소, 최대 힙 문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 나의 코드 from heapq import heappop, heappush import sys min_heap = [] result = [] for i in range(int(input())): inputNumber = int(sys.stdin.readline().rstrip()) if inputNumber == 0: if len(min_heap) == 0: result... 힙 트리 ( 최소 힙, 최대 힙 ) 힙트리(heap)란? 최댓값 또는 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 부모-자식 노드 간의 대소 관계가 성립하며 반정렬 상태(느슨한 정렬 상태)를 유지한다. 형제 간의 대소 관계는 없고 값을 중복하여 저장가능 하다 힙은 최대 힙의 높이만큼 탐색하여 O(logn)의 시간 복잡성을 가진다. 힙 트리는 최소 힙과 최대 힙으로 나뉠 수 있다. 최소 힙은 부모노드가 자식 노드보다 작거나 같으며 최대 힙은 부모노드가 자식 노드보다 크거나 같다. 힙 트리에서의 삽입 연산 1. 트리 끝에 노드를 추가한다. 2. 부모 노드와 대소를 비교한다. 3-1. 최대 힙인 경우, 추가한 값이 부모 노드보다 크면 자리를 바꾼다. 3-2. 최소 힙인 경우, 추가한 값이.. 백준 1620번 dictionary의 활용 문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 나의 풀이 import sys pocketmonCount, problemCount = map(int,input().split()) encyclopedia = dict() for i in range(1, pocketmonCount+1): encyclopedia[sys.stdin.readline().rstrip()] = i convertEncyclopedia =dic.. 백준 1158번, deque와 replace 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 나의 풀이 from collections import deque n,k=map(int,input().split()) queue = deque() for i in range(1, n+1): queue.append(i) permutation = [] while queue: for _ in range(k-1): queue.append(queue.popleft()) permutation.append(queue.popleft()) print(str(permutation).replace('['.. 이전 1 2 3 다음
