Algorithm

백준 1181번 Java 풀이

문제 풀이 방법 & 생각 과정 - 일반적인 백준 난이도 실버 5 문제와 다르게 생각할 거리가 많은 문제였다. - 문제를 보고 가장 먼저 중복을 우선적으로 제거해야겠다 라는 생각이 들었다. 이전에 프로그래머스에서 중복 제거를 위해 HashMap을 사용한적이 있어서, 해당 방법으로 중복을 제거했다. (다른 풀이 방법을 보니 조건 1,2를 먼저 처리한 후에 중복을 처리한 경우가 많았다.) - 조건1인 길이가 짧은 순 정렬은 객체 정렬할 때 쓰이는 Comparator의 메서드를 재정의하여 사용하였다.이 지점에서 문제가 발생했는데, 길이 순으로 정렬한 상태에서 Collection.sort를 사용하니 사전 순으로 정렬은 되었지만 길이 순 정렬이 깨져버렸다. (기존에 Comparator 메서드 재정의 한 것을 조건을..

DFS

- DFS(Depth First Search) 그래프 탐색의 한 종류 깊이 우선 탐색 Stack을 활용하여 데이터 탐색 * 구현 방법 1. 인접 행렬 - 행렬로 정점들 사이의 관계를 표현 하는 것 - 간선 방향의 존재 유무에 따라 표현하는 방법에 차이 존재 - 예시 - 용어 정리 (1) edge - 간선의 수 (2) vertex - 정점의 수 (3) map - 정점 간의 연결 정보를 담는 객체 (4) visit - 정점을 방문했는지 체크하기 위한 객체 2. 인접 리스트 - 인접 리스트 방식은 리스트 방식으로 각 정점이 연결 된 노드들이 정보를 저장한다. - 예시 - 인접 행렬과 다르게 모든 정점의 수를 나타내지 않고 한 정점과 연결된 것들만 보여준다. - 메모리를 신경써야 할 때 인접 리스트로 표현해주는..

다이나믹 프로그래밍

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 * 크다와 작다는 문제의 크기를 의미. - 큰 문제를 작은 문제로 나누는 알고리즘에는 2가지 종류가 있음 1. 다이나믹 프로그래밍(DP) 2. 분할 정복(D&C) * 다이나믹 프로그래밍은 작은 문제들이 중복이 가능하지만, 분할 정복은 작은 문제들끼리 중복이 되지 않는다. - 다이나믹으로 풀 수 있는 문제의 속성 1. Overlapping Subproblem : 겹치는 부분(작은) 문제 ex) 피보나치 수 : (0,1,1,2,3,5,8,13,21,34,55...) Fn = F(n-1) + F(n-2) 여기서 Fn이 큰 문제이고, 나머지 F(n-1)과 F(n-2)가 작은 문제라고 할 수 있다. 하지만 작은 것은 상대적인 개념이므로 F(n-1)을 구할 때는 F(..

알고리즘 기초 - 수학1

- 골드바흐의 추측 -> 2보다 큰 모든 짝수는 두 소수의 합으로 표현이 가능하다. * 아직 증명 되지는 않았지만 10^18 이하에서는 참인것으로 증명 되어있다. 백만 이하의 짝수중 임의의 숫자 N = a+b(a,b는 소수)를 만족하는지 검증하는 문제. 에라토스테네스의 체를 이용하여 Check[N-b]가 false인지 판별하면 된다. *N-b가 소수이면 a는 자동으로 소수가 되기 때문이다. - 팩토리얼 N! = 1 x 2 x 3 .... x N ex) 10! = 3628800 * 팩토리얼 0의 갯수문제 임의의 수 N!에서 0이 몇 개 인지 알아내는 문제. ex) 10! = 3628800 -> 0이 2개. c++ 또는 java에서 이를 실제로 계산하여 count 하면 시간이 엄청 오래걸리게 된다. -> 소..