코린이의 코딩일기 코린이의 코딩일기

브루트 포스(brute force)완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.브루트 포스의 장점은 예외없이 100%의 확률로 정답을 찾아낸다는 것이다. 대부분 반복문과 조건문을 통하여 답을 도출한다. 모든 경우의 수를 전부 탐색하기 때문에, 100%의 확률로 정답을 찾아내지만,모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다.  완전 탐색과 브루트 포스 알고리즘의 차이 완전 탐색 알고리즘 : 모든 경우의 수를 전부 탐색하는 방식의 알고리즘, 결과보다는 탐색 과정에 중점을 둔다.브루트 포스 알고리즘 : 문제를 해결하기 위해, 모든 경우를 탐색하고 답을 도출하는 알고리즘, 결과를 찾는 것에 중점을 둔다. 브루트 포스의 기본적인..

https://www.acmicpc.net/problem/1074  # 접근방식  # 소스코드  # 성능  # 회고

분할 정복 알고리즘 한 번에 해결할 수 없는 큰 문제를 작은 문제들로 분할하여 작은 문제들 부터 문제를 해결하는 방법이다.분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현한다.  분할 정복 동작과정 Divide원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다. Conquer각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위라면 탈출 조건을 설정하고 해결한다. CombineConpuer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.  장점Top-dwon 재귀방식으로 구현하기 때문에 코드가 직관적이다.문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결할 수 있다. 단점 분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하기..

https://www.acmicpc.net/problem/1012# 문제 # 접근방식DFS, BFS 모두 사용할 수 있다.배추의 위치 2차원 배열인 arr와 방문을 체크하는 2차원 배열인 check를 이용한다.배추가 드문드문 나기 때문에 arr를 모두 탐색하면서 1인 좌표를 찾아야한다.1인 좌표를 찾으면 그 좌표의 상, 하, 좌, 우를 탐색하면서 1이고 방문하지 않은 좌표를 찾는다.이 부분을 DFS로 나타내면 된다,m과 n의 범위에서만 찾도록 해야한다. # 소스코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class ..

메모이제이션(Menoization) 동일한 문제를 반복해야하는 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식이다.메모이제이션을 이용하면 중복 계산을 줄일 수 있다. 메모이제이션 방법으로는 TOP-DOWN 방식과 BOTTOM-UP 방식이 있다. TOP-DOWN 문제 해결이 위에서부터 아래로 진행되는 방식이다.int arr[] = new arr[t];int fibonaci(int n){ if(nfibonaci(10)을 호출하면 fibonaci(10)부터 작은 수를 호출하며 가장 작은 수까지 도달하게 된다.  BOTTOM-UP 문제 해결이 아래에서부터 위로 진행되는 방식이다.int fibonaci(int n){ arr[0] = 0; arr[1] = 1; for(int i=2; ifibo..

동적 계획법을 이해하려면 피보나치 수열부터 알아야한다.동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있기 때문이다.  피보나치 수열(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 143 ....피보나치 수열은 제 2항까지 1을 반환, 제 3항부터는 바로 앞의 두 항을 더한 수로 정의된다.(제 0항은 생략할 수 있다.) 피보나치 수열은 재귀를 통해 표현할 수 있다. 재귀란  (자신)함수를 다시 호출하는 방식이다.int fibonaci(int n) { if(n  하지만 피보나치 수열은 중복이 생기게된다. 그렇기 때문에 동적계획법을 사용하게된다. 동적계획법 피보나치와 재귀를 통해 표현한다는 점에서 비슷하지만, 동적계획법에서는 처음 진행되는 연산은 기록해 두고, 이미 진행..

https://www.acmicpc.net/problem/1094 # 문제  # 접근방식지민이가 가지고 있는 막대기가 x와 같을 때까지 2로 나누어주는 방식이다.반으로 나눈 값들을 합한 것이 x와 같으면 출력해주면 된다. while문을 사용하여 x > 0일때까지 반복해준다.지민이가 가지고 있는 막대기(stick)가 x보다 크면 stick/2를해준다.stick이 x와 같거나 작다면 count++해준다. count했기 때문에 x에서 stick값만큼 빼준다. # 소스코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main..

https://www.acmicpc.net/problem/1032 # 문제  # 접근방식N만큼 파일 이름을 입력받아 String배열에 입력해준다.charAt( )으로 파일이름을 비교한다.boolean형 변수를 이용하여 String배열에 저장된 파일 이름 중 같은 자리에 다른 문자가 있으면 false로 바꾸어 출력한다. # 소스코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..