도누의 기록

10 조합 10-1 조합 알아보기 조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다. 1. 특정 문제를 가정하기 2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기(★) (예를 들어 5개의 데이터중 앞의 4개는 이미 선택이 완료된 데이터로 가정하고 마지막 데이터를 선택함과 선택안함으로 나누어 전체를 표현한다.) 3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기 (일반) 11 동적계획법(DP) 11-1 동적 계획법 알아보기 동적계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 1. 큰 문제를 작은 문제로 나눌 수 있어야 한다. 2. 작은 문제들이 반복돼 나타..

08 그래프 8-1 그래프의 표현 (중요) 1. 에지 리스트 - 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다. (방향이 없는 그래프라면 [1,2] , [2,1]은 같은 표현이다.) - 가중치가 있는 그래프는 행을 3개로 늘려 가중치를 저장하면 된다. - 구현하기는 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다 (시간 복잡도 큼) - 에지 리스트는 벨만포드나 크루스칼 알고리즘에 사용 2. 인접 행렬 - 2차원 배열을 자료구조로 이용하여 그래프를 표현함. - 에지 리스트와 다르게 노드 중심으로 그래프를 표현함. - 인덱스를 활용하여 표현 A[3][4]는 3에서 4를 향하는 엣지이다. - 가중치가 없으면 해당 2차원 배열에 1을 넣고 가중치가 있으면 ..

06 그리디 알고리즘 6-1 그리디 알고리즘 그리디 알고리즘은 현재 상태에서 보는 선택지 중 best 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 즉, 부분의 best가 전체의 best이다. 하지만 항상 최적의 해를 보장하지는 않는다. 따라서 그리디 알고리즘을 적용할 수 있는 문제인지 아닌지를 파악하는 것이 중요하다. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적정설 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. 07 정수론 7-1 소수 구하기 소수는 1과 자기 자신 외에 약수가 존..

5-1 깊이 우선 탐색 (DFS) 깊이 우선 탐색은 그래프 완전 탐색 기법중 하나로 그래프의 시작 노드에서 출발하여 한쪽 분기를 정한 후 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 시간 복잡도는 O(노드 수 + 에지 수)이다. 재귀 함수로 구현 스택 자료구조 이용 (후입 선출) 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로를 유의해야 한다. DFS로 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬등의 문제를 풀 수 있다. DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현한다. DFS 구현은 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현합니다. 1. 우선 DFS를 시작..

04 정렬 정렬에는 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 기수정렬등이 있음. 4-1 버블 정렬 버블 정렬은 인접한 데이터의 크기를 비교해 정렬하는 방법으로 구현은 간단하지만 시간복잡도가 O(n^2)로 다른 정렬보다 느린 편이다. loop를 돌면서 인접한 데이터끼리 swap해서 정렬한다. 버블 정렬 과정 비교 연산이 필요한 루프 범위를 설정하고 인접한 데이터 값을 비교한다. swap 조건에 부합하면 swap 연산을 수행한다. 루프 범위가 끝날 때까지 위를 반복한다. 정렬 영역을 설정하고 다음 루프를 실행할때는 이 영역을 제외한다 (이미 정렬된 영역임) 비교 대상이 없을 때 까지 위를 계속 반복한다. 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데..

03 자료구조 3-1. 배열과 리스트 배열과 리스트는 비슷한 점이 많지만 두 자료구조의 특징을 정확하게 이해하고 문제가 요구하는 조건에 따라 적절하게 선택해 사용하는 것이 중요 배열 배열은 메모리 연속 공간에 값이 채워져 있는 형태의 자료구조로 인덱스를 통해 참조할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. (주변에 있는 값을 이동시키는 과정 필요) 배열의 크기는 선언할 때 지정할 수 있으며, 한번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하므로 코딩 테스트에서 많이 사용한다. 리스트 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조입니다. 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야한다. (즉, 접근하는 속도가 느..

01 시간복잡도 1. 시간복잡도 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산횟수로 일반적으로 수행 시간은 1억번의 연산을 1초의 시간으로 간주하여 예측 코딩테스트에서는 빅-오 표기법을 기준으로 계산해야한다 (최악의 경우) 예를 들어 시간 제한이 2초면 2억번의 연산안에 문제를 해결해야함 즉, 연산 횟수 = (알고리즘 시간 복잡도) * (데이터의 크기) < 200,000,000번 이어야함 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있음 02 디버깅 2. 디버깅 반드시 할 줄 알아야 함. 로그 찍어보는 것보다 훨씬 편함. - 디버깅 방법 코드에서 디버깅..

- 상수 표현 final int y = 30; - 데이터 타입 //정수 long l = 30L; int x = 30; short s = 30; byte b = 30; //실수 double dd = 30.0; float ff = 30.0f; boolean isMarried = true; isMarried = false; char c ='a'; // 거의 잘 안씀 char cc = '한'; String str = "여러 글자"; - 문자열 출력 System.out.printf("저는 %s입니다. 나이는 %d살이고요, 키는 %f cm 입니다. \n", "홍길동",20,180.5f); String str2 = String.format("저는 %s입니다. 나이는 %d살이고요, 키는 %f cm 입니다. \n", "..