그리디 알고리즘 (탐욕 알고리즘) 이란? 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함수와 전역 변수를 쓰면 쉽게 풀리는데 이는 다른 알고리즘에서 자중하..

가끔 인강 영상들을 보다보면 배속기능이 없는 강좌들이 있다. 물론 무조건 학생들이 처음부터 끝까지 다 보라는 마음에 조작 키들을 없애버린 것 이겠지만,, 21세기에 살고 있는 우리들에겐 이런걸 듣고 있을 시간이 없다.. 내가 웹을 공부하고 나서 보니, 결국 웹을 만든 것도 사람이다. 결국 보안을 철저히 하지 않는 이상 헛점이 들어날 수 밖에 없고, 웹을 공부하고 있는 사람으로써 이런건 못참는다..ㅎ 본론으로 돌아가, 우리 학교 웹 사이트를 기준으로 설명을 하겠다. 우선 개발자 도구(일반적으로 F12)를 열어서 그림에 커서가 가리키고 있는 버튼을 눌러준다. 그리고 웹사이트에 커서를 대면 이것저것 뜰텐데, 커서를 영상파일에 가져다 대고 클릭하면 해당 영상의 HTML Element를 가리켜 준다. 위 그림에서..

몬테 카를로(Monte Carlo) 방식은 무작위로 추출된 난수를 이용하여 함수의 값을 계산하는 통계학의 방법이라고 한다. 위 이미지의 코드와 같은 경우에는 다음과 같이 이용되었다. (여기서의 난수라 함은 0~1 사이의 값을 얘기한다.) 1. 난수 값을 r1에 저장한다. 2. r1이 난수일 확률 probability를 계산한다. (probability = r1 으로 둔다.) 3. 또 다른 난수 r2를 저장한다. 4-1. r2가 probability 보다 크다면, 작은 보폭을 선호. 4-2. r2가 probability 보다 작다면, 큰 보폭을 선호. 5. 두가지 경우 중, 원하지 않는 결과라면 1로 돌아가고 원하는 결과면 r1을 return 한다. 그리고 Math.random을 사용하는 과정에서 최소값,..