hail2y.log

책 [JAVA 언어로 배우는 디자인 패턴 입문 3판;유키 히로시 저]을 참고하여 작성하였습니다. 1. Strategy 인터페이스(API)2. 구체 전략 클래스3. Strategy를 사용하는 곳 (Player) Player에서 어떤 Strategy 전략 클래스를 이용해 게임을 한다고 가정한다.  Player와 같이 Strategy를 사용하는 곳에서 구체 클래스가 아니라 인터페이스를 이용해 코드를 짜면 Strategy에 뭐가 들어오든지 간에 '어떤' 전략을 사용할 수 있는 것이다. (Player는 넓은 시야에서 프로그램을 어떻게 전개시킬지 정한다.) 다시 말해 Main 클래스에서 new Player(new RandomStrategy())와 같이 Playe 객체를 생성할 때 매개변수로 내가 Strategy 인..

책 [JAVA 언어로 배우는 디자인 패턴 입문 3판;유키 히로시 저]을 참고하여 작성하였습니다. 추상 클래스- 템플릿 메서드에서 추상 메서드 사용- 이 추상 메서드를 구현부에서 구현- 상위 클래스에서는 처리의 뼈대(알고리즘)를 결정- 구체적인 처리 내용은 하위 클래스까지 가야 결정되지만, 추상 클래스 단계에서 처리 흐름을 형성할 수 있다.  구현 클래스 - 하위 클래스에서 그 구체적 내용을 결정 메인부 로직을 공통화할 수 있다 ... 공통된 알고리즘, 유지보수 관점상위 클래스와 하위 클래스의 연계 플레이 ... 상위 클래스의 소스 프로그램 없이 하위 클래스의 구현이 어려울 수 있다하위 클래스를 상위 클래스와 동일시한다 - 상위 클래스형 변수에 하위 클래스의 인스턴스 중 어느 것을 대입해도 제대로 동작할 ..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  다익스트라(Dijkstra) 알고리즘출발 노드와 모든 노드 간의 최단 거리 탐색 (출발 노드와 도착 노드, 두 노드만이 아님)에지(가중치)는 모두 양수여야 한다시간 복잡도는 O(E * logV)그리디 알고리즘- 접근 방법그래프를 인접 행렬, 인접 리스트로 구현할 수 있지만 일반적인 경우에서 인접 리스트가 더 빠름, 하지만 상황에 따라 달라짐- 인접 행렬 O(V^2) - 밀집 그래프에 유리, 연결 노드 확인하는 데 O(1)- 인접 리스트 O(E * log V) - 희소 그래프에 유리, 연결 노드 확인하는 데 O(연결된 간선의 수)최단 거리 배열을 초기화 (최댓값으로 모두 채우기)거리 배열에 출발 노드 인덱스에 0..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  이 글은 증명보다는 방정식의 해를 구할 때 어떻게 접근해야 하는지 설명한다.유클리드 호제법이 두 수의 최대공약수를 구하기 위한 것이라고 보면, 확장 유클리드 호제법은 방정식의 해를 구하는 것이라고 볼 수 있다. 이름에서 알 수 있듯이 확장 유클리드 호제법은 기본 호제법을 알고 있어야 진행된다ax + by = c주어진 a, b, c, x, y는 모두 정수라고 생각한다. 이때 x, y의 해는 c % gcd(a,b) = 0 조건이 성립되어야 정수해를 구할 수 있다. 그렇기 때문에 문제에 접근할 때 먼저 c의 값이 gcd(a,b)의 배수가 맞는지 확인부터 해야 한다. 배수가 맞다면 일차 조건은 만족한 것이다. c가 g..

모듈러 연산을 활용해 분배 법칙을 하면 우리가 흔히 분배 법칙으로 기대하는 결과와는 차이가 있다. (A + B) % C = (A % C + B % C) % C(A - B) % C = (A % C - B % C + C) % C (A * B) % C = ((A % C) * (B % C)) % C(A / B) % C = (A * B^(-1)) % C = ((A % C) * (B^(-1) % C)) % C뺄셈의 경우 추가적으로 +C를 해주었는데 이러면 나머지 결과가 0 이상임을 보장할 수 있다. 코딩할 때 사실 결과로서 위 법칙만을 기억해도 괜찮을 것 같아서 증명 과정이 필요할까 싶지만... 과정을 알면 나중에 더 쉽게 기억할 수 있을 것 같아 첨부한다. 증명은 더하기만 확인해 보기로 한다. 어려워 보일 수 있..

(학교 수업 자료를 참고하여 작성하였습니다.) DFS, BFS는 탐색 알고리즘으로 브루트포스에 포함된다. 주로 그래프와 트리를 순회할 때 사용되고, 탐색 방법과 목적에는 약간의 차이가 있다. 그치만 코딩테스트 문제들에서 DFS, BFS를 따지지 않고 탐색만 하는 것으로 해결되는 경우도 많다고 한다. 그래프: 연결되어 있는 객체 간의 관계를 표현하는 자료구조트리: 그래프의 한 종류로, 사이클이 없는 N개 노드, (N-1)개 간선을 가진 연결된 그래프그래프는 인접 행렬(O(N^2)), 인접 리스트(O(N+E)) 형태로 구현한다. 깊이 우선 탐색, DFSDFS: Depth-First Search의 약자로 깊이 우선 탐색을 말한다한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  오일러 피 함수 P[N]코딩 테스트에 자주 나오지는 않으나 알고 있어야 보임1부터 N까지 범위에서 N과 서로소인 자연수의 개수원리는 에라토스테네스('배수를 제거한다'는 원리)와 비슷다른 점은 현재 배열의 값이 소수일 때, 그 배수를 제거하기 위해 배열의 끝까지 P[i] = P[i] - (P[i] / K) 연산을 수행한다는 것(K는 현재 선택된 수, i는 K의 배수)이 과정은 N에서 해당 소인수 K의 배수를 제거하고 남은 수의 개수를 반영한다실제 구현할 때는 N까지를 배열로 구현하지 않아도 되는데, 1부터 N까지의 서로소 개수를 result 변수로 생각하는 것이다. 그래서 처음에 N을 넣고 K를 2부터 시작해 N..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  분할 정복(divide and conquer) 방식: 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘가장 작은 데이터 집합(크기 1)으로 나눈 후 2개의 그룹을 합치면서 정렬2개의 그룹을 합칠 때는 투 포인터를 이용하여 둘 중 더 작은 수를 결과 배열에 먼저 저장그런 다음 포인터를 1씩 증가시키는데, 어느 한 포인터가 배열의 끝에 먼저 도달하면 나머지 배열의 값들도 옮겨 붙임   시간 복잡도는 평균 O(nlogN)- 크게 보면 row 하나 당 n번의 데이터 접근- 병합 과정에서 logN번만큼 정렬버블 정렬(swap)과 연관지은 핵심 아이디어- 버블 정렬에서는 swap이 몇 번 일어날까- 첫째 줄에서 5..

API(Application Programming Interface)운영체제와 응용프로그램 사이의 통신에 사용되는 언어나 메시지 형식중간 전달자로서(like 점원) 양쪽의 서버를 연결open API개발자라면 누구나 사용할 수 있도록 공개된 API [위키백과]다양한 서비스와 데이터를 좀 더 쉽게 이용할 수 있도록 공개한 개발자를 위한 인터페이스 [서울 열린데이터광장]API를 제공하는 기업은 자신의 서비스를 널리 알려 인지도를 높이고, 반대로 API를 이용하는 기업은 더 좋은 서비스를 쉽게 사용할 수 있다HTTP APIHTTP를 사용해서 서로 정해둔 스펙으로 데이터를 주고받으며 통신하는 것 - 넓은 의미로 사용 [인프런 김영한님 QnA - https://www.inflearn.com/community/que..

책 [파이썬으로 쉽게 풀어쓴 자료구조; 최영규, 천인국 지음]을 참고하여 작성하였습니다.  QuickSort; 퀵 정렬평균적으로 매우 빠른 수행 속도병합 정렬과 같이 분할-정복법 사용하지만 병합 정렬과는 다르게 균등 분할할 필요 없다리스트 안의 한 요소를 피벗(pivot), 즉 기준점으로 삼고 이 값을 기준으로 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 옮긴다(오름차순일 경우)그런 다음 순환 호출하여 부분 리스트들을 정렬한다불안정정렬, 별도의 메모리 공간 필요하지 않는다cf. 안정성: 입력 데이터에 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것- 시간 복잡도최선의 경우: 리스트 분할이 가운데에서 이루어져 k번(log_2 n)의 분할 * 평균 n번의..