알고리즘 자료구조 공부일지

유니온 파인드 개념상호 배타적 부분 집합(Disjoint Set : 서로소 집합)을 표현할 때 사용여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별 연산•Union (합집합) : 노드 x가 포함된 부분 집합과 노드 y가 포함된 부분집합을 합치는 연산•Find (x): 노드 x가 포함된 부분집합을 찾는 연산  최적화 기법1. Path Compression2. Union by Rank (Union by Height)3. Weighted Rule (Union by Size)  유니온 파인드구현초기화부모 노드를 지정할 parent 배열 선언 (코드로 구현할땐 편하게 p로 선언하겠다)parent를 자기 자신으로 지정하여 초기화n개의 원소가 각각 하나의 부분집합 이룸for(int ..

알고리즘 분석 정확성(correctness): 가능한 입력에 대해서 항상 옳은 답을 출력하는가? 자원(resources): 얼마나 많은 자원을 사용하는가? 자원은 알고리즘 실행 시간과 필요한 메모리의 양이 있다. 이 자원을 측정하기 위해 만든 것이 가상의 컴퓨터 RAM (Random Access Machine) 모델순차적으로 수행되는 보통의 컴퓨터에 기반을 두고 있다. -> 직렬구조로 명령어가 사용된 개수에 따라 달라질 수 있다.사칙연산, 비교, 치환 등 간단한 명령어를 가지고 있는데 이 연산을 모두 단위 시간에 수행할 수 있다고 가정한다. 실제 컴퓨터와 마찬가지로 정수의 고정된 길이(32bit, 4byte)로 표현한다무한한 양의 메모리를 가지며, 단위 시간에 메모리에 접근할 수 있다고 가정한다알고리즘 ..

누적합 개념 정리누적합: 배열에서 앞에서부터 해당 인덱스까지의 원소의 값을 모두 더한 것구간합: i부터 j까지 해당 구간 사이 원소의 합예를 들어 5 4 3 2 1 이라는 값을 가진 5 크기의 배열 arr가 있다고 하자. 1. 첫번째 누적합은 기존의 값이 그대로 내려온다.2. 누적합과 그 다음 값을 더한 값이 두번째 누적합이 된다. 3. 위 과정을 반복해서 누적합 배열을 만든다.만약 1~ 3번째 구간의 합을 구하고 싶다면 5+4+3=12 이므로 즉 인덱스 2번의 누적합 값이다. 2~4번째 구간의 합을 구하고 싶다면 4+3+2=9인데, 이 값은 1~4번째까지 더한 값 14에서 첫번째 값 5를 빼면 구할 수 있다. 정리하자면 i부터 j까지의 구간합은 j번째 누적합 - (i-1)번째 누적합이다.  누적합을 쓰..

투포인터의 개념투포인터: 두개의 포인터를 사용해 문제를 푸는 알고리즘. 1. start와 end (또는 front, back이나 left, right 등 이름은 다양하게 할 수 있다.) 두개의 포인터를 만든다. 반드시 start 여야 한다. 2. 초기 두개의 포인터는 0번 인덱스를 가리키도록 세팅한다. 3. 현재 s에서 e-1까지의 합을 sum이라 하였을때 sum이 구하려는 값(m)보다 크다면 s++4. sum이 m보다 작다면 e++ 5. sum과 m이 같다면 카운트 해준다. 6. s와 e의 위치를 바꿔가면서 모든 경우를 확인한다. 정리하자면 start 시작과 end 끝을 모두 증가시켜가며 부분 배열의 합이 m인 경우를 찾는 알고리즘이다. 예를 들어 배열의 크기 n=7, 구하려는 값 m=5 일때 투포인..

재귀함수의 개념재귀: 자신을 정의 할때 자기 자신을 재참조 하는 것, 원래 자리로 되돌아온다. 재귀함수: 어떤 알고리즘이나 함수가 자기 자신을 호출하여 작업을 수행하는 함수재귀함수의 원리스택(STACK) 자료구조스택은 함수가 호출될때 마다 메모리 공간을 확보한다. 재귀함수가 호출될 때마다 스택의 가장 위에 쌓이며 실행 완료되면 제거된다. 나중에 들어온 것이 가장 위쪽으로 쌓이고 제일 먼저 들어온 것은 가장 마지막에 제거되므로 LIFO(Last In First Out) 구조이다. 현재 스택에서 가장 위에 있는 함수가 다음으로 실행되는 함수이다.   기저조건재귀함수를 탈출하기 위한 조건이다. 어떤 특정 조건(기저조건)이 충족될때 return 하고 함수 호출을 중단하는 것이다. 재귀함수는 자기 자신을 계속해서..

개발자라면 꼭 알고리즘을 공부해야할까?알고리즘? 그게 정확히 뭐 어떤건데? 알고리즘의 개념 정리본격적인 알고리즘 공부를 시작하기 전에 먼저 알고리즘이 정확히 무엇인지에 대해 정리해야 한다. 알고리즘(Algorithm)의 사전적 의미어떤 문제를 해결하기 위한 명령어, 방법, 절차의 집합문제를 가장 합리적으로 해결할 수 있는 방안알고리즘(Algorithm)의 또 다른 의미프로그램에서 올바르게 실행 가능한 명령어들의 유한 집합컴퓨터가 사용자의 데이터를 분석해 가장 최적화된 컨텐츠 제공넓게 생각해보자면 알고리즘은 문제를 해결하기 위한 가장 합리적인 절차와 방안을 나타낸다. 꼭 컴퓨터에만 적용되는 언어가 아닌 일상에서도 내가 이 문제를 해결할 합리적이고 최적화된 방안이 제시되었다면 알고리즘이 될 수 있는 것이다...