[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)의 시간복잡도를 갖는다. -> 이를 해결하기 위해 양쪽 균형이..
[C] 백준 | 10773번 코드 - 제로
>문제 > 핵심 ..배열 인덱스? 스택 >풀이과정 실버 4길래 그래도 뭔가 좀 있지 않을까 했는데 매우 쉽게 풀었다. "정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다." 그러므로, "0"이 들어오면 앞에 무엇이든지 지울 숫자가 하나 이상은 있다는 이야기이다. 일단 e 에 정수를 입력받는다. idx = 0부터 출발 만약 e가 "0" 이라면, ar[--idx] = 0 으로 0 이전에 있던 값을 0으로 바꾼다. 만약 e가 "0" 이 아니라면, ar[idx++] = e 로 현재 위치한 인덱스에 값을 넣는다. 이렇게 반복문을 한번 돌고 난 이후에 다시 반복문을 돌면서 남아있는 값을 sum 하여 출력하면 끝. 문제를 풀고나서 다른사람이 쓴 코드를 보니까 원래는 스택으로 푸는 문제인 것 같았다. ..
[C] 백준 | 9012번 코드 - 괄호
>문제 > 핵심 스택 >풀이과정 어제 풀었던 4949번 문제랑 거~~의 똑같다. 어제 코드 조금만 고쳐서 냈다. '(' 가 입력으로 들어오면 스택에 push ')' 가 입력으로 들어오면 스택에서 pop. 이때 pop된 값이 반드시 '(' 이어야 짝이 맞음. 짝이 안맞는 경우 chk=0 후 break. 문자열을 다 돌고 나왔을때, 스택이 비어있지 않거나, chk = 0 인 경우 -> 짝이 안맞으므로 NO. 이외는 YES. 위 과정을 N번 반복!.. 인데 이대로 끝내기 아쉬워서 다른 방법을 사용한 코드도 한번 짜봤다. chk = 1, cnt = 0에서 시작해서 '('가 입력으로 들어오면 cnt+=1; ')'가 입력으로 들어오면 cnt-=1;. 깨달은점 스택은 어려웡 >코드 · 스택을 이용한 방법 #defin..