SEO

동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -위키백과- 분할 정복과의 차이점 분할 정복은 큰 문제를 해결하기 어렵기에 작은 문제로 나누어 푸는 방법이다. 하지만 이 작은 문제가 포함된 큰 문제에서 이를 다시 풀어야 한다. 이러한 문제를 해결한 것이 동적 계획법이라고 할 수 있다. 동적 계획법은 큰 문제를 작은 문제로 나누어 푼다는 점에서 분할 정복과 유사하지만 작은 문제를 단 한번만 푼다는 점에서 차이점이 있다고 할 수 있다. 동적 계획법 풀이 한번만 푼 모든 작은 문제의 답을 어딘가(배열..

기록용 3줄 TMI 알고리즘 스터디 날짜가 조금씩 밀렸다. 이는 내가 나태해지고 있다는 걸 의미하는 것 같아 반성을 하고 있다. 이번주 활동부터는 정말 절대로 미루지 않을 것이다. 나는 약속을 정말 중요하게 생각하는데 활동이 밀리는 걸 보며 회의감이 든다. 백 트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. -나무위키- 라고 정의되어있긴 하지만 내가 생각하는 정의와는 좀 다르다..

기록용 3줄 TMI 어제 소소한 행복(?)이 있었다. 바로 C++ 프로그래밍 중간고사에서 최고점을 받았다!!! 사실 모든 학점이 나온게 아니고 단순히 중간만의 점수라 이렇게 좋아하는 이유가 이해되지않는 사람도 있을 것이다. 시험 하나로 이렇게 기쁜 이유는 1학기 내 프로그래밍 성적과 비교가 많이 되기 때문이다. 자세한 얘기는 끝인사에서... 처음에는 그냥 출력이 첫번째 숫자와 그 뒤에 이어지는 숫자를 나눴을 때 기약분수 형태구나라고만 생각했다. 그리고 무작정 코드를 구현하기 시작했다. 구현하면서 기약분수의 정의를 생각해보니 출력값 자체가 이 문제에 힌트라는 것을 알 수 있었다. 기약분수 : 분모와 분자를 최대공약수로 약분하여 1 이외의 공약수를 갖지 않도록 만든 분수를 뜻한다. 즉, 분모를 공약수로 나누..

기록용 3줄 TMI 시험 끝나고 첫 포스팅이다. 어제 시험이 끝났는데 오늘(11/3) 바로 스터디 준비에 들어갔다. 일단 딥러닝 강의도 슬슬 끝을 보이기 시작한다. 앞으로 일주일 뒤에 딥러닝 강의 수강이 끝나고 심화 프로젝트로 개발에 들어갈 것 같다. 이번주부터 양자컴퓨터 관련 공부 기록도 올라갈 것 같다. 정수론 : 각종 수의 성질을 대상으로 하는 수학의 한 분야 프로그래밍에서 정수론이 어떻게 활용될까? (코딩테스트에서 비주류 유형이라고 하지만 가끔 출제된다고 한다.) 1. 최대공약수/최소공배수 -> 유클리드 호제법 2. 에라토스테네스의 체를 사용한 소수 찾기 및 소인수 분해 3. 거듭제곱과 모듈러 연산 (더 있지만 쉽게 보기 힘든 유형이므로 생략) 먼저 최대공약수(GCD)와 최소공배수(LCM) -> ..

이 정렬 문제에 데이터는 최대 1000개로 작으니 단순 정렬과 버블 정렬을 사용하겠다. 버블 정렬은 시간이 오래 걸리는 편이지만 코드 구현이 쉬워서 많이 쓰인다고 한다. 관련 개념들은 아래 포스팅을 참고해주셨으면 한다. https://scorchingnraining.tistory.com/entry/%EA%B0%9C%EB%85%90%EC%A0%95%EB%A6%AC%EC%A0%95%EB%A0%ACnabi [개념정리]정렬_nabi 기록용 3줄 TMI 시험 공부를 하면 할수록 빨리 스터디를 다시 시작하고 싶은 마음이 커진다. 요새 갑자기 든 생각인데 공부를 하려면 항상 겸손해야하는 것 같다. 좀 감성적인 생각인 것 같지만 scorchingnraining.tistory.com 먼저 선택 정렬 코드이다. #incl..

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 흔히 유용하게 쓰인다. 이 알고리즘의 결과는 반드시 다음 두 조건을 만족해야 한다. 1. 출력은 비 내림차순(각각의 원소가 전 순서 원소에 비해 이전의 원소보다 작지 않은 순서)이다. 2. 출력은 입력을 재배열하여 만든 순열이다. -위키백과- 정렬이란 데이터를 일정한 규칙에 따라 재배열하는 것으로 오름차순 정렬과 내림차순 정렬이 있다. 위키백과에서 선택,삽입,버블 외에..

기록용 3줄 TMI 융합보안 논문 경진대회 준비를 위해 슬슬 양자컴퓨터에 대해 공부해야한다. 양자컴퓨터의 정의 정도는 알지만 그 이외내용은 찾아본적도, 공부해본 적도 없었다. 시험기간이 되니 느끼는 건데 동아리 활동이나 스터디 활동이 훨씬 힘들긴 해도 공부하는 과정은 비교도 안되게 재밌는 것 같다. Brute force란 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법 - 나무위키 나무위키에서는 브루트 포스의 정의를 위와 같이 표현하고 있지만 알고리즘의 측면에서 본다면 그 예시로 완전 탐색 알고리즘을 들 수 있다. 즉, 모든 경우의 수를 비교해보고 답을 찾아내는 알고리즘이다. (친구와 스터디 진행 후 좀 더 보완을 하면) 완전 탐색 알고리즘의 종류 중 브루트 포스가 있다는 말..

기록용 3줄 TMI 지난 일주일 정도 공개글 포스팅이 없었다. 지난 일주일간 재귀 2447번을 공개글로 업로드했어야했지만 끝까지 풀지 못했다. 하루에 3시간 정도 약 3일간 풀려고 노력했지만 결국 풀지 못했고 블로그 풀이를 이해하는데도 오랜 시간을 썼다. 블로그 풀이를 이해한 내용으로 작성해서 올릴까 생각도 했지만 내가 푼 풀이가 아니라 올리고 싶지 않았다. 브루트 포스는 완전 탐색 알고리즘으로 이 문제를 예시로 들면 모든 경우의 수를 계산해보고 가장 정답에 알맞는 것을 고르면 된다. 수능 공부 시절 이런 문제의 계산을 할 때의 방법을 이용해 풀었다. 1,2,3,4,5 다섯개의 계산을 하고 최댓값을 찾아야 하는 상황이라면 1,2,3 계산 후 1,2,4 -> 1,2,5 ->1,3,4 -> 1,3,5 -> ..