'전체 글'에 해당되는 글 203건

  1. 2015.06.16 자료구조 - 리스트(List)
  2. 2015.05.09 node.js의 중요한 특징
  3. 2015.05.01 2591_숫자카드
  4. 2015.04.30 2564_경비원
  5. 2015.04.30 조합알고리즘의 최적화

자료구조 시간에 배운 내용. 프로젝트를 하다보면서 개발을 하다보면서 하나하나 어렴풋해진 이러한 자료구조를 주기적으로 볼 수 있게끔 블로그에 정리해두어야 할 필요가 있겠다고 생각했다. 

우선 첫 번째가 리스트(List)이다. 

리스트의 정의는 "도표 또는 목록을 추상화 한 것" 

(추상화 이런 단어가 썩 내키지 않지만, 이미 정의에서 조차 추상화라는 단어는 좋지 않은 것 같다.)

간단히 말하면 "그냥 자료를 나열해 놓은 것"이라고 정리하고 싶다. 


리스트를 표현하는 자체는 크게 배열과 연결 리스트라고 한다. 

리스트를 배열로 표현할 때의 장점과 단점, 연결 리스트로 표현할 때의 장점과 단점을 알아야 할 것같다. 

한 가지 확실한 것은 배열이 좋다, 연결 리스트가 좋다라고 단정 할 수 없다는 것이다.


리스트를 배열로 표현 했을 때

장점 : 

(1) 검색이 쉽고 빠르다. 

단점 : 

(1) 삽입, 삭제가 용이하지 않다. 

(2) 자료의 크기를 가늠할 수 없어 충분히 크게 잡으면 메모리의 낭비를 초래할 수있다.


리스트를 연결리스트로 표현 했을 때

장점 : 

(1) 삽입, 삭제가 용이하다.

(2) 자료를 동적인 메모리 공간에 할당하므로 메모리의 낭비를 줄일 수 있다.

단점 : 

(1) 단 번에 접근하여 검색 할 수 없다. 처음부터 원하는 데이터가 나올 때까지 연결고리를 이용해 찾아들어야 간다.


왜 그런지에 대해서 그림으로 설명 할 필요가 있겠다. 


[배열]

검색이 쉽고 빠르다

우선 배열은 배열의 각 원소가 정해진 크기를 가진다. 

간단하게 말해서 물리적으로 동일한 주소크기만큼을 가지고 있다.

그래서 인덱스를 통해서 단 한방에 접근이 가능하다. => 결국 D 라는 데이터에 접근하기 위해서는 [3]로 바로 접근이 가능하다는 얘기다.

무척이나 빠르다는 말!





삽입삭제가 쉽지 않다.?

다음과 같은 경우에 Z라는 값을 배열로 구성된 리스트에 삽입하기 위해서는 해당 자리에 값을 넣고 

기존의 있던 3~5까지를 한 번 뒤로 밀어야 한다. 

X는 3이라는 인덱스를 갖게 되고 D는 4, E는 5,  F는 6
한 번 삽입하는데 시간과 자원의 낭비라고 생각하지 않는가?








[연결리스트]

검색이 오래 걸린다?

연결리스트는 구조가 그 값을 가지는 데이터와 연결 될 주소값을 가지는 데이터로 구성되는 노드(Node) 형태로 존재한다. 

여기서 한 가지 알고 가야될 꺼는 다음의 데이터로 연결되는 주소들이 일정하지 않고 그 값을 알 수 없다는 것이다.

D를 검색하기 위해서는 A부터 시작해서 B를 지나 C를 지나 D에 도달해야만 된다는 것이다!

이 것은 단번에 접근가능한 배열에 비해 심한 낭비 일 수 있다. 



삽입 삭제가 빠르다?
N이라는 값을 B다음에 삽입하고 싶으면 다음과 같이 하면 된다.

기존에 연결되어있던 B->C의 연결을 끊고 B->N으로 연결하고, N->C로 연결하면 끝이다. 

C라는 값을 삭제하고 싶으면 다음과 같이 하면 된다.

기존에 연결되어 있던 B->C와 C->D를 끊고 B->D로 연결해버리면 된다. C++과 같은 경우에 할당된 C의 값을 가진 노드를 할당해제해주면된다.


너무 간편하다. 배열처럼 원하는 자리에 넣고 원소들의 값을 뒤로 밀거나 앞으로 땡길 필요가 없다.



 

'자료구조' 카테고리의 다른 글

트리(Tree)  (0) 2015.07.01
위상정렬  (0) 2015.07.01
정렬에 관해서  (0) 2015.04.03
트리 순회_동적할당소스코드  (0) 2015.03.31
트리의 순회  (1) 2015.03.25
Posted by slender ankles
,

노드js는 자바스크립트의 발전 이래 범용 자바스크립트인 Common JS 1.0 명세를 따르고 있습니다. 

node.js의 특징이자 강력한 장점에 대해서 차근차근 설명해나가고자 합니다. 

이전에는 백엔드 프로그래밍과 프로트엔드 프로그래밍에서의 언어가 확실히 분리되어 

서버 프로그래밍에는 java, c, php, perl, ruby와 같은 언어들이 사용되었고(물론 지금도 광범위하게 사용되고 있다)

프론트엔드 프로그래밍에는 UI를 구성시키는 html과 css그리고 동적으로 동작하게 하는 javascript가 사용되었다.

프론트엔드를 다루었던 javascript는 프로토타입(prototype : 원형)형 객체지향 프로그램이을 따르고 있었고, 스크립트 언어이었기에 속도가 느려서 백엔드에서 로직을 구동하는 것은 어려운 언어였다. 

하지만 v8에서 기본적인 javascript들이 미리 컴파일되어 작동시키는 구조를 갖게 됨으로써 엄청 속도가 향상되게 되었다. 

이러한 javascript의 발전으로 nodejs라는 백엔드 서버 기술로써 javascript를 사용하는 nodejs가 탄생 할 수 있게 되었다.


** Common JS 란 무엇인가?

nodejs는 Common JS란 스펙을 따르고 있는데 그렇다면 이 Common JS란 무엇인가? 

node.js를 작업하다보면 exports, module, require 등의 클라이언트 자바스크립트에서 사용하지 않는 지시어를 사용하게 되는데 이 것이 Common JS의 스펙에 명세된 지시어이기 때문이다.


** Node.js 이전에 helma, appjet, jaxer 등등 역시 모두 javascript로 서버 사이드를 작업을 할 수 있게 만든 것이었는데 유독 Node.js 만 성공한 이유는 무엇일까?

(1) 자바스크립트에 대한 인식 변화(역시 뛰어난 자들이 자바스크립트 진영에 뛰어든 효과는 엄청나다고 생각한다)

(2) javascript engine의 성능향상(v8엔진은 c++로 만들어져있고 성능이 매우 우수하다)

(3) Blocking I/O를 제거했다!

이렇게 정리 할 수 있겠다. 


nodejs를 두 단어로 표현한다면?

Event Driven !, Non-Blocking IO !


A. 싱글 스레드의 의미에서 설명하자면 

점원이 한명이고 손님이 5명, 그리고 그 다음 손님이 나라면 

내가 업무를 처리 할 수 있는 것은 점원이 5명의 손님의 업무를 처리한 채로 6번째 순서가 된다. 

엄청난 시간 낭비가 아닐 수 없다. 한국 사람들이 그렇듯이 컴퓨터 역시 이렇게 불필요하게 기다리는 것은 정말 싫어한다.


B. 멀티 스레드의 의미에 대해서 설명하자면

점원이 5명이고 손님이 5명, 여섯 번째 손님인 나는 1명만 기다리면 된다.


C. 이벤트 드리븐 방식에 대해서 설명하자면

점원은 한 명 손님은 여러명이다. 하지만 점원이 업무를 처리하는 동안 나는 저기 다른데 가서 일을 처리하고 있으면 된다.

결과적으로 내가 기다리는 시간 0시간이다. 다른 일을 할 수 있게 되었다는 것은 엄청나다. 

이와 같은 예는 이벤트 드리븐 방식과 논 블록킹을 설명하는데 아주 적합한 예라고 할 수 있겠다.

 

출처는 http://blog.secmem.org/491



Posted by slender ankles
,

정말 dp로 문제를 풀어나가는데 어려움을 느낀다.

시험이 끝나고 dp문제를 많이 풀어봐야겠다. dp를 잘 풀어야 문제해결능력이 높다고 할 수 있다는 것을 깨달았다. 


이 문제는 dp에 대한 풀이경험이 많다면 충분히 풀 수 있는 문제였다.

우선 문제에 대해서 정리하자면

1~34까지의 숫자가 적힌 카드가 있다. 

어느 한 숫자들 문제에서 보면 27123을 이 숫자카드를 나열하여 만들 수 있는 경우의 수를 구하는 문제였다. 

처음에는 dp인지도 모르고 백트래킹으로 풀어냈다. 

처음에 2인 카드를 놓는 경우에 그 다음 카드부터 7 또는 27카드를 놓을 수 있는 경우의 수와 함께

분기시켜며 결국 답을 구해냈다. 하지만 시간초과 ㅜㅜ 

이 문제는 찾아보니 dp문제였다. 

1~40자리의 수 이므로 백트레킹으로는 아무리 줄이더라도 정말 어마어마한 숫자가 나온다. 

그래도 1자리와 2자리 조건이 있으므로 충분히 시간 안에 답이 나올 수 있을 것이라 생각했는데 

아니었다. 


그 이후로는 도저히 방법이 생각 안나 막혔는데, 도움을 얻고 풀어냈다 생각의 전환이 필요했다. 

27123을 나열할 때 

2 -> 27 , 1 -> 12 -> 123 이 피보나치 수열의 형태로 경우의 수를 가진다는 것을 알았다. 

0으로 끊키거나, 2자리수가 34가 넘는 수는 피보나치의 형태를 깨뜨리고 다시 시작하게 되었다. 

예전에 풀었던 자리배치 dp문제와 완벽히 비슷한 문제였는데, 풀어내지 못 해서 아쉽다. 

자리배치 문제는 고정석을 경계로 피보나치의 값을 가지는데 이 경우는 10, 20, 30과 34를 넘는 수에서 피보나치가 끊키고

약간의 조건만 걸어주면 되는 문제였다. 

경우의 수 문제에서는 시간 안에 풀 수 없다면 피보나치를 한 번 생각해보자!!


'알고리즘문제풀이' 카테고리의 다른 글

더블릿_worldcup  (0) 2015.08.20
더블릿_rprime  (0) 2015.08.20
2564_경비원  (0) 2015.04.30
2565_전깃줄  (0) 2015.04.29
2505_두번뒤집기  (0) 2015.04.28
Posted by slender ankles
,

이 문제는 내가 심각하게 잘 못 길을 잡아서 고생했던 문제였다. 

이러한 아이디어는 경험을 통해서 얻어내야겠다고 생각했는데, 이번에도 방향을 조금 잘 못 잡은 듯하다. 


문제에 대해서 간단히 정리하면

배열의 경계에 스토어들과 시작해야 하는 특정 위치가 주어진다. 

그러면 특정위치에서 시계방향 또는 반시계방향으로 경계면을 

돌아 그 위치까지의 최단거리를 찾아서 모두 다 더해주는 문제였다. 

딱히 길이에 대한 방법이 떠오르지 않아 재귀로 방향을 통해 들어가서 답을 구했다. 결국은 해냈지만 

여러 사항들을 처리해주느라 조금 힘들었다. 

하지만 적절하지 않은 방법이라도 답을 낼 수는 있게 된거 같다. 


풀고나서 다른 사람들의 풀이법을 보니까 

전체 w * h의 좌표계에서 경계면을 따라 반시계 방향 또는 시계 방향으로만 돌기 때문에 

전체 길이에서 그 해당 상점까지의 길이 또는 전체 거리에서 그 상점까지의 길이를 빼준 두 개의 경우 밖에 없다는 것이다. 


매우 간단한 문제였다 ... 문제를 좀 더 잘 분석해서 해결해 나가야 겠다.


'알고리즘문제풀이' 카테고리의 다른 글

더블릿_rprime  (0) 2015.08.20
2591_숫자카드  (0) 2015.05.01
2565_전깃줄  (0) 2015.04.29
2505_두번뒤집기  (0) 2015.04.28
2580_스도쿠  (0) 2015.04.28
Posted by slender ankles
,

조합알고리즘

nCr 을 구현해야 됐던 적이 있었나?

경험적으로 재귀적으로 수행했을 때도 충분히 답이 나오는 문제만 풀어서 그런지 없었다. 


1010 다리 놓기 라는 문제를 통해 

그냥 재귀탐색과 DP를 통한 메모이제이션 탐색의 엄청난 시간 차이를 경험했다. 


조합알고리즘에 대해서 간단히 설명하자면

n개 중에서 r개를 뽑는 경우의 수를 nCr 이라고 표현하고 

수학에서는 (n - r)! / r!     또는      n! / r! * (n-r)!으로 계산 해주지 않았나?

=> 6C3 => 6 * 5 * 4 / 3 * 2 * 1 이었다.

하지만 수학이 아닌 컴퓨터에서는 

이렇게 팩토리얼 개념을 적용시켜주면 자칫 메모리를 엄청나게 

쓰다가 스택 오버플로우가 날 수 있다.

n이 충분히 커지게 되면 n!은 기하급수적으로 증가하게 된다. 


그래서 식을 다음과 같이 바꾸어주게 된다. 

nCr = (n - r + 1) / r * nCr-1

nC0 = 1(r ==0일때, basecase)


그렇다면 이 것을 cache를 써서 다음과 같이 표현해주면 완벽하다.


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
#include <iostream>
#include <string.h>
using namespace std;
 
int testcasenum;
int n, r;
int cache[31][31];
 
int bino(int n, int r){
    if (r == || r == n){
        return 1;
    }
    if (cache[n][r] != -1
        return cache[n][r];
    
    return cache[n][r] = bino(n - 1, r - 1+ bino(n - 1, r);
}
 
int main(){
    cin >> testcasenum;
    for (int t = 1; t <= testcasenum; t++){
        memset(cache, -1sizeof(cache));
        cin >> r >> n;
        cout << bino(n, r) << endl;        // nCr을 구한다.
    }
    return 0;
}
 
cs




'알고리즘' 카테고리의 다른 글

재귀호출 - Recursive Call  (0) 2015.09.24
빅 오 분석법 O(n)  (0) 2015.07.23
2차원 배열의 경우의 수 구하기  (0) 2015.04.28
증가하는부분수열(Longest Increase Subsequence)  (0) 2015.04.26
퇴각 검색(BackTracking)  (0) 2015.04.22
Posted by slender ankles
,