[Algorithm] BOJ 다리놓기 - 1010번

1. 문제 풀이 다리 놓기는 일직선 모양의 강의 동쪽과 서쪽에 다리를 겹치지 않게 놓을 수 있는 경우의 수를 구하는 문제이다. 서쪽과 동쪽에는 각 N개와 M개의 다리를 둘 수 있는 곳이 있고 0 > ca; //경우의 수 long long count = 1; for (int i ..

[Algorithm] BOJ 동전 1 - 2293번

1. 문제 풀이 n 가지 종류의 동전으로 그 가치의 합이 k원이 될 수 있는 경우의 수를 구하는 문제이다. 각각의 동전은 몇개라도 사용할 수 있다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 으로 주어진다. 우선 해당 값을 만들 수 있는 경우의 수는 값의 배수 일때 1번. 순열으로 만들었을때 두가지 동전으로 만들 수 있는 경우의 수 = 이전 동전으로 만들 수 있는 경우의 수 + 현재 동전으로 만들 수 있는 경우의 수 가 되는것이다. 이것을 점화식으로 인덱스에 기록해가며 더해가면 해당 동전들로 가능한 경우의 수를 구할 수 있다. 처음 첫 인덱스에 값을 1로 설정하고 그 뒤를 0으로 초기화해 처음 coin의 값이 들어갈 때 1이 더해지도록 했다. 2. 코드 #include using namespa..

[Algorithm] BOJ 팰린드롬? - 10942번

1. 문제 풀이 팰린드롬? 문제는 자연수 N 안에서 S번째와 E번째 수까지 팰린드롬, 곧 거꾸로 읽어도 제대로 읽는 것과 동일한지 알아내는 문제이다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. 우선 S부터 E사이의 차를 거리라 부르고 S와 E의 사이의 결과를 담을 이차원배열을 N*N 크기로 생성했다. 펠린드롬의 패턴은 S와 E 보다 1씩 줄어든 거리가 팰린드롬이고 S와 E가 같으면 팰린드롬이 되는 규칙을 이용해 하나씩 1로 채워가는 방식으로 풀이하였다. 거리가 0, 곧 같은 인덱스 일때는 1로 모두 초기화를 하고 거리가 1일때 j , j+1이 같으면 1로 설정했다. 거리가 2이상일때는 거리를 j , 대상인덱스를 z 로 while 문을돌려가며 z / j + z 가 같고 그 안에 직전 값이 1이..

[Algorithm] 알고리즘의 복잡도와 Big-O 란?

알고리즘이란 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들의 집합을 의미한다. 가는 루트는 다양하며 여러가지 상황에 따른 알고리즘은 모두 다르다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘을 수행할 때 연산이 몇번 이루어지는 지를 표기 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 빅오 표기법(Big O Notation) 복잡도를 표현할때에는 빅오 표기법을 ..