댕댕아 코딩하자

>문제 www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net > 핵심 피보나치 수열 DP >풀이과정 DP 문제라길래 DP스럽게 풀어보려고 했다. 맞게 푸는건지 모르겠네 메모이제이션을 하기 위한 배열을 int형이 아니라 구조체 배열로 만들어서 A와 B의 개수를 따로따로 세기 편하도록 했다. 꼭 구조체가 아니더라도 A, B 두가지 경우밖에 없기 때문에 이차원배열을 통해서 구분해도 될 것 같다. 크게 어렵지는 않았다! >깨달은점 모르겠다 BABA! >코드 #define _..

>문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net > 핵심 배열 >풀이과정 쉽다. 처음엔 연결리스트로 할까 생각하다가 시간이 오래걸릴 것 같아서 그냥 배열로 때려박았다. >깨달은점 쉽다. >코드 #define _CRT_SECURE_NO_WARNINGS #include #include int main() { int i, m, e; char op[10]; int numset[21] = { 0 }; scanf("%d", &m); for (i = 0; i < m; i++) { scanf(" %s", op); if (strcmp(op, "add") ..

>문제 > 핵심 에라토스테네스의 체 >풀이과정 소수 구하기 문제. 이거 어디서 본 것 같은데?? 백준 1978번 문제 >> sedangdang.tistory.com/18?category=969000 [C] 백준 | 1978번 코드 - 소수찾기 >문제 > 핵심 반복문 돌기. 효율적인 알고리즘을 강구해보자. >풀이과정 [소수 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. ] 소수 찾기 알고리즘 기본서에 꼭 나오는 내용으로 기 sedangdang.tistory.com 이미 풀어본 문제다! 다만 저 문제는 1000 이하의 소수를 찾는 것이고 이 문제는 백만까지의 소수를 구해야 하는 것이라는 큰 차이가 있다.. 그래서 이 문제는 넓은 범위에서 소수를 찾을때 유용하게 쓰이는 알고리즘인 를 이용했다..

>문제 > 핵심 브루트포스 알고리즘 (모든 경우를 다 따져보는 방법) >풀이과정 아.. 어렵다 혼자 끙끙 생각하다가 도저히 생각이 안나서 다른사람이 쓴 아이디어를 보고나서야 풀었다.. 풀고나서야 그렇게 어려운 문제가 아니었다는걸 깨달았다.. 코딩은 나의 길이 아닌가 내가 생각한 방법 1. 블록의 높이를 입력받으면서 가장 높은 max, 가장 낮은 min 값을 찾는다. 2. max층부터 min층까지 층층이 탐색하면서, 2-1. 현재 높이에서 구멍이 몇칸 뚫려있는지 구하고 2-2. 인벤토리에 있는 블럭으로 그 구멍을 다 메꿀 수 있으면 메꾸고 break. 2-3. 메꿀 수 없으면 한층 더 파고 내려가기 3. 그렇게 돌면서 모든 블럭이 평평하게 맞춰진다면 break 후 총 걸린시간 출력.. 하는 구조를 생각했었..

>문제 > 핵심 이분탐색 long long형 >풀이과정 이 문제,, 어딘가 낯이 익다 했더니 1654번 문제 "랜선 자르기" 랑 구조가 거의 똑같다!! 그래서 나무의 최대 길이가 2,000,000,000이라는 점에서 int형이 아니라 long long 형을 사용해야 한다는 점을 잊지 않고 사용해서 어렵지 않게 문제를 풀 수 있었다. 우선 나무의 길이를 입력받으면서 가장 긴 나무의 길이를 max에 저장한다. 그리고 이분탐색을 위해 left = 0, right = max (left 깨달은점 한번 풀어본 유형은 어떻게 풀어야겠다는 감이 빨리 온다는걸 이 문제로 느꼈다. 클래스 2는 이제 거의 다 풀어가는데 앞으로도 계속 다양한 유형의 문제를 접해봐야겠다. >코드 #define _CRT_SECURE_NO_WAR..

>문제 > 핵심 큐 >풀이과정 이 문제를 풀다가 돌아버릴 뻔 했다. 문제를 풀고 나니 모두 나의 무지에 의한 것이였다. 내가 겪었던 문제점 1. 내가 원하는 문서가 언제 출력되는지 어떻게 알아? 큐의 front에 있는 값이 현재 큐에서 가장 중요도가 높은 문서라면 dequeue를 진행하고, 그렇지 않다면 dequeue 후 맨 뒤에 enqueue 한다. 근데 처음에 m번째 위치에 있는 문서가 enqueue, dequeue를 거치며 순서가 뒤죽박죽 섞이는데 언제 출력될지 어떻게 알까..? 곰곰이 생각하다가,, int[SIZE][2] 배열을 쓸까 생각하다가 이건 큐로 만들기 조금 복잡할 것 같아서 구조체! Paper을 만들어서 구조체 배열을 갖는 큐를 만드는 방식을 사용했다. Paper 구조체에 중요도를 넣는..

>문제 > 핵심 스택 >풀이과정 문제가 뭔소린가.. 싶어서 문제를 이해하는데 조금 시간이 걸렸다. 그래도 이해하고 난 후 코드를 짜는건 크게 어렵지 않았다. num=1부터 오름차순으로만 증가!. (e : 입력값) 1. 스택의 Top e : e에 도달하기 전까지 pop, num은 고정. 3. 스택의 Top != e : 수열을 만들 수 없음. chk = 0 으로 체크 후 break. 4. 스택의 Top == e : 해당 값을 pop 하고 위 과정 반복. 하나 고려해야 할 점은 정수를 입력받고 나서 바로 + 혹은 - 를 찍으면 안되고, 모든 정수를 입력받은 후에 만들수 있는 수열인지, 아닌지 체크를 한 다음 정답을 출력해야하므로 따로..

>문제 > 핵심 이분탐색 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..