[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..
[C] 백준 | 4949번 코드 - 균형잡힌 세상
>문제 > 핵심 문자열 입력 스택 >풀이과정 괄호 비교! 자료구조 수업에서 스택을 배워본 사람이라면 한번쯤 만들어본 코드일 것이다. 나도 그럴 줄 알고 쉽게 만들 수 있을 줄 알았는데 스택도 오랜만에 하다보니 가물가물해서 쪼끔 시간이 걸렸다. 이 문제를 통해서 문자열 입력에 대해 다시 공부할 수 있었다. >>문자열 입력 함수 · scanf("%s", ar) scanf의 %s는 개행문자(\n), 공백문자, 탭 문자 직전까지를 하나의 문자열로 인식한다. 그래서 scanf를 이용해 "Hello World"를 입력한다면, 출력할때 "Hello"까지밖에 나오지를 않는다. 그리고, 이 scanf가 개행문자 직전까지만 문자열로 입력을 받으므로, 내가 입력했던 엔터('\n')이 버퍼에 덩그러니 남게된다. 그래서!! s..