사용언어: 파이썬 2.7






1. 난이도, Lv 1


1) 피보나치 수열

문제: http://codingdojang.com/scode/461

1
2
3
4
5
6
7
8
9
10
11
12
13
input = 10
cnt = 0
a = 0
b = 1
 
for index in range(0, input):
    if index %2 == 0:
        print a
        print b
    cnt = a+b
    a = b
    b = cnt
    pass
cs





2) Multiples of 3 and 5 

문제: http://codingdojang.com/scode/350

1
2
3
4
5
6
7
8
9
10
11
12
13
14
max = 1000
result = 0
 
for index in range(1, max):
    if index % 3 == 0:
        result += index
        print index
    elif index % 5 == 0:
        result += index
        print index
    pass
 
 
print result
cs

1000에서는 233168





3) 구글 입사문제

문제: http://codingdojang.com/scode/393

1
2
3
4
5
6
7
8
9
10
11
12
13
max = 10000
cnt = 0
 
for index in range(1, max):
    tmp = index
    while tmp > 0:
        if tmp % 10 == 8:
            cnt += 1
        tmp /= 10
    pass    #END. while tmp > 0:
pass    #END. for index in range(1, max):
 
print cnt
cs





4) 삽입정렬

문제: http://codingdojang.com/scode/443

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
g_list = [524613]
listLeng = len(g_list)
 
for index in range(1, listLeng):
    tmp = g_list[index]
    leftIdx = index - 1
 
    while ( leftIdx >= 0 and g_list[leftIdx] > tmp):
        g_list[leftIdx + 1] = g_list[leftIdx]
        g_list[leftIdx] = tmp
        print "loop. index=" + str(index) + ", leftIdx=" + str(leftIdx) + ", "  + str(g_list)
        leftIdx -= 1
        # END. while
    pass    # END. for index in range(1, listLeng):
 
print str(g_list)
cs


이미지출처: http://effectiveprogramming.tistory.com/19




2. 난이도, Lv 2


1) 아마존 면접문제

문제: http://codingdojang.com/scode/416

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
g_list = [102030405060708090112131415161718191]
limit = len(g_list) / 2
aList = []
bList = []
print "START. " + str(g_list)
 
for index in range(0, limit):
    aList.append( g_list[index] )
    bList.append( g_list[index + limit] )
    """
    해당 반복문은 아래의 2줄로도 가능하긴 함.
    aList = g_list[0:limit]
    bList = g_list[limit:len(g_list)]
    """
    pass
print "aList =" + str(aList)
print "bList =" + str(bList)
 
g_list = []
for index in range(0, limit):
    g_list.append( aList[index] )
    g_list.append( bList[index] )
    pass
print "FINAL. " + str(g_list)
cs




2) 문자열 압축하기

문제: http://codingdojang.com/scode/465

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
msg = "aaabbcccccca"
resultMsg = ""
msgLeng = len(msg) - 1
cnt = 1
index = 0
 
for index in range(0, msgLeng):
    if ( msg[index] == msg[index + 1] ):
        cnt += 1
        pass
    else:
        resultMsg += ( msg[index] + str(cnt) )
        cnt = 1
        if( index+1 == msgLeng ):
            resultMsg += ( msg[index+1] + str(1) )
            pass
        pass
    pass
 
print resultMsg
cs





3) 구글 전화면접

문제: http://codingdojang.com/scode/414

1
2
3
4
5
6
7
8
9
10
11
12
13
14
g_list = [-113, -22]
leftList = []
rightList = []
 
for index in range ( 0len(g_list) ):
    tmp = g_list[index]
 
    if( tmp < 0 ):
        leftList.append(tmp)
    else:
        rightList.append(tmp)
    pass
 
print leftList + rightList
cs





4) 10진수 변환

문제: http://codingdojang.com/scode/458

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def binaryNum(res, divN, result = ""):
    if( divN < 2 and 16 < divN):
        return
 
    if(res < 1 ):
        print result + "[" + str(divN) + "]"
        return
    else:
        tmp = res % divN
        if tmp > 10:
            result = chr( 65 + (tmp-10) ) + result
            pass
        else:
            result = str(tmp) + result
            pass
        tmpInt = res/ divN
        binaryNum( tmpInt, divN, result )
    pass
 
binaryNum(23316"")  #입력
cs





5) 비슷한 단어 찾아내기

문제: http://codingdojang.com/scode/445

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
def oneEditApart(arg0Str, arg1Str):
    cntF = 0
    block = 0
    tmp = len(arg0Str) - len(arg1Str)
 
    if( tmp > 0 ):
        for index in range (0len(arg0Str)-1):
            if( arg0Str[index:index+1] == arg1Str[0:1] ):
                block = index
                break
            pass
        arg1Str = ('_' * block) + arg1Str
        pass    #END. if( tmp > 0 ):
    elif( tmp < 0 ):
        for index in range (0len(arg1Str)-1):
            if( arg1Str[index:index+1] == arg0Str[0:1] ):
                block = index
                break
            pass
        arg0Str = ('_' * block) + arg0Str
        pass    #END. elif( tmp < 0 ):
 
    for index in range (0len(arg0Str) ):
        if ( arg0Str[index]==arg1Str[index] ):
            cntF += 1/( float(len(arg0Str)) )
            pass
        pass
 
    if( cntF > 0.5 ):
        print "TRUE\t" + arg0Str + "/" + arg1Str
    else:
        print "FALSE\t" + arg0Str + "/" + arg1Str
    pass    #END. def oneEditApart(arg0Str, arg1Str):
 
oneEditApart("cat""dog")
oneEditApart("cat""cats")
oneEditApart("cat""cut")
oneEditApart("cat""cast")
oneEditApart("cat""at")
oneEditApart("cat""acts")
cs





3. 난이도, Lv 3


1) Spiral Array

문제: http://codingdojang.com/scode/266

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
def spiralArray(rowLeng, colLeng):
    spiralMetrix = [[0 for col in range(colLeng)] for row in range(rowLeng)]
 
    direction = 1
    mx = 0
    index = 0
    while (index < colLeng * rowLeng):
        idx = 0
        if(direction == 1):   #RIGHT
            for idx in range (mx, colLeng - mx):
                spiralMetrix[mx][idx] = index
                index += 1
                pass
            direction = direction << 1
            pass
        elif(direction == 2):   #DOWN
            for idx in range (mx+1, rowLeng - mx):
                spiralMetrix[idx][colLeng - (mx+1)] = index
                index += 1
                pass
            direction = direction << 1
            pass
        elif(direction == 4):   #LEFT
            for idx in range (colLeng - (mx+2) , mx-1, -1):
                spiralMetrix[rowLeng - (mx+1)][idx] = index
                index += 1
                pass
            direction = direction << 1
            pass
        elif(direction == 8):   #UP
            for idx in range (rowLeng - (mx+2), mx, -1):
                spiralMetrix[idx][mx] = index
                index += 1
                pass
            mx += 1
            direction = direction >> 3
            pass
 
        #   REULT
        print "\n\tloop. " + str(index) + ", " + str(direction)
        for i in spiralMetrix:
            print i
            pass
    pass
 
spiralArray(66);
cs






2) 그 시간 사무실에 몇 명이 있었나?(아마존 면접)

문제: http://codingdojang.com/scode/418

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
log = """09:12:23 11:14:35
09:04:00 12:00:00
11:06:00 12:00:45
10:34:01 13:23:40
09:04:00 11:00:00
10:34:31 11:20:10"""
 
def howMany(logStr, time):
    personCheck = log.splitlines()
    personNum = len(personCheck)
    cnt = 0
    hour = int(time[0:2])
    minute = int(time[3:5])
    second = int(time[6:8])
 
    for index in range(0, personNum):
        tmp = personCheck[index].split(' ')
        inTime = tmp[0]
        outTime = tmp[1]
 
        if( hour == int(inTime[0:2]) ):
            if( minute > int(inTime[3:5]) ):
                cnt += 1
                pass
            elif( minute == int(inTime[3:5]) and second >= int(inTime[6:8]) ):
                cnt += 1
                pass
            pass
        elifint(inTime[0:2]) < hour < int(outTime[0:2]) ):
            cnt += 1
            pass
        elif( hour == int(outTime[0:2]) ):
            if( minute < int(outTime[3:5]) ):
                cnt += 1
                pass
            elif( minute == int(outTime[3:5]) and second <= int(outTime[6:8]) ):
                cnt += 1
                pass
            pass
        pass    #END. for index in range(0, personNum):
 
    print time + ", " + str(cnt) + "person(s)."
    pass    #END. def howMany(logStr, time):
 
howMany(log, "09:30:00")
howMany(log, "11:05:20")
cs




3) Ugly Numbers

문제: 

처음에 시도한 아래의 코드는 사실 계산상 문제는 없지만 저조한 퍼포먼스.

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
import time;
 
def uglyNumber(nthNum):
    _t = time.time();
    resultFt = 0.0;
    listCnt = 1;
    idxFt = 1.0;
 
    while (listCnt < nthNum):
        if( degradedNum(idxFt) ):
            print "[" + str(listCnt+1+ "] " + str(idxFt);
            listCnt += 1;
            resultFt = idxFt;
            pass
        idxFt += 1.0;
        pass
 
    print str(resultFt) + ',   %.02f seconds' % (time.time() - _t);
    pass    # END. def uglyNumber(nthNum):
 
def degradedNum(input):
    tmp = input;
    if(tmp%2 == 0):
        while (tmp%2 == 0):
            tmp /= 2;
            if (tmp == 1):
                return True;
            pass
        pass
    if(tmp%3 == 0):
        while (tmp%3 == 0):
            tmp /= 3;
            if (tmp == 1):
                return True;
            pass
        pass
    if(tmp%5 == 0):
        while (tmp%5 == 0):
            tmp /= 5;
            if (tmp == 1):
                return True;
            pass
        pass
    return False;
    pass    # END. def degradedNum(isEven, input):
 
uglyNumber(1550)
cs






4) 숫자에 콤마 삽입

문제: http://codingdojang.com/scode/398

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
def setComma(arg):
    mark = "";
    if (arg< 0):
        mark = "-";
        arg *= -1;
        pass
 
    #    소수점 이하 분리.
    pointFt = float(arg - int(arg));
    tmpPtStr = str(pointFt);
    arg -= pointFt;
    arg = int(arg);
    
    tmpStr = str(arg);
    msgStr = "";
    idx = 0;    #콤마 표기용 idx값
    for index in range (len(tmpStr)-1-1-1):
        if(idx % 3 == 0 and idx > 1):
            msgStr = "," + msgStr;
            pass
        idx += 1;
        msgStr = tmpStr[index] + msgStr;
        pass
 
    print mark + msgStr + tmpPtStr[1:len(tmpPtStr)];
    pass
 
setComma(1000);
setComma(20000000);
setComma(-3245.24);
cs






5) 앞뒤가 같은 수

문제: http://codingdojang.com/scode/401


1안. 재귀함수 사용시

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
56
57
58
59
60
61
62
63
import time;
 
def getPairNum(arg):
    cntInt = 0;
    result = -1;
    _t = time.time();
 
    if(arg == 0):
        print "pairNum[" + str(arg) + "]=1";
        return;
 
    while (cntInt < arg):
        result += 1;
        tmpStr = str(result);
        strLeng = len(tmpStr);
        if( result < 10 ):
            cntInt += 1;
            pass
        elif( result < 100 ):
            if( tmpStr[0== tmpStr[1] ):
                cntInt += 1;
            pass
        elif( result < 1000 ):
            if(tmpStr[0== tmpStr[2]):
                cntInt += 1;
            pass
        elif(tmpStr[0== tmpStr[strLeng-1and tmpStr[1== tmpStr[strLeng-2]):
            if( result < 10000 ):
                cntInt += 1;
            elif( checkPair(tmpStr, 0, strLeng) ):
                cntInt += 1;
        pass;    # while (cntInt < arg):
 
    print "pairNum[" + str(arg) + "]=" + str(result) + ',   %.04f seconds' % (time.time() - _t);
    pass;    # def getPair(arg):
 
def checkPair(msg, token, gap):
    #print str(gap) + ", msg=" + str(msg);
    if(len(msg)%2==0 and gap<1):
        return True;
        pass
    elif(len(msg)%2!=0 and gap<2):
        return True;
        pass
    elif(msg[token] == msg[gap-1]):
        token += 1;
        gap -= 2;
        checkPair(msg, token, gap)
        pass
    else:
        return False;
    pass    # def checkPair(msg, msgLeng):
 
getPairNum(1);
getPairNum(4);
getPairNum(20);
getPairNum(21);
getPairNum(30);
getPairNum(100);
getPairNum(1000);
getPairNum(1001);
getPairNum(30000);
getPairNum(1000000);
cs



2안.

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
56
57
58
59
60
61
import time;
 
def getPairNum(arg):
    cntInt = 0;
    result = -1;
    _t = time.time();
 
    if(arg == 0):
        print "pairNum[" + str(arg) + "]=1";
        return;
 
    while (cntInt < arg):
        result += 1;
        tmpStr = str(result);
        strLeng = len(tmpStr);
        if( result < 10 ):
            cntInt += 1;
            pass
        elif( result < 100 ):
            if( tmpStr[0== tmpStr[1] ):
                cntInt += 1;
            pass
        elif( result < 1000 ):
            if(tmpStr[0== tmpStr[2]):
                cntInt += 1;
            pass
        elif(tmpStr[0== tmpStr[strLeng-1and tmpStr[1== tmpStr[strLeng-2]):
            if( result < 10000 ):
                cntInt += 1;
            elif( checkPair(tmpStr, strLeng) ):
                cntInt += 1;
        pass;    # while (cntInt < arg):
 
    print "pairNum[" + str(arg) + "]=" + str(result) + ',   %.04f seconds' % (time.time() - _t);
    pass;    # def getPair(arg):
 
def checkPair(msg, msgLeng):
    rangeEnd = int(msgLeng/2);
    head = -1;
 
    for head in range(0, rangeEnd):
        rear = msgLeng - 2*head - 1;
        if(rear < 3):
            return True;
            pass;
        elif(msg[head] != msg[rear]):
            return False;
        pass;
 
    pass    # def checkPair(msg, msgLeng):
 
getPairNum(1);
getPairNum(4);
getPairNum(20);
getPairNum(21);
getPairNum(30);
getPairNum(100);
getPairNum(1000);
getPairNum(1001);
getPairNum(30000);
getPairNum(1000000);
cs





6) 넥슨 입사문제, 셀프 넘버

문제: http://codingdojang.com/scode/365


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
def selfNumAcc(start, end):
    resultInt = 0;
    generateList = [];
    tmpToken = [];
 
    for index in range(start, end):
        generateList.append( getGenerator(index) );
        pass;
    #print str(generateList);
 
    for index in range(start, end):
        if( index not in generateList):
            resultInt += index;# print str(index) + ", " + str(resultInt);
            pass
        pass;
    print str(start) + "~" + str(end) + " self num sum = " + str(resultInt);
 
    pass;    # def selfNumAcc(start, end):
 
def getGenerator(arg):
    tmpSum = arg;
    while(arg > 0):
        tmpSum += (arg%10);
        arg //= 10# quotient
        pass;
    return tmpSum;
    pass;
 
selfNumAcc(15000);
cs


답: 1227365







기타. 변경이력


일자

변경이력

2015-03-10

 초안.


'프로그래밍note > 자료구조&알고리즘' 카테고리의 다른 글

코딩도장 문제풀이  (0) 2015.03.10
알고리즘: 기초정리(1)  (0) 2012.08.30
자료구조: 연결리스트&스택(Stack)  (0) 2012.01.09
STL: 리스트&벡터&맵  (0) 2011.05.24


알고리즘: 기초정리(1)

알고리즘: 기초정리(2)






00. 상식 

 1. 알고리즘이란?

① 정의

알고리즘이란 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합이다.

- C로 배우는 알고리즘, 27쪽 - 

② 어떤 알고리즘을 써야 하는가?
- 알고리즘의 종류는 많다. 하지만 만병통치약같은 알고리즘은 없다. 그렇기 때문에 해결하고자 하는 문제에 적합한 알고리즘을 선택해야 한다. 또한 알고리즘의 속도/메모리 소요를 고려해야한다.

- 문제를 해결할수 있는 알고리즘중 단순한 알고리즘을 쓰는것이 좋다. 하지만 속도와 자료처리량에 따라서 타협이 필요하다.




 2. 알고리즘 분석

① 경험적/수학적 분석

- 경험적 분석 : Empirical analysis. 프로그램 언어로 구현해서 실행시간을 비교하는 분석법.

- 수학적 분석 : Mathematical analysis. 수학적 분석만으로 알고리즘의 실행시간을 분석.

② 최악/최선의 경우(시간소요량 기준)

- 최악의 경우란 알고리즘이 실행되는데 걸리는 최대의 시간을 말한다.

 즉, 늦어도 이정도 시간까지는 문제해결이 된다.

- 알고리즘이 실행되는게 걸리는 최소의 시간.

③ 알고리즘 분석의 단계(3단계)

- 입력자료 결정 : 여러종류의 자료를 입력하면 실행시간의 범위가 유추된다. 이 과정에서 평균 수행시간을 구할수도 있다.

- 수행시간 계산 : 알고리즘의 동작을 분해해서 계산.

- 수학적인 분석 : 최악의 경우를 이용해서 수행시간의 상한선등을 결정할수 있다.




 3. 알고리즘의 유형

* N = 입력되는 자료의 수

* 어떤 알고리즘이라도 변형에 따라 수행시간 유형이 달라진다.(=프로그래머 재량에 좌우....)

1

 입력 자료와 무관한 실행시간

 명령들을 1번만 실행하거나 몇번만 실행

log N

 성능이 좋은 검색 알고리즘은 대부분 이 정도 실행시간을 가진다.

N

 자료량에 비례되는 실행시간.

 이 정도가 되어도 쓸만한 실행시간이라고 한다.

N log N

 규모가 큰 문제를 작은단위로 쪼개서 각각을 해결한 후에 통합하는 경우(Top down - Integration???)

 이중루프에서 자료를 처리할때 발생.

 자료량이 많을때는 비권장.

 자료량이 많은 문제에는 부적합

2ⁿ

 처음 개발된 알고리즘에 간혹 나타남.






01. 간단한 알고리즘

 1. 유클리드 알고리즘(Euclid's Algorithm)

-> 최대공약수(Greatest Common Divisor)를 구하는 알고리즘이다.

① 성질

     GCD(u, v) = GCD(u-v, v) [u에 u-v를 저장.]

     GCD(u, v) = GCD(v, u)    [좌, u < 우, v일때 교환.]

     GCD(u, 0) = u                 [u = 0, 2로 돌아간다 / u != 0, v가 최대 공약수]

 최대 공약수의 성질을 이용해서 뺄셈/두 값의 교환을 사용해서 최대 공약수를 구한다.

② 구현 [*.cpp]







③ 나머지 연산(%)을 이용한 개선

     GCD(u, v) = GCD(u%v, v) [u에 u%v를 저장후 새로운 u와 v의 위치를 맞교환]

-> 조금 풀어 보면 기존것은 순차적으로 뺼셈을 여러번 했는데,

그 뺄셈을 묶으면 v의 배수가 되니깐 나머지 연산을 시켜서 0이면 v가 최대공약수가 되는거다.


void Gcd::get_gcd()

{

... ... ...

_u %= _v; // _u = _u % _v;

while( _u )

{

if( (_u < _v) || (_u == 0) ) //기본적인 처리법

{

tmp = _u;

_u = _v;

_v = tmp;

}

_u -= _v;

printf(" = GCD(%d, %d)\n", _u, _v);

}

... ... ...

print(result);

}

④ 루프횟수 비교

-> 나머지 연산값이 0이라서 while문을 돌지 않고 완료되었다.




 2. 소수를 구하기 알고리즘(1)

① 성질

     1과 자기자신만으로 나누어 떨어지는 양의 정수

->소수인지를 판별하는데 적합하다.

② 구현 [*.cpp]







③ 제곱근 sqrt()를 이용한 개선시도

-> 하지만 코드상 간결해진다 하더라도 sqrt()함수는 실수형 데이터라서 이를 캐스팅 시키고 하면 전체수행시간이 더뎌지는 단점이 있다.

-> 하지만 입력값에 의한 속력차가 없다고 한다. (즉, 입력값이 클떄 유용)




 3. 소수를 구하기 알고리즘(2)

① 성질

     입력된 N의 크기만큼 배열을 생성한다.

     for(int k; k < N; k++)

          arr[k] != 0이면 i++로 재실행

          for(j= i+i; j <= N; j+=i)

          arr[j] = 1;

     for(int k; k < N; k++)


->특정 숫자보다 작은 소수를 구하는데 유용

② 구현 [*.cpp]












02. 주요 개념들

 1. 최적화 기법

① 문제에 맞는 좋은 알고리즘을 선택한다.

② 함수를 사용하면 함수호출등으로 속도가 느려지거나 오버헤드가 발생할수도 있으나, 적절히 사용하면 컴파일후 실행파일의 크기가 작아진다.

③ 실수형 연산 사용을 줄여라.

④ 반복문내를 최대한 간결하게 하라.

⑤ 재귀호출 형태는 가급적 피하자.




 2. 데이터 추상화

-> 구조체처럼 공통된 정보를 가진 정보집합을 대표명을 가진 묶음으로 만든것이다.




 3. 포인터

① 포인터와 변수

int n;

int *myPointer;

myPointer = &n;   //-> 특정변수의 주소값을 저장하는 변수

포인터의 포인터

->연결된 링크참조

③ void 포인터

-> 주소만 저장하는 포인터로 사용하는데 약간 주의해야 한다.

-> 포인터가 가르키는곳의 내용물을 읽는 역참조 사용불가.

-> 데이터형이 없으므로 연산처리불가.


void *v_pt;

int a, b;

a = *(int*)v_pt;

b = *((int*)v_pt + 1);

④ 포인터와 구조체

struct box

{

int width;

int height;

}

struct box b1, *b2;

b2 = &b1;

... ... ...

b1.width = 100;

b1.height = 200;

... ... ...

b2->width = 2000;

b2->height = 12;

함수 포인터

-> 세부사항은 연결된 링크 참조




 4. OOP

캡슐화(=은닉)

다형성

상속

'프로그래밍note > 자료구조&알고리즘' 카테고리의 다른 글

코딩도장 문제풀이  (0) 2015.03.10
알고리즘: 기초정리(1)  (0) 2012.08.30
자료구조: 연결리스트&스택(Stack)  (0) 2012.01.09
STL: 리스트&벡터&맵  (0) 2011.05.24



1. 스택


 ①스택 선언

 ②push(), 삽입

 ③pop(), 삭제

Algorithm size():
    return t +1 //인덱스가 0부터 시작
Algorithm isEmpty():
    return (t < 0)

Algorithm top():
    if isEmpty() then
      throw a StackEmptyException
    return S[t]

Algorithm push(o):

    if size() = N then
      throw a StackFullException
    t ← t + 1
    S[t] ← o

Algorithm pop():
    if isEmpty() then
      throw a StackEmptyException
    e ← S[t]
    S[t] ← null
    t ← t-1
    return e


1) 구현

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <conio.h>
 
using namespace std;
 
//#define MAX = 12;
const int MAX = 12;//가급적 const사용
 
//스택
int g_stack[MAX];
int top = -1;
 
void push(int val);
void pop();
void print_stack();
 
void main()
{
    print_stack();
    push(2015);
    push(12);
    push(23);
    push(11);
    print_stack();
    pop();
    pop();
    pop();
    pop();
    pop();
    print_stack();
 
    cout << "PRESS KEY" << endl;
    _getch();
}
 
void push(int val)
{
    if (top + 1 < MAX)
    {
        top++;
        g_stack[top] = val;
    }
    else
    {
        return;
    }
    cout << "idx=" << top << ", top = " << g_stack[top] << endl;
}
 
void pop()
{
    int tmp = g_stack[top];
 
    if (top >= 0)
    {
        g_stack[top] = 0;
        top--;
    }    
 
    cout << "pop: " << tmp << ", new top = " << g_stack[top] << endl;
}
 
void print_stack()
{
    if (top != -1)
    {
        for (int idx = top; idx >= 0; idx--)
        {//스택은 탑->다운이 기본이니깐
            cout << g_stack[idx] << endl;
        }
    }
    else
    {
        cout << "STACK EMPTY\n" << endl;
    }
}
cs


2) 구현, 포인터 및 구조체 사용한 방식

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <conio.h>
using namespace std;
 
//#define MAX= 256;
const int MAX= 256;//가급적 const사용
int pop (struct stack *s_arr);
int push (struct stack *s_arr, int x);
void CreateStack(StackSturct **Stack, int Capacity);
void DestroyStack(StackSturct **Stack);
 
struct stack_arr
{
   int item[MAX_SIZE];
   int top;
}
 
typedef struct Node
{
     int Data; //굳이 int로 한정되진 않음.
}Node;
 
typedef struct Stack
{
     int Capacity;
     int Top;
     Node *Nodes;
}StackSturct;
 
void main()
{
    cout << "PRESS KEY" << endl;
    _getch();}
}
 
int pop (struct stack *s_arr)
{
   int  pop_val;
 
   if(s_arr->top == -1)
   {
      printf("스텍 언더플로우");
      exit();
   }
   pop =  s_arr->item[s_arr->top--];
 
   return (pop_val);
}
 
int push (struct stack *s_arr, int x)
{
   if(s_arr->top ==  MAX_SIZE)
   {
      printf("스텍 오버플로우");
      exit();
   }
   s_arr->item[++s_arr->top];
}
 
void CreateStack(StackSturct **Stack, int Capacity)
{
     (*Stack) = new StackSturct;//(StackSturct *)malloc(sizeof(StackSturct));
 
     //노드*단위용량만큼 메모리.
     (*Stack)->Nodes = new Node;//(Node *)malloc(sizeof(Node) *Capacity);
 
     /* 용량, TOP 초기화 */
     (*Stack)->Capacity = Capacity;
     (*Stack)->Top = 0;
}
 
void DestroyStack(StackSturct **Stack)
{
      //free(Stack->Nodes); //노드해제
    //free(Stack);        //스택해제
    Stack->Nodes = NULL;
    Stack = NULL:
}
cs






2. 연결리스트


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <conio.h>
 
using namespace std;
 
//일반 연결 리스트
typedef struct list_linked
{
    int key;
    struct list_linked *next;//다음 노드 위치 저장.//이 경우 재귀적인 정의.
}node_link;
node_link *head, *tail;//*next값을 변경하기 좋은 포인터 태그.
 
node_link *node_insert1(int num, node_link *new_tail);
int node_del(node_link *target);
node_link *node_find(int key);
 
void main()
{
    head = new node_link;
    tail = new node_link;
 
    head->next = tail;
    tail->next = tail;//꼬리에서 흐름이 끝나게 하는 부분.
 
 
    cout << "PRESS KEY" << endl;
    _getch();
}
 
//================================================================================
//    노드제어 관련.
//================================================================================
node_link *node_insert1(int num, node_link *exist_node)
{//특정 노드 뒤에 삽입
    node_link *node_new = NULL;
    node_new = new node_link;
    node_new->key = num;
    node_new->next = exist_node->next;//exist_node와 exist_node->next 사이에 삽입되므로
    exist_node->next = node_new;
 
    return node_new;
}
 
node_link *node_insert2(int preKey, int nextKey)
{//키값을 기준으로 두 노드사이에 삽입
    //node_find와 node_insert1를 응용
}
 
int node_del(node_link *target)
{//target의 다음 노드를 삭제
    node_link *tmp = NULL;
    int result = 0;
 
    if (target->next == tail)
        result = 0;
    else
    {
        tmp = target->next;
        target->next = target->next->next;
        tmp = NULL;
        result = 1;
    }
 
    return result;
}
 
node_link *node_find(int key)
{
    node_link *tmp = NULL;
    tmp = head->next;
 
    while (tmp->key != key && tmp != tail)
    {
        cout << "tmp=" << tmp << ", tmp->key=" << tmp->key << endl;
        tmp = tmp->next;
    }
 
    return tmp;
}
cs





3. 연결리스트 스택(Linked List Stack)

-> 메모리 동적할당이라 스택을 구현하는데 아주 유용.
-> 스택의 크기가 고정되지 않음. 스택내 데이터의 개수만큼만 메모리를 사용.

 ①스택 선언

 ②push(), 삽입

 ③pop(), 삭제

typedef struct tagNode

{
   //int Data; //굳이 int로 한정되진 않음.
   char *Data; //linkde_value의 주소값.
   struct tagNode *NextNode;
}NodeStruct;
typedef struct tagStack
{
   int Capacity;
   int Top;
   NodeStruct *Nodes;
}StackSturct;
typedef struct tagLinkedListStack
{
   Node *List;
   Node *Top;
}LLS_Struct;

void LSS_Push(LLS_Struct **Stack,
                      Node *NewNode)
{
   if (Stack->List == NULL)
   {
      Stack->List = NewNode;
   } //공백스택이면, 새노드가 리스트에 곧장 들어감.
   else
   {
      Node *OldTop = Stack->List;;
      while (OldTop->NextNode != NULL)
      {
         OldTop = OldTop->NextNode;
      }
      OldTop->NextNode = NewNode;
   }
   Stack->Top = NewNode;
}

void LLS_Pop(LLS_Struct **Stack)
{
   Node *TopNode = Stack->Top;

   if (Stack->List == Stack->Top)
   {
      Stack->List = NULL;
      Stack->Top = NULL;
   }
   else
   {
      Node *CurrentTop = Stack->List;
      while (CurrentTop != NULL
                &&
                CurrentTop->NextNode != Stack->Top)
      {
         CurrentTop = CurrentTop->NextNode;
      }
      Stack->Top = CurrentTop;
      CurrentTop->NextNode = NULL;
   }
   return TopNode;
}


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
typedef struct tagNode
{
   //int Data; //굳이 int로 한정되진 않음.
   char *Data; //포인터형(char *)은 단순히 값의 복사가 아니라, linkde_value의 주소값.
   struct tagNode *NextNode;
}NodeStruct;
typedef struct tagStack
{
   int Capacity;
   int Top;
   NodeStruct *Nodes;
}StackSturct;
typedef struct tagLinkedListStack
{
   Node *List;
   Node *Top;
}LLS_Struct;
 
void LSS_CreateStack(LLS_Struct **Stack) //스택생성
{
   (*Stack) = (LLS_Struct*)malloc(sizeof(LLS_Struct)); //자유저장소 할당.
   (*Stack)->List = NULL;
   (*Stack)->Top = NULL;
}
 
void LSS_DestroyStack(LLS_Struct **Stack) //노드소멸
{
   while!LLS_isEmpty(Stack) )
   {
      Node *Popped = LLS_Pop(Stack);
      LLs_DestroyNode(Popped);
   }
   free(Stack);
}
 
void LSS_CreateNode(char *NewData) //노드생성
{
   Node *NewNode = (Node*)malloc(sizeof(Node));
   NewNode->Data = (char*)malloc(strlen(NewData) + 1);//입력받은 문자열 크기로 자유 저장소
   strcpy(NewNode->Data, NewData);//문자열 복사
   NewDode->NextNode = NULL:
 
   return NewNode;//노드주소 반환
}
 
void LSS_DestroyNode(Node * _Node) //노드소멸
{
   free(_Node->Data);
   free(_Node);
}
 
void LSS_Push(LLS_Struct **Stack, Node *NewNode)//스택삽입
{
   if (Stack->List == NULL)
   {
      Stack->List = NewNode;
   } //텅빈 스택이면, 새노드가 리스트에 곧장 들어감.
   else
   {
      Node *OldTop = Stack->List;;
      while (OldTop->NextNode != NULL)
      {
         OldTop = OldTop->NextNode;
      }
      OldTop->NextNode = NewNode;
   }
   Stack->Top = NewNode;
}
 
void LLS_Pop(LLS_Struct **Stack)
{
   Node *TopNode = Stack->Top;
 
   if (Stack->List == Stack->Top)
   {
      Stack->List = NULL;
      Stack->Top = NULL;
   }
   else
   {
      Node *CurrentTop = Stack->List;
      while (CurrentTop != NULL && CurrentTop->NextNode != Stack->Top)
      {
         CurrentTop = CurrentTop->NextNode;
      }
      Stack->Top = CurrentTop;
      CurrentTop->NextNode = NULL;
   }
   return TopNode;
}
cs





기타. 변경이력


일자

변경이력

2012-01-09

 초안.

2015-12-23

 가독성 개선 및 기본형 예시코드 2종 추가







'프로그래밍note > 자료구조&알고리즘' 카테고리의 다른 글

코딩도장 문제풀이  (0) 2015.03.10
알고리즘: 기초정리(1)  (0) 2012.08.30
자료구조: 연결리스트&스택(Stack)  (0) 2012.01.09
STL: 리스트&벡터&맵  (0) 2011.05.24






1. 리스트
-> 순차적 검색으로 최대 N(리스트의 용량)정도의 실행시간?
-> 저장될 데이터가 많아질수록 비효율.

2. 벡터
-> 중간에 데이터 삽입, 삭제가 없을 경우 용이.
-> 배열과 달리, 크기가 가변적이라 저장할 데이터가 적거나 많은것에 사용가능.
-> 데이터의 랜덤접근 가능.

3. 맵
-> 빠른검색가능. [logN급]
-> 삽입, 삭제시 느리다.



참고.
[면접질문] Vector와 Map의 차이에 대해서 설명하여라.

'프로그래밍note > 자료구조&알고리즘' 카테고리의 다른 글

코딩도장 문제풀이  (0) 2015.03.10
알고리즘: 기초정리(1)  (0) 2012.08.30
자료구조: 연결리스트&스택(Stack)  (0) 2012.01.09
STL: 리스트&벡터&맵  (0) 2011.05.24

+ Recent posts