버블 정렬
버블 정렬은 앞에서 부터 1번째와 두번째 두개를 비교해서, 특정 조건에 맞춰서 자리를 바꿔주는 것이다. 이중 for문을 돌려서, 체크를 하고, 두번째 반복문에서는, 제일 마지막에쌓인 데이터는 다시 처리하지 않는다.(처리해도 무방하긴 하다, 다만 낭비가 심하니까, 해당 작업은 하지않는다.) 특수하게 짜는 경우는 내부 반복분에 boolean flag를 두어서, 한번돌았을때, 정렬을 한번 도 하지 않는 경우 즉 swap 이 일어나지 않는 경우는 그냥 끝낸다. 왜냐면, 낭비를 줄이기 위해서....그렇게 하기 이해서는 flag를 내부 반복문 안으로 넣는다. 1. 이중 반복문 (내부 반복문 도는 횟수 max값 -1 씩 감소) 2. 자리바꿈시 flag true , 아니면 break 3. 두개 바꿔야 하면 collec..
알고리즘 공부 [힙]
힙에 대한 알고리즘 공부를 해보자. 힙은 heap이라고 해서, 다른 의미로 생각할 수 있지만, 쉽게 말하면 단순히 완전 이진 탐색 트리이다. 완전 이진 트리라고 생각하면 된다. 특징으로는 아래와 같다. - 하위의 자식 노드는 무조건 2개가 있다. - 왼쪽이 작거나 오른쪽이 크거나 할 것없이, 단순히 부모가 자식보다 큰게 다이다. - 0의 index는 비워두고 1부터 계산한다. 해당 이유는, 부모는 자식노드 /2 , 오른쪽 은 /2+1 이런식으로 간단하게 구하기 위해서이다. - 최대힙, 최소힙이 존재하여, 데이터를 탐색하는용도 보다 최대값 최소값을 빠르게 찾기 위해서 사용한다. 우선 힙과, 힙에 데이터를 넣는 메소드를 재구현 해보자 데이터를 넣을때, 항상 넣은 데이터와 부모의 데이터를 비교해서, 두개의 s..
[알고리즘 공부] 2. 큐
큐는 배열이나 다른 것과 달리, 일반적인 입력순서가 출력순서에 영향을 주는 자료구조중에 하나이다. FIFO이라고도하고, 줄서기와 같다고도 하고, 무튼 첫번째로 입력된게 첫번째로 출력이 된다. add or offer로 값을 넣고, poll() 로 해당 리스트의 원소를 출력한다. 추가로, 해당 list를 그냥 출력하게 되면, 리스트의 모든 원소들이 출력이 된다. poll()을 하게 되면,해당 원소의 값을 가질수있게 return 이 되지만 해당 원소를 삭제 하고자 하면(순서는 poll과 동일) 아래와 같이 remove를 사용하면 된다. 이런 queue를 내가 별도로 제네릭 타입을 선언해서, add, poll 기능을 하는 것을 만든다고 해보자 아래와 같이 해당을 구현할수 있다. 자, 이제 그러면 예제를 풀어보자
