mondegreen

재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용한다. 하나의 큰 문제를 해결하기 위해 다소 해결하기 쉬운 작은 문제의 결과를 조합한다. 재귀함수(Recursive Function)함수 내부에서 자기 자신을 호출하는 함수로서기저 부분(basis part)와 유도부분(inductive part)으로 이루어져 있다. 함수 호출은 프로그램의 메모리 구조 중 스택을 사용한다. 반복적으로 스택을 사용하기 때문에 메모리 및 속도에서 성능 저하가 발생한다.  함수 호출 시 기저 부분이 작동하지 않으면 자기 자신을 무한 호출하여 stackoveflow 발생 // n!에 대한 재귀함수int fact(int n){ if(n** 반복과의 비교n이 커질수록 재귀가 반복보다 메모리와 연산속도 효..

0. 문제 1. 내 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cpNum = Integer.parseInt(br.readLine()); int[][] wP = new int[102][102]; for (int cP = 0; cP < cpNu..

검색이란 저장된 자료 중에서 원하는 항목을 찾는 작업으로서 자료를 구별하여 인식할 수 있는 키인 탐색 키를 가진 항목을 찾는 것이다. 검색의 종류 1. 순차 검색(sequential search) 2. 이진 검색(Binary search) 3. 완전 검색(Exhausting Search) 1. 순차 검색 일렬로 되어 있는 자료를 순서대로 검색하는 방법으로 가장 간단하고 직관적인 방법이다. 배열이나 연결 리스트 등 순차 구조로 구현된 자료 구조에서 원하는 항목을 찾을 때 유용하다. 알고리즘이 단순해 구현이 쉽지만, 검색 대상의 수가 많은 경우 수행시간이 급격히 증가해 비효율적이다. 1) 정렬되어 있지 않은 경우 첫 원소부터 순서대로 자료 구조의 마지막까지 검색 대상과 키 값이 같은 원소가 있는지 비교하며 ..

정렬이란 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 순서(오름차순) 또는 그 반대의 순서로(내림차순) 재배열 하는 것을 말한다. 제한이 있는 경우 또는 특수한 경우가 아니면 quick sort(Arrays.sort /Collection.sort)를 활용해 정렬하자. -> 괜히 복잡도 늘리지 않기 정렬에서의 키: 자료를 정렬하는 기준이 되는 특정 값 정렬의 종류 1. 버블 정렬 -> 버블정렬 시간 복잡도 O(n^2) 2. 선택 정렬 -> 선택정렬 시간 복잡도 O(n^2) 3. 삽입 정렬 -> 삽입정렬 시간 복잡도 O(n^2) 4. 카운팅 정렬 -> 카운팅 정렬 시간 복잡도 O(n+k) 5. 병합 정렬 -> 병합 정렬 시간 복잡도 O(nlogn) 6. 퀵 정렬 -> 퀵 정렬 시간 복잡도 O(n..

알고리즘은 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법으로서 컴퓨터 용어로 쓰여 컴퓨터가 어떠한 일을 수행하기 위한 단계적 방법을 말한다. 컴퓨터 분야에서 알고리즘을 표현하는 방식은 순서도와 의사코드 두 가지가 있는데 전자는 유연성이 떨어지기 때문에 의사코드(흉내만 내는 코드로서 정해진 규칙은 없지만 이해 가능하게 작성하고 독해능력 필요)를 많이 사용한다. 좋은 알고리즘의 기준 1. 얼마나 정확하게 동작하는가(정확성) 2. 최소의 연산으로 원하는 결과는 얻는가(작업량) 3. 얼마나 적은 메모리를 사용하는가(메모리 사용량) 4. 얼마나 단순한가(단순성) 5. 최적화되어 있는가(최적성) 알고리즘의 작업량은 시간 복잡도(Time Complexity) 로 성능을 판단할 수 있는데 빅 - 오 표기법을 활..

알고리즘이 잘 풀리지 않을 때 1) '변수를 적극 활용하자'는 것과 2) '코드를 따라가며 시뮬레이션을 하자'고 생각한다. 1) 변수활용: 개인적으로는 기존에 입력한 코드에 갇혀서 사고의 틀이 제한되기 때문에 습관적으로 변수 활용을 생각한다. 2) 시뮬레이션: 코드 작성 전에 떠오른 대로 코드가 맞을 것이라고 생각하지만.. 항상 오류가 발생한다. 그 때 내가 작성한 코드의 결함을 발견하기 위해서는 테스트 케이스를 한 개 정하고 코드 수행에 따른 단계적 결과를 확인해본다. 이 두 가지는 너무 당연한 과정이지만 마음만 조급해져서 자꾸 놓치고, 결국에는 한참 뒤에야 다시 밟게되는 과정이었다. 앞으로는 코드 작성 초반부터 습관을 들여야겠다. 0. 문제 1. 내가 작성한 코드 package algorithm.BA..