algorithm

코로나19로 할일 없는 요즘.. 인턴은 인턴인데 할 일이 너~~무 없어서 심심해서 코드잼에 참가해보았다. Code Jam! 구글에서는 알고리즘 대회들이 꽤 많다. Kick Start, Hash Code 등등 다양한 것이 있는데, 아무래도 가장 유명한 coding competition을 뽑자면 이 코드잼 아닐까? 코드잼은 전세계의 사람들이 다함께 참여할 수 있는 알고리즘 대회로, Qualification Round -> Round 1 -> Round 2 -> Round 3 -> World Final 의 순서로 진행된다. 사람들을 떨궈(??)가며 진행하는데, 최종 우승자들에게는 상금도 준다. 상금도 상금이지만, 글로벌한 대회에서 좋은 성적을 거두었다는 것 자체가 매우 영광스러운 일이어서 너도 나도 많이들 참..

트리의 개념 트리는 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 가지고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 이는 반복적으로 정의된다. 트리는 노드(node)들과 노드들을 연결하는 간선(edge)로 구성되어있다. 트리에는 사이클(cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을수도 있고 없을 수도 있다. 각 노드는 어떤 자료형으로도 표현 가능하다. class Node{ public String name; public Node[] children; } 비선형 자료구조로 계층적 관계를 표현한다. ex) 디렉터리구조, 조직도 그래프의 한 종류..

11월 17일 오후 2시부터 5시까지 있었던 Kick Start Round H에 참가했다!!! 사실 코딩테스트 자체가 나는 처음이었어서, 조금 많이 두근댔다!!! 전 세계의 개발자(?!)들과 함께 하는 작은 행사니 뭔가 흥분되기도 했다. kick start에 관해서 전에 소개했던 포스팅은 아래 링크다. 2019/11/12 - [알고리즘 Algorithm ] - 구글의 온라인 알고리즘 대회, Kick Start 구글의 온라인 알고리즘 대회, Kick Start https://codingcompetitions.withgoogle.com/kickstart Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzz..

O(n log n)인 정렬 알고리즘들이 알고리즘은 최선으로나 평균적으로나 O(n log n)의 성능을 나타낸다. 최악의 상황에서도 병합정렬이나 힙정렬은 O( n log n)을 유지하는 반면 순수한 퀵 정렬은 오히려 O(n^2)로 뒤진다. 그래서 실제로는 퀵 정렬을 조금 개량해서 최악의 경우가 발생하지 않도록 코드를 짠다. 병합 정렬 (Merge Sort) 대표적인 분할정복(Divide and Conquer) 알고리즘.분할정복이란 말 그대로 문제를 분할 한 다음, 분할한 문제들 (sub-program)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것을 말한다.마찬가지로 합병 정렬은 원소의 개수가 1 또는 0이 될 때 까지 두 부분으로 쪼개고 그 결과들을 크기를 비교하며 정렬하는 방식으로 병합해나간..

여러가지 정렬 알고리즘들을 배우기 앞서...실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용한다. 예를 들면, 정렬 대상을 특정 크기만큼 만들 때에는 퀵 정렬을 쓰다가 특정크기가 되었을 때에는 작은 규모에서 강점을 보이는 삽입 정렬을 쓴다거나 한다.혹은 특정 횟수 이상 재귀호출이 발생하면 O(NlogN)이 보장되는 힙정렬을 쓴다. O(n²) 인 정렬 알고리즘 계싼 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어나는 알고리즘들이다. 그 종류를 살펴보도록 하자. 버블 정렬 (Bubble Sort) 버블 정렬(Bubble sort)는 인접한 원소들의 대소관계를 비교하여 일정한 대소관계를 만족하지 않을 시 인접한 원소들을 교환하는 방법이다. 첫 번째 원소와 두번째 원소를 비교하여 정렬하고, 2번째와..