IT 발자취.../알고리즘
-
[자료구조] 완전 이진 트리를 배열로 만들 경우 크기 계산IT 발자취.../알고리즘 2019. 8. 3. 15:16
완전 이진 트리를 동적 배열로 생성하려면 전체 크기 (배열사이즈)를 알아야 합니다. N=5 일 때, 트리의 전체 크기 구하기 완전 이진 트리는 자식이 생길때 마다 노드가 2개씩 증가하는 것을 알 수 있습니다. 완전 이진 트리에서 N = 5 라고 하는 말은 리프 노드의 갯수가 위의 그림과 같이 5개가 있다는 것을 알 수 있습니다. 먼저 트리의 전체 크기를 구하려면 트리의 높이(h)를 먼저 구해야 합니다. 완전 이진 트리의 특성상, ( h >= 1) , 2^(h-1) < N
-
[알고리즘] 세그먼트 트리 ( Segment Tree )IT 발자취.../알고리즘 2019. 8. 3. 15:07
요약 : 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조 예제 문제 : https://www.acmicpc.net/problem/2042 ( 구간 합 구하기 ) 예제 문제 코드 : https://gintrie.tistory.com/32 참고 블로그 : https://www.crocus.co.kr/648 예로 1 2 3 4 5라는 배열 arr 이 있다. ( 배열 인덱스가 1부터 시작한다고 가정 ) 2번째 부터 5번째의 구간의 수를 더한다. arr[2] + arr[3] + arr[4] + arr[5]를 구하는 쿼리가 있다. 가장 쉽게 푸는 방법은 모든 경우의 수에서 모든 배열의 수를 다 더해주는 것이다. 지금 당장은 2 + 3 + 4 + 5로 간단히 해결할 수 있지만, arr[3]을 6으로 변경하..
-
[알고리즘] 구간 합 구하기 ( 백준 2042 )IT 발자취.../알고리즘 2019. 8. 3. 15:06
구간 합 구하기 문제 : https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 상세 해설 : https://gintrie.tistory.com/31 import java.io.Buff..
-
[알고리즘] 다익스트라 알고리즘 (최단 경로 알고리즘) - 이론편IT 발자취.../알고리즘 2019. 7. 24. 21:50
다익스트라 알고리즘은 가장 유명한 그래프 알고리즘 중 하나입니다. 그래프에서 정점끼리의 최단 경로를 찾는 경우가 여러 가지가 있습니다. 1. 하나의 정점에서 다른 하나의 정점까지의 최단 거리 ( Single source and Single destination shortest path ) 2. 하나의 정점에서 다른 모든 정점까지의 최단 거리 ( Single source shortest path ) 3. 하나의 목적지로 가는 모든 최단 거리 ( Single destination shortest path ) 4, 모든 최단 거리 ( All pairs shortest path ) 다익스트라 알고리즘은 여기서 2번째인 시작 정점 s에서 다른 정점들까지의 최단 거리를 계산합니다. 다익스트라 알고리즘은 너비 우선 ..
-
[알고리즘] 큐빙IT 발자취.../알고리즘 2018. 12. 12. 20:54
삼성 기출문제큐빙 문제 https://www.acmicpc.net/problem/5373해결 방법문제에서 주어진 조건에 맞게 그림을 잘 그리면서 풀기!!!주의할 점은 큐브가 돌 때 주변의 색만 변하는게 아니고 자기 면도 변한다는 점~1차시도 (/src/Main)3차원 배열을 이용하여 cube[사분면][행][열]머리속에서 3차원을 그려가며 열심히 삽질이건 아냐 .... 3차원 배열을 만드는 순간 알고리즘 시험은 포기@@@2차 시도 (/src/SingleMap)U, D, F, B, L, R 의 6개의 1차원 배열을 만든다.각 면을 보는 시점에 따라 좌측 위부터 우측 아래로 1~9까지의 숫자를 배정한다.cube전개도ooooooooogggwwwbbbyyygggwwwbbbyyygggwwwbbbyyyrrrrrrrr..
-
[TDD] 피보나치수열IT 발자취.../알고리즘 2018. 12. 9. 00:34
안녕하세요.초급 개발자의 TDD 공부기입니다.TDD 공부 할 겸? 알고리즘 공부를 해보기 위해 TDD를 이용한 알고리즘 학습을 주제로 포스팅을 시작해보려합니다. 테스트 주도 개발 보면서 TDD를 맛보고일단 키보드로 두들기면 익혀보기로 했습니다. 환경: java8, junit4github 주소 : https://github.com/gintire/algorithm/tree/master/algorithm 먼저 다음과 같이 Fibonacci 클래스와 FibonacciTest 클래스를 만들어줍니다. Step/src/main/java/Fibonacci.java/src/test/java/FibonacciTest.java 결과 Step1 2. fib함수가 0을 대입했을 경우 0을 반환하는건 확실하므로 먼저 상수 0을 ..