문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 설명 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5 일때의 예제를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하여라. 표에 채워진 수는 모두 다르다. 풀이 방식 문제 자체는 이해하는데 있어 어렵지 않다. 쉽게 변..

분할 정복 (Devide & Conquer) 이란? 한 번에 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 알고리즘. 분할하여 푼 문제들을 다시 합병하여 문제의 답을 얻음 주로 재귀함수로 구현하여 나눌수 없는 순간까지 나눔. 분할 방법에 따라 시간 복잡도는 천차만별. 구현 방법에 따라 시간 복잡도가 다양하다. 입력범위 N이 큰 편이다. 재귀 함수를 구현할 때에는 무한루프에 빠지지 않도록 기저조건을 확실히 해야한다. 분할 정복의 순서 Devide: 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. Conquer: 나누어진 문제에 대해서 해결을 한다. 만약 더 쪼개질 수 있다면 Devide과정을 수행한다. Combine: Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. 문제를 제대..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 오르막 수는 수가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. - 가능: 2234, 3678, 11119 - 불가능: 2232, 3676, 91111 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라. 0으로 시작가능. 풀이 방식 다음 이미지대로 하면 된다. 이게 DP의 방식 인지는 모르겠는데.. 이전의 값을 가지고 와서 현재의 값을 만들어 낸다. 다음..

그리디 알고리즘 (탐욕 알고리즘) 이란? Greedy는 '탐욕스러운, 욕심 많은' 이라는 뜻이다. 그리디 알고리즘은 선택하는 순간마다 당장 최적의 상황만을 선택해 최종적인 해답에 도달하는 방법이다. 그리디 알고리즘은 최적의 해를 구하는 데에 사용되는 근사적인 방법이다. 순간마다 선택하는 답은 그 순간에서는 지역적으로 최적의 답일 순 있지만, 그 선택들을 계속 수집하여 나온 최종적인 답은 최적이 아닐 수 있다. 시간적으로 매우 효율적임. 수학적 증명이 요구되는 사항이 많음. 코딩 테스트의 경우 비슷한 문제나 직관에 의해 판단 할 수 있도록 문제가 주어짐. 그렇기에 많은 문제를 풀어서 감을 익힐 수 있도록 해야함. 예시 루트 노드 7에서 시작해서 10과 12의 대소관계를 파악한다. 더 큰 12를 택한 후 다..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구해야 한다. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 풀이 방식 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 다음 n = 5일때 다음과 같은 삼각형이 있다고 하자. 다음 풀이의 핵심은 이전 값의 계산을 ..

백트래킹 이란? 완전 탐색을 하던 도중, 현재의 탐색이 무의미한 경우 되돌아가는 알고리즘을 의미한다. 말 그대로 모든 경우의 수에 대해서 탐색을 하던 도중, 조건과 맞지 않을 경우에 대해서는 탐색을 하지 않고 돌아간다는 뜻이다. 유명한 문제로 N-Queens 문제가 존재한다. 특징 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다. 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에, 재귀를 사용해야 하는 경우가 많다. 조건에 맞지 않는 다면, 이전의 어떤 지점으로 돌아갈 지 정하는 것이 중요하다. 가지치기를 어떻게 구성하느냐에 따라 코드의 효율이 달라진다. 주로 백트래킹을 구현하다 보면, void함수와 전역 변수를 쓰면 쉽게 풀리는데 이는 다른 알고리즘에서 자중하..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 오름차순의 수열을 구하는 프로그램을 작성해야 한다. 풀이 방식 A = { 70, 30, 50, 60, 70, 0, 10} 다음과 같은 수열이 있다고 하자. brute force식으로 구해보면 다음과 같다. 어떻게 해도 이 블로그 보다 설명을 잘 할 수 없으니 모르겠다면 참고 하도록 하자. 백준 11053번 가장 긴 증가하는 부분 수열 파..

요새 기초적인 물리나 수학적인 부분들을 공부한다고 프로그래밍에 별로 신경을 못쓰고 있다. 그러다 보니 실력이 예전만하지 않다.. 반성 또 반성.. 여튼 시간날때 Javascript로 Nature Of Code 책을 참고해서 하나 만들어 보았다. 사실상 개념은 아래 글과 거의 똑같다. Javscript의 Math.random과 정규분포에 대해 요새 Nature of Code 라는 책을 간간히 보고 있는 중인데, Javascript의 Math.random 이라는 함수가 단순히 난수를 생성하는 지 또는 정규분포를 나타내는지 궁금하여 알아보게 되었다. 수학적 지식이 뛰 so-tired.tistory.com 대학에서는 파이썬 배우던데.. 이것도 공부해놔야 하나..ㅋㅋㅠㅠ