알고리즘
-
[그래프] DFS와 BFS 구현하기 :: 마이구미알고리즘 2017. 1. 19. 22:15
이번 글은 자료구조 중 그래프를 다뤄본다.백준 알고리즘 1260번을 통해 진행하니 참고하길바란다. 그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. G = (V, E) 그림을 보다시피, 정점과 간선이 무엇을 나타내는 지 알 수 있다.정점은 각 출발점 도착점과 같은 점이라고 보면 되고, 간선은 그 정점간 연결된 관계를 뜻한다. 무방향 그래프와 방향 그래프가 있다.말그대로 방향이 있는 그래프는 2->1로만 갈 수 있고, 무방향이라면 2->1, 1->2 가능하다는 것이다.여기서는 무방향 그래프를 기준으로 다뤄볼 것이다. 그래프의 탐색에 있어 DFS, BFS 방식이 있다.깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식을 알아보자.두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 ..
-
선택 정렬이 불안정 정렬인 이유 :: 마이구미알고리즘 2017. 1. 13. 00:07
이번 글은 선택 정렬이 불안정 정렬인 이유에 대해 다뤄본다.그에 앞서 증명을 위해 버블 정렬, 선택 정렬, 삽입 정렬을 언급하겠다. 3가지를 드는 이유는 특별한 건 없다.단지 가장 구현하기 쉽고, 이해하기 쉬운 정렬이기 때문이다.(세가지 모두 시간 복잡도는 O(n^2) 이다.) 버블 정렬 선택 정렬 삽입 정렬세가지 정렬은 어렵지 않기 때문에 위키의 도움을 빌리겠다. 안정 정렬과 불안정 정렬이라는 말을 들어봤을 것이다.안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )불안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 선택 정렬 )위와 같이 무슨 뜻인지만 알고 있는 경우가 많다.왜? 질문을 던지면 선뜻 증명을 못하면 문제가 있다.많은 글..
-
이진 탐색 알고리즘 Binary Search :: 마이구미알고리즘 2016. 12. 11. 23:39
이번 글의 주제는 탐색 알고리즘인 이진 탐색 알고리즘이다. 탐색이 필요할 때 유용하게 쓸 수 있고, 비교적 구현이 쉽다. 글을 읽기 전 https://www.acmicpc.net/problem/2776 백준 알고리즘 2776번 암기왕을 풀어보고 오면 좋다. 일반적으로 기본적인 순차 탐색과 비교하면서 다루겠다. 순차 탐색이란 말 그대로 순차적으로 탐색을 하는 경우다. 누구나 한번쯤은 사용했거나 지금도 사용하고 있는 가장 간단하고 기본적인 방법이다. 아래 소스를 통해 보자. int[] array = {1,4,2,9,10}; int size = array.length; int target = 10; for(int i=0;i 0) { int one = sc.nextInt(); array = new int[one..
-
LIS 최장증가수열 알고리즘 :: 마이구미알고리즘 2016. 12. 10. 11:55
이번 글의 주제는 LIS 알고리즘이다. LIS는 Longest Increasing Subsequence 로써 최장증가부분수열이라는 의미이다.시간복잡도 O(n^2)을 다룰 것이고, O(nlogn)의 경우는 링크를 보자. (관련 글) 백준 알고리즘 11053번 11055번을 가지고 진행할 것이다. 최장증가수열은 무엇인지 백준 알고리즘 사이트 문제만 읽어도 알 수 있다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 위와 같은 경우가 증가 부분 수열이다. 본인은 이번 글에서 이 문제를 가..
-
문자열 검색 KMP 알고리즘 :: 마이구미알고리즘 2016. 10. 28. 19:11
이번 글은 KMP 알고리즘에 대해 다룰 것이다.KMP 알고리즘이란 무엇인가?이름에 대해서는 큰 의미가 없다. 그냥 사람 이름이다. 백준 5525번, 10769번, 1786번을 풀다가 알게 된 알고리즘이다.유용한 알고리즘이기에 한명이라도 더 알리기 위해 글로 다루게 되었다. (복습 목적이지만..^^) 그렇다면 어떤 알고리즘인가? 어떤 경우에 사용하는 알고리즘인가?시작해보자.시작하기에 앞서 목적은 문자열 검색에 사용되는 알고리즘이다. 문자열 검색의 예를 들어보자.문자열 ABCEDFRIEPQJDNVABRIDFNIABC 라는 문자열이 있을 때 ABCEF라는 문자열을 찾아보자.여러분들은 어떻게 하겠는가?가장 순진한 방법을 말해보겠다. ABCEDABCEFQJDNVABRIDFNIABC ABCEFABCEDFRIEPQJ..