프로그래밍/Algorithm 8

tryhello 줄 서는 방법 feat. Algorithm Study

알고리즘 스터디를 진행하면서, 오늘 처럼 놀라운 경험을 한 적 처음인 것 같다. 줄 서는 방법 이라는 문제를 진행하는데, 나는 그냥 라이브러리를 이용해 풀었는데, 스터디원 2분이서 새로운 효율적인 생각? 알고리즘 설계를 하셨다. 문제는 다음과 같다. N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에... 서 있는 상태를 나타냅니다.이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.1번..

프로그래밍/Algorithm 2016.06.12 (2)

무방향 그래프 - DFS/BFS

DFS/BFS는 순회 알고리즘이라고 할 수 있습니多. 주로, 트리, 그래프에서 사용 됩니다. 혹은 특정 문제를 풀기 위한 해법이기도 하죠 ? DFS는 Depth-First-Search로 불리며 한국어로는 깊이 우선 탐색이라고 합니다. 즉, 무조건 깊이 깊이~ 우선 탐색을 하죠. 그리고 BFS는 Breadth-First Search로 불리며, 너비 우선 탐색이라고 합니다. 말 그대로 너비를 우선적으로 탐색하죠. 뭐든 말로는 제일 쉽죠…(개발자는 힘드렁…) 아래 소스는 DFS/BFS 문제에 대한 풀이입니다. https://www.acmicpc.net/problem/1260 물론 이 문제를 풀기 위해선 아래의 코드를 살짝 손 봐야 합니다.

Algorithm Study 1 - 2주차

코딩클럽 알고리즘 2주차 - 탐색, 정렬탐색 수행 능력을 평가하기 위해서는 메모리로부터 자료를 가져오는(fetch) 시간보다 자료들을 비교하는 데 걸리는 시간이 더 많이 소모되므로, 비교횟수( number of comparison )를 탐색 방법의 평가 기준으로 삼는다. 즉, 비교횟수가 적은 알고리즘일수록 좋은 성능을 보여준다고 가정한다.왜????데이터 양이 많아 지면 많을 수록 비교 횟수는 시간 복잡도를 잡아 먹는 원인 중 하나이기 때문에 비교 횟수가 적은 알고리즘이 탐색 및 정렬 알고리즘에 있어서 가장 중요하다. 비교 횟수가 증가 할 수록 시간 또한 증가 된다.탐색탐색이란, 원하는 값을 찾는 행위를 말한다. 컴퓨터 전산학에서는 탐색을 자료 구조에서 보통 값을 찾는 데 사용한다. 물론, 우리가 사용하는..

Algorithm Study 1 - 1주차

Ed외부:활동 티스토리 알고리즘 스터디 - 1일차 4/30(토) 알고리즘 스터디1 자료구조란 무엇일까? A) 일련의 자료를 집합형태로 쌓을 수 있는 구조를 말한다고 생각한다. 실생활에서 장에 그릇을 놓는 다면 찬장, 책을 모아 두면 책장이 되는 것 처럼 ‘틀’이라고 생각 할 수 있다. 그런 의미로 볼 수 있다고 생각한다. 컴퓨터로 치면 데이터 집합인 배열, 리스트 등등도 그러한 경우 결국 어떤 용도로 쓸 것인지가 중요하다. 결국 자료구조의 용도는 무엇을 담을지에 대한 초점이다. 팀원) 사용하기 편하게 & 빠르게 만드는게 자료구조. - 효율성 위주 ( 목적성 위주로 생각해도 될 것 같다.) 자료구조를 왜 사용할까? A) 나는 프로그래머의 편의성인 것 같다. 우선 컴퓨터 프로그래밍에서 자료구조가 생긴 이유는..

에라토스테네스의 체

소수 구하는 알고리즘 중에 고대인이 만든 배수 소거법으로 만든 소수 구하는 알고리즘이다. 자세한 것은 위키 백과를 참조하자. 대충 해본거라 맞는지는 모르겠다. 사실 위키에 있는 Java 알고리즘 구현은 상당히 경이롭다. boolean을 이용한 것인데. 아직 멀었구나 싶더라.. 무단 수정 및 배포는 금지합니다. 모든 내용은 본 블로그 운영자가 정리한 내용입니다. 참조한 정보에 대해서는 출처를 남기고 있습니다. 틀린 내용 / 오류가 포함된 내용은 댓글로 남겨주세요. choiseungho0822@gmail.com 보내주셔도 됩니다. Seungdols Wiki 운영중입니다.

알고리즘 - 정렬

전반적으로 많이 부족한 것 같다. 많이 준비 한 것 같아도 발표와 Slideshare에 공유하는 목적이니 목적이 달라 발표때 있었던 동영상은 제거 하고, 새로 수정 하였습니다. 알고리즘 스터디(정렬) Seungdols from seungdols 무단 수정 및 배포는 금지합니다. 모든 내용은 본 블로그 운영자가 정리한 내용입니다. 참조한 정보에 대해서는 출처를 남기고 있습니다. 틀린 내용 / 오류가 포함된 내용은 댓글로 남겨주세요. choiseungho0822@gmail.com 보내주셔도 됩니다. Seungdols Wiki 운영중입니다.

퀵정렬 (Quick-Sort)

퀵 정렬은 분할통치법에 기초한 정렬 알고리즘이다. quickSort(L) if(L.size() > 1) { k ← position in List (Less , Equals , great) ← partition(L , k) quickSort(Less) quickSort(great) L ← merge(Less, Equals, great) } return 1. 분할 기준원소 pivot을 택하여 list를 세부분으로 나눈다. less - pivot 보다 작은 원소 equals - pivot과 같은 원소 great - pivot 보다 큰 원소 2. 재귀 less와 great를 정렬 3. 세 리스트를 결합한다. partition(L , k) pivot ← L.element less , equal , great ← ..