참고 :https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98https://hongcana.tistory.com/41 1. 그리디 알고리즘(Greedy Algorithm)이란? 매 선택에서 지금 당장에 최적인 답을 선택해 적합한 결과를 도출하는 알고리즘을 그리디 알고리즘이라고 한다. 그리디 알고리즘에서 선택된 답은 항상 최적이 될 수 없다는 것을 알아야한다. 브루트포스 알고리즘처럼 선택할 수 있는 모든 길을 분석한 후 최적의 답을 뽑아내는 것이 아닌 그 순간마다의 최적의 경로를 찾기 때문이다.  그리디 알고리즘은 최적 부분 구조 특성을 가지는 문제에 대한 해답을 뽑아낼 때 유용하다. 즉, 한 번의 선택이 ..

1. 문제 하노이의 탑 문제이다. 옮긴 횟수와 n 2. 하노이의 탑 하노이의 탑은 퍼즐의 일종이다. 세 기둥과 여러개의 원판이 있고 원판은 한 기둥에 순서대로 쌓여있다. 하노이의 탑은 규칙 3가지를 지키면서 한 기둥에 있는 원판들을 다른 기둥에 순서 그대로 옮겨야한다. 더 작은 원판 위에 더 큰 원판을 올릴 수 없다.가장 위에 있는 원판만 옮길 수 있다.한 번에 한 개의 원판만 옮길 수 있다. 하노이의 탑 문제는 재귀 함수를 이용해서 풀 수  있는 가장 유명한 예제 중 하나라고 한다.한 기둥의 n장의 원판을 다른 기둥으로 옮기기 위한 최소 횟수는 2^n - 1 이다. 하노이 타워에 대한 프랑스 수학자 Edouard Lucas 가 만든 유래도 있으니 찾아보길 바란다. 3. 풀이앞서 말했듯이 하노이 탑 문제..

1. 문제 ㄱ자 모양을 여러 각도로 돌린 모양의 참외밭에서 자라는 참외의 수를 출력하는 문제이다. 1m^2당 참외의 개수는 k로 입력 받고 참외밭의 면적은 동서남북으로 선 하나하나 입력 받는다.  2. 풀이이번 포스트에서는 큰 직사각형 면적에서 작은 직사각형 면적을 빼는 방식으로 풀었다.  큰 직사각형 면적은 가장 긴 가로 길이와 가장 긴 세로 길이의 곱으로 구할 수 있다. 그리고 작은 직사각형 면적은 큰 직사각형 면적에서 제외하는 방식으로 구할 수 있다.즉, 가장 긴 가로 길이와 반대편에 위치한 동/서 방향의 가로 길이와 가장 긴 세로 길이와 반대편에 위치한 남/북 방향의 세로 길이의 곱으로 구한다. 반대편 길이를 구하기 위해 두 가지를 알아야한다. 변이 6개, 육각형으로 가정가장 긴 길이의 위치를 찾..

1. 문제  실수 a의 b제곱을 정확하게 계산하는 문제이다. 지수 연산 문제로, 얼핏 보면 쉬운 문제며 코드도 짧다.   2. 지수 연산지수 연산이란, 어떤 수를 여러번 곱하는 것을 말한다. 즉, 문제의 제목인 a^b 는 a를 b번 곱한 값이 된다.a^0 = 1a^1 = aa^b * a^c = a^(b+c)등의 성질이 있다.  3. 풀이a^b를 정확하게 계산하고 출력하기 위해서 BigDecimal이라고 하는 자바에서 매우 큰 소수나 정수를 정밀히 다룰 수 있는 클래스와 지수 연산을 하기 위해 .pow()를 사용해서 코드를 짰다. 4. 코드 오답 코드 1 import java.util.*;import java.math.*;class Main { public static void main(String[..

1. 문제 에라토스테네스의 체에 관한 문제이다. 관련 알고리즘 로직을 알고 응용해서 푸는 문제이다. 2. 에라스토스테네스의 체란?참고 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 2부터 소수를ko.wikipedia.org 에라토스테네스의 체란, 소수를 빠르게 찾는 알고리즘 중 하나이다. 특정 범위 내에서 소수를 판별할 때 효과적..

백준 2740번 행렬 곱셈에 대한 C, C++ 코드를 풀이해보자.백준 2740번 : https://www.acmicpc.net/problem/2740 1. 문제  선형대수학의 행렬곱 문제이다.N*M 크기의 A배열과 M*K 크기의 B배열의 곱을 구해야한다. 2. 행렬곱결과 행렬의 크기는 A의 행과 B의 열의 곱이다. 따라서 A의 열의 개수와 B의 행의 개수가 같아야 구할 수 있다.행렬곱의 각 원소는 간단히 말해서, A의 행과 B의 열을 곱한 후 합산해서 구한 값이다.따라서 결과 행렬 C의 i행 j열은 A의 i행과 B의 j열의 원소들을 각각 곱한 후에 모두 더한 값이 된다. 3. 풀이다시 문제로 돌아가서 행렬곱을 이용해 예제 문제를 풀어보면,  4. 코드풀이한 문제를 코드로 구현해보자. 아래는 C언어 코드이..