[C] 백준 | 1966번 코드 - *프린터 큐
>문제 > 핵심 큐 >풀이과정 이 문제를 풀다가 돌아버릴 뻔 했다. 문제를 풀고 나니 모두 나의 무지에 의한 것이였다. 내가 겪었던 문제점 1. 내가 원하는 문서가 언제 출력되는지 어떻게 알아? 큐의 front에 있는 값이 현재 큐에서 가장 중요도가 높은 문서라면 dequeue를 진행하고, 그렇지 않다면 dequeue 후 맨 뒤에 enqueue 한다. 근데 처음에 m번째 위치에 있는 문서가 enqueue, dequeue를 거치며 순서가 뒤죽박죽 섞이는데 언제 출력될지 어떻게 알까..? 곰곰이 생각하다가,, int[SIZE][2] 배열을 쓸까 생각하다가 이건 큐로 만들기 조금 복잡할 것 같아서 구조체! Paper을 만들어서 구조체 배열을 갖는 큐를 만드는 방식을 사용했다. Paper 구조체에 중요도를 넣는..
[C] 백준 | 1874번 코드 - 스택 수열
>문제 > 핵심 스택 >풀이과정 문제가 뭔소린가.. 싶어서 문제를 이해하는데 조금 시간이 걸렸다. 그래도 이해하고 난 후 코드를 짜는건 크게 어렵지 않았다. num=1부터 오름차순으로만 증가!. (e : 입력값) 1. 스택의 Top e : e에 도달하기 전까지 pop, num은 고정. 3. 스택의 Top != e : 수열을 만들 수 없음. chk = 0 으로 체크 후 break. 4. 스택의 Top == e : 해당 값을 pop 하고 위 과정 반복. 하나 고려해야 할 점은 정수를 입력받고 나서 바로 + 혹은 - 를 찍으면 안되고, 모든 정수를 입력받은 후에 만들수 있는 수열인지, 아닌지 체크를 한 다음 정답을 출력해야하므로 따로..
[C] 백준 | 1654번 코드 - 랜선자르기
>문제 > 핵심 이분탐색 long long 자료형 >풀이과정 (내가 처음 생각한 계획 K개의 랜선 중 제일 짧은 랜선을 찾는다 -> k_min 1부터 k_min까지 1씩 ++하면서 N개 이상의 랜선을 만들어내면 len과 대조해 큰 값을 넣는 계획이었는데.. 이중반복문을 돌리다 보니 시간초과가 뜬다..) 그래서 어떻게 할까.. 고민하다가 이진탐색 방법이 딱 생각났다!! K개의 랜선 중 제일 긴 랜선을 찾는다 -> k_max 이진탐색을 위해 left, mid, right 선언 left = 0, right = k_max부터 시작해 mid=(left+right)/2 K개의 랜선을 mid 길이로 잘랐을때 N개의 랜선이 만들어지면? -> mid보다 더 길게 잘라도 N개의 랜선이 만들어질 수 있으니 left = mi..
[C] 백준 | 11866번 코드 - 요세푸스 문제 0
>문제 > 핵심 큐 or 배열 >풀이과정 일단 N, K 값을 입력받고, 크기 N만큼의 배열을 동적할당한다. 그 이후에 배열에 1부터 N까지의 값을 차례대로 집어넣는다. 이제 하나씩 값을 제거할텐데, 출력 조건을 보면 처럼 괄호 처리를 따로 해줘야한다. 그래서 "" 세부분으로 나눠 출력하기 위해서 첫번째 값 삭제는 반복문 밖에서 먼저 해줬다. 배열에는 양의 정수가 채워져있기 때문에 제거된 값은 -1로 채워넣는 것으로 했다. K번째 값을 삭제하는거니까 배열에서는 먼저 table[K-1]번째 값을 지워준다 그 이후에 인덱스 [K-1]번부터 시작해서 반복문을 돈다. j=0부터 올라가면서 table[(idx+j) % N] != -1 양의정수를 만날때마다 cnt++ 해주고, cnt가 K와 같아지면 탈출. 여기서 (..
[C] 백준 | 10866번 코드 - 덱
>문제 > 핵심 덱 연결리스트 >풀이과정 처음엔 이 문제를 보고 이건 큐인가,, 스택인가,, 고민하다가 그냥 헤더 하나 만들어 놓고 연결리스트를 이어놓으면 다 되겠구나! 싶어서 연결리스트 방식으로 문제를 풀었다. 명령어가 워낙 많아서 코드가 엄~청 길어졌다. 손이 바쁘다 바빠 그나저나 다 풀고 나니까 덱이 뭔지 알았다. 덱(Deque)는 "double-ended queue" 의 줄임말으로 양쪽에 끝이 있는 큐라는 의미이다. 큐의 앞에서도 삽입/삭제, 뒤에서도 삽입/삭제가 모두 가능한 구조. 스택이면서 동시에 큐 같은 느낌? 아무튼 이 deque에서는 문제에 나온것 처럼 네가지 명령을 기본적으로 수행한다 · push_front (->addLast) · push_back (->addFirst) · pop_f..
[C] 백준 | 10845번 코드 - 큐
>문제 > 핵심 큐 >풀이과정 이 문제도 자료구조 시간때 큐를 배워본 사람이라면 누구나 한번쯤은 만들어 봤을 문제인 것 같다, enqueue와 dequeue할 때, SIZE로 나머지 연산을 하는 이유는 원형큐로 활용하기 위해서! 큐는 선입선출! 스택은 제일 늦게 들어온게 제일 먼저 팝! 그리고 C++에는 큐, 스택 라이브러리가 있는데 C는 그런게 없단다.. 그래서 일일히 직접 손코딩으로 함수를 다 만들어서 써야한다. 이런! >깨달은점 큐는.. 스택보다는 쪼끔 어렵다! >코드 #define _CRT_SECURE_NO_WARNINGS #include #include #define SIZE 10001 typedef struct { int queue[SIZE]; int front, rear; }QueueType..
[C] 백준 | 10828번 코드 - 스택
>문제 > 핵심 스택 >풀이과정 그냥 스택 문제다. 자료구조 시간때 스택을 배운 사람들이라면 이런 코드는 수업시간때 한번쯤은 짜봤지 않을까 하는 생각이 든다. ㅋㅋㅋ 그래도 이 기회에 스택에 대해 개념을 확실히 다져놓고 넘어가자. 일단 C언어에서 False = 0, True = 0이 아닌 모든것(1) 이라는거 제발 좀 까먹지 말자.. 왜자꾸 까먹는지.. · 스택 구조체 선언 및 초기화 #define SIZE 10001 typedef struct { int stack[SIZE]; int n; }StackType; void init_stack(StackType* s) { s->n = -1; } 스택 구조체 StackType를 만들고, s->n=-1로 초기화 하여 첫 값이 0번째 인덱스에 들어가도록 세팅 · ..
[C] 백준 | 10816번 코드 - 숫자 카드 2
>문제 > 핵심 이진탐색 / 이진탐색트리..? >풀이과정 처음에는 배열을 list[50만][2] 짜리로 선언을 해서, 입력받은 정수와, 개수를 묶어서 탐색을 하려고 했었는데, 이중반복문을 돌아야할 것 같아서 다른 방법을 곰곰이 생각하다가,, 화장실에서 문득 이진트리! 생각이 나서 이진탐색트리 방법으로 풀었는데 다행히 정답이 나왔다. 같은 카드를 여러장 가지고 있을 수 있으므로, 값이 중복해서 들어오는 경우를 대비해 노드에 cnt 변수를 추가하여 같은 값이 들어올 때 cnt+=1만 하고 노드를 따로 생성하지는 않는 코드만 살짝 추가했다. 이진탐색트리는 최선의 경우(양쪽으로 잘 분배된 경우) O(logn), 최악의 경우(한쪽으로 쏠린경우) O(n)의 시간복잡도를 갖는다. -> 이를 해결하기 위해 양쪽 균형이..