그럼에도 불구하고

문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라..

들어가며 이번 글에서는 문제를 해결하는 가장 단순한 방법인 완전탐색 또는 Brute-Force알고리즘에 대해서 알아보도록 하겠습니다. 목차 정의 사용개념(재귀호출) 재귀 호출을 완전탐색에 사용하는 방법 문제 예시 : Boggle Game 시간복잡도 분석 정의 Brute-Force는 직역하면 무식하게 풀기라는 의미입니다. 문제가 주어졌을 때 일어날 수 있는 모든 경우의 수를 계산해서 원하는 출력값을 얻는 것을 의미합니다. 모든 경우의 수를 탐색하므로 완전탐색(Exhaustive Solving)이라고도 불립니다. 이는 컴퓨팅 자원을 극심하게 소모하기 때문에 입력값이 작을 것으로 기대될때만 사용하는 것이 좋습니다. 간단하게 예를 들어보겠습니다. 열 명의 학생을 한 줄로 세우려고 하는데 서로 사이가 안 좋은 학..

출처: http://t1.kakaocdn.net/codefestival/preliminary.pdf 이번에 풀어볼 문제는 다음과 같습니다. 이번 문제를 풀 때 DFS search를 써서 인접한 영역들을 찾아내고 그 크기를 계산하는 것을 시도했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 class Solution { public static int m,n; public static int[][] picture; public static boolean visited[]..

Selection Sort(선택정렬) & Bineary search(이진탐색) 목차 선택정렬 설명 & 코드 이진탐색 설명 & 코드 알고리즘 코딩을위한 팁 Selection Sort(선택정렬) 설명 선택정렬이란?: 선택 정렬은 전체배열에서 가장 작은 것(또는 큰것)들을 하나씩 선택하여 정렬을하는방법입니다. 선택정렬을위한 단계 주어진 리스트 중에 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 자 그럼 단계를 알았으니 이것을 C언어로 프로그래밍해보겠습니다. 프로그램은 배열의 크기와 배열을 입력받아서 이를 선택정렬후 출력하도록합니다. 시작하기전 어떻게 코딩을 할것인지 각주를 통해 구상을 해봅시다. 1. 배열을 입력받아야하..

Transposing Sparse Matrix 1. 희소행렬(Sparse Matrix)이란? 희소행렬은 행렬안의 값들 중에서 0이외의 값이 희소한 행렬을 의미합니다. 따라서 대부분 0이라면 모든 값들을 표현하지 않고 0이아닌 값과 그 위치만 알고 나머지는 0이다 라고 표현을 할 수 있습니다. 그러므로 평소에 그리던 행렬을 이런 방식으로 표현할 수 있습니다.(변환 방식은 생략) 2. 희소행렬의 대칭이동 위에서 봤던 간단하게 표현된 행렬을 통해서 대칭이동을 하겠습니다. 단순한 대칭이동은 그저 row와 col값을 교환해주면 간단합니다. 그러나 정렬을 유지 하고싶다면 어떻게 해야할까요? 단순 교환은 정렬이 유지되지 않습니다. 따라서 새로운 방법을 궁리해야합니다. 3. 대칭이동과 정렬 우선 기존행렬을 A, 바뀐 ..