스택 - 후위 표기법2

카테고리 Python, DataStructure, Stack

후위 표기법 2

소괄호를 포함한 후위 표기법 바꾸기

소괄호()는 *보다 우선순위가 높다.

후위 표기법은 우선순위가 높은 것을 먼저 출력하므로, 열린 소괄호가 나오면 스택에 넣는다.

이후 닫힌 소괄호가 나오면 스택에 열린 소괄호 나올 때 까지 pop하여 연산자를 결과값에 추가한다.

  • 괄호는 변수에 추가하면 안되므로 스택에서 pop하여 제거한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    result = ''
    s = []

    for x in str:
        if x.isnumeric():
            result += x
        elif x == '(':
            s.append(x)
        elif x == ')':
            while s[-1] != "(":
                result += s.pop()
            s.pop()
        elif x in priority:
            if s and s[-1] != '(' and priority[s[-1]] < priority[x]:
                result += s.pop()
            s.append(x)

    while s:
        result += s.pop()

    return result
  • 코딩테스트를 본다고 생각하고 리스트를 활용하여 위 문제를 풀어보았다.
  • isnumeric() 함수는 문자열이 숫자인지 판단하는 메서드이다.
  • stack의 top을 의미하는 s[-1] 슬라이싱을 활용하였다.
  • 빈 리스트는 논리값이 False라는 점을 활용하여 while 반복문을 실행했다.

후위 표기법 계산하기

  1. 문자열을 순회하면서 해당 문자가 숫자면 정수형으로 변환하여 스택에 push
  2. 연산자이면 스택에서 두 수를 pop하여 계산
  3. 스택은 후입선출이므로, 처음 pop한 수를 n2, 두번째 pop한 수를 n1으로 두고 (n1 연산자 n2)로 계산한다.
  4. 계산결과를 스택에 push
  5. 스택에 마지막에 저장된 값이 결과값이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def eval_postfix(expression):
    s = []
    for exp in expression:
        if exp.isnumeric():
            s.append(int(exp))
        elif exp != " ":
            n2 = s.pop()
            n1 = s.pop()
            if exp == '+':
                res = n1 + n2
            elif exp == '-':
                res = n1 - n2
            elif exp == '*':
                res = n1 * n2
            else:
                res = n1 / n2
            s.append(res)
    return s[0]

댓글 공유

스택 - 후위 표기법

카테고리 Python, DataStructure, Stack

후위표기법 1

연산자를 피연산자 뒤에 쓰는 연산기법

예를 들어, 3+5x2 를 중위 표기법이라 하고,

352x+를 후위 표기법이라고 한다.

계산 방법

3+5x2를 후위 표기법으로 적으면, 352x+이다.

352x+를 계산하기 위해서 다음과정을 따른다.

  1. 피연산자(숫자)는 스택에 담는다. [3,5,2]
  2. 연산자를 만나면, 스택에서 피연산자 2개를 꺼내 계산한다.
  3. 결과값을 다시 스택에 넣는다. [3,10]
  4. 다음 연산자는 +이므로 3+10을 계산한다.
  • 컴퓨터 입장에서는 후위 표기법이 연산의 우선순위가 명확하다는 장점이 있다.

중위 표기법을 후위 표기법으로 변환

3+5x2를 후위 표기법으로 바꾸는 과정을 알아보자.

  1. 피연산자 3을 결과값에 추가
    • 연산자 스택에 push
  3. 피연산자 5 결과값에 추가
  4. x 연산자와 스택의 마지막 값인 + 우선순위 비교
  5. x 연산자가 우선순위 높으므로 스택에 push
  6. 피연산자 2 결과값에 추가
  7. 스택이 빌 때까지 pop하여 결과값에 추가

3x5+2를 후위 표기법으로 바꿔보자.

  1. 피연산자 3을 결과값에 추가
  2. x 연산자 스택에 push
  3. 피연산자 5 결과값에 추가
    • 연산자와 스택의 마지막 값인 x 우선순위 비교
  5. 스택의 마지막 값인 x 연산자가 높으니 pop하여 결과값에 추가
    • 연산자는 스택에 push
  7. 피연산자 2을 결과값에 추가
  8. 스택이 빌 때까지 pop하여 결과값에 추가

문제 풀이

Stack 클래스를 이용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    s = Stack()

    result = ''
    for x in str:
        if x not in priority.keys():
            result += x
        else:
            if s.top == None:
                s.push(x)
            else:
                if priority[s.top.data] < priority[x]:
                    s_pop = s.pop()
                    result += s_pop
                s.push(x)

    while not s.is_empty():
        s_pop = s.pop()
        result += s_pop

    return result

아래는 if 문으 조금 줄여보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    s = Stack()

    result = ''
    for x in str:
        if x not in priority.keys():
            result += x
        else:
            if not s.is_empty() and priority[s.top.data] < priority[x]:
                s_pop = s.pop()
                result += s_pop
            s.push(x)

    while not s.is_empty():
        s_pop = s.pop()
        result += s_pop

    return result

댓글 공유

스택 - 연습문제

카테고리 Python, DataStructure, Stack

문제 1. 괄호 짝 검사

괄호의 짝이 바르면 True, 바르지 않으면 False를 반환하는 함수를 작성하라.

예를 들어 ((a*(b+c))-d) / e는 괄호의 짝이 올바르지만, (((a*(b+c))-d) / e 는 괄호의 짝이 맞지 않는다.

괄호는 소괄호(())만 사용한다.

풀이

1
2
3
4
5
6
7
8
9
10
def solution(str):
    stack = Stack()

    for x in str:
        if x == '(':
            stack.push(x)
        elif x == ')':
            if not stack.pop():
                return False
    return stack.is_empty()
  • 여는 괄호가 나오면 stack에 Push
  • 닫는 괄호가 나오면 stack을 pop
    • 이 때, stack에서 아무것도 pop되지 않는다면, 제대로 된 괄호가 구성되지 않은 것이다.

문제 2. 소,중,대괄호 짝 검사

소괄호, 중괄호, 대괄호 짝이 맞는지 검사

1
2
3
"[{a * (b + c)} - d] / e" # True

"[{a * (b + c)] - d] / e" # False

풀이

1
2
3
4
5
6
7
8
9
10
11
12
def solution(str):
    brackets = {")":"(", "}":"{", "]":"["}
    stack = Stack()

    for x in str:
        if x in brackets.values():
            stack.push(x)
        elif x in brackets:
            popped = stack.pop()
            if not popped or brackets[x] != popped:
                return False
    return stack.is_empty()
  • brackets을 관리하는 딕셔너리를 만든다.
  • 여는 괄호면 stack에 push한다.
  • 닫는 괄호면, 해당 닫는 괄호와 짝을 이루는 여는 괄호가 stack.pop()한 요소와 같은지 비교
    • 만약 다르거나 pop한 요소가 None이라면 False

문제 3. 짝지어 제거하기

같은 알파벳 2개가 붙어 있는 짝을 찾습니다.

그 다음 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙입니다.

이 과정을 반복하여 문자열이 모두 제거된다면 1을 반환하고 그렇지 않으면 0을 반환합니다.

풀이

1
2
3
4
5
6
7
8
9
def solution(str):
    stack = []

    for ch in str:
        if stack and ch == stack[-1]:
            stack.pop()
        else:
            stack.append(ch)
    return 0 if stack else 1
  • stack 클래스 대신 배열을 사용했다.
  • stack의 push(): append()
  • stack의 pop(): pop()
  • stack의 peek(): [-1]로 인덱싱
  • is_empty(): 빈 리스트 논리값은 False 임을 이용

댓글 공유

스택 - 파이썬으로 스택(stack) 구현하기

카테고리 Python, DataStructure, Stack

파이썬으로 Stack(스택) 구현하기

stack

  • 스택은 서류나 책 위에 다른 서류나 책을 쌓아 올리는 형태이다.
  • 자료를 꺼낼 때에는 맨 위부터 꺼내야한다. 후입선출(Last In First Out, LIFO)

stack2

  • 90도 눕혀서 보게 되면 연결리스트와 비슷한 구조를 지닌다.
  • 연결리스트의 head를 스택에서는 top이라고 부른다.

Stack 메서드

  • push(data): data를 넣는 작업, 연결리스트의 appendLeft와 같다.
  • pop(): 자료를 꺼내는 작업, 연결리스트의 popLeft와 같다.
  • peek(): 마지막에 넣은 자료 확인, pop과 비슷하지만 값을 제거하지는 않는다.
  • is_empty(): 빈 스택인지 확인

Stack 클래스 만들기

  • 단일 연결리스트를 활용하여 Stack 클래스에서는 top 속성을 넣고 length 속성은 뺀다.
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
class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

  def push(self,data):
    node = Node(data)
    if self.top == None:
      self.top = node
    else:
      node.next = self.top
      self.top = node

  def pop(self):
    if self.top == None:
      return None

    node = self.top
    self.top = node.next
    return node.data

  def peek(self):
    if self.top == None:
      return None
    return self.top.data

  def is_empty(self):
    return self.top == None

댓글 공유

==, is는 같지 않다. (Python)

카테고리 Python

==, is는 같지 않다.

  • == 는 값을 비교한다.
  • is 는 메모리 주소를 비교한다.

파이썬에서 변수는 객체에 붙은 이름표라고 생각하자.

1
2
3
4
5
a = [1,2,3]
b = [1,2,3]

a == b # True
a is b # False

예외 케이스

1. 정수형값

1
2
3
4
5
a = 10
b = 10

a == b # True
a is b # True
  • Python은 메모리 최적화를 위해 -5 ~ 256 까지는 캐싱하는 싱글턴 오브젝트이다.

각 자료형 is, == 비교

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
#정수
print('==integer==')
a = 10
b = 10
print(a == b) #True
print(a is b) #True

#부동소수
print('==float==')
a = 3.15982489254324342
b = 3.15982489254324342

print(a == b) #True
print(a is b) #True

#복소수
print('==complex==')
a = 1+4j
b = 1+4j

print(a == b) #True
print(a is b) #True

#문자열
print('==string==')
a = 'test'
b = 'test'

print(a == b) #True
print(a is b) #True


#부울
print('==bool==')

a = True
b = True

print(a == b) #True
print(a is b) #True

#리스트
print('==list==')
a = []
b = []

print(a == b) #True
print(a is b) #False

a = [1,2]
b = [1,2]

print(a == b) #True
print(a is b) #False


#튜플
print('==tuple==')
a = ()
b = ()

print(a == b) #True
print(a is b) #True

a = (1,2)
b = (1,2)

print(a == b) #True
print(a is b) #True

#딕셔너리
print('==dictionary==')
a = {}
b = {}

print(a == b) #True
print(a is b) #False

a = {'a':1, 'b':2}
b = {'a':1, 'b':2}

print(a == b) #True
print(a is b) #False

결론

주로 ==을 사용하지 메모리를 직접 비교하는 is는 자주 사용되지 않고 헷갈리므로 ==를 사용하자.

댓글 공유

연결리스트 - 주어진 리스트가 순환이 있는지 확인하는 문제

카테고리 Python, DataStructure, LinkedList

1. 연결리스트 길이로 풀기

1
2
3
4
5
6
def isCircleLinkedlist(Linked_list):
    node = Linked_list.head
    for _ in range(len(Linked_list)):
        node = node.next

    return True if node else False
  • 연결리스트의 길이를 구하여 연결리스트의 마지막 노드의 next 를 확인한다.
    • 만약 마지막 노드의 next가 있다면, 순환연결리스트
    • 그렇지 않으면 연결리스트이다.

2. 집합을 사용하여 풀기

1
2
3
4
5
6
7
8
9
10
def isCircleLinkedlist(Linked_list):
	s = set()
	node = Linked_list.head
	while node:
		if node in s:
			return True

		s.add(node)
		node = node.next
	return False
  • 노드의 값이 중복되지 않는다면, 지나간 노드를 집합(set)에 저장한다.
  • 노드가 이동할 때 마다 집합에 있는 노드인지 확인한다.
    • 집합에 지나간 노드가 있으면 True
    • 그렇지 않으면 False

3. 중복된 값이 있을 경우, 두개의 포인트를 사용하여 풀기

1
2
3
4
5
6
7
8
9
def isCircleLinkedlist(Linked_list):
    node1 = node2 = Linked_list.head
    while node1 and node1.next:
        node1 = node1.next.next
        node2 = node2.next

        if node1 == node2:
            return True
    return False
  • node1은 두칸씩 이동한다.
  • node2는 한칸씩 이동한다.
  • 만약 순환이 있다면 언젠가는 두 노드가 만난다.
  • 순환이 없다면 node1 또는 node1.next가 None에 도달한다.

댓글 공유

연결리스트 - 클래스 구현

카테고리 Python, DataStructure, LinkedList

연결리스트 클래스

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#파일 이름: sllist.py

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Linked_list:
    def __init__(self):
        self.head = None
        self.length = 0

    def __len__(self):
        return self.length

    def __str__(self):
        if self.head is None:
            return "Empty List"
        node = self.head
        string = ""
        while node.next:
            string += str(node.data) + " → "
            node = node.next
        return string + str(node.data)

    def __contains__(self, data):
        node = self.head
        while node:
            if node.data == data:
                return True
            node = node.next
        return False

    def appendleft(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            node.next = self.head
            self.head = node
        self.length += 1

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            prev = self.head
            while prev.next:
                prev = prev.next
            prev.next = node
        self.length += 1

    def popleft(self):
        if self.head is None:
            return None
        node = self.head
        self.head = self.head.next
        self.length -= 1
        return node.data

    def pop(self):
        if self.head is None:
            return None
        node = self.head
        if self.head.next is None:
            self.head = None
        else:
            while node.next is not None:
                prev = node
                node = node.next
            prev.next = None
        self.length -= 1
        return node.data

    def insert(self, i, data):
        if i <= 0:
            self.appendleft(data)
        elif i >= self.length:
            self.append(data)
        else:
            prev = self.head
            for _ in range(i - 1):
                prev = prev.next
            node = Node(data)
            node.next = prev.next
            prev.next = node
            self.length += 1

    def remove(self, data):
        if self.head.data == data:
            self.popleft()
            return True
        prev = self.head
        while prev.next:
            if prev.next.data == data:
                prev.next = prev.next.next
                self.length -= 1
                return True
            prev = prev.next
        return False

    def reverse(self):
        if self.length <= 1:
            return
        ahead = self.head.next
        prev = self.head
        prev.next = None
        while ahead:
            self.head = ahead
            ahead = ahead.next
            self.head.next = prev
            prev = self.head

연결리스트 테스트

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
def get_data(msg):
    print(msg, end = ">>> ")
    data = input()
    return int(data) if data.isdigit() else data

my_list = LinkedList()

while True:
    menu = """
-----------------------
실행할 명령어를 선택하세요.

[0] 연결 리스트의 상태 출력
[1] 처음에 노드 추가   [2] 끝에 노드 추가      [3] 노드 검색
[4] 첫 노드 꺼내기     [5] 마지막 노드 꺼내기  [6] 특정 위치에 노드 삽입
[7] 노드 삭제         [8] 연결 리스트 뒤집기
[9] 끝내기

"""
    print(menu, end=" >>> ")
    command = int(input())
    print("-----------------------")
    print()

    if command == 0:
        print(my_list)
    elif command == 1:
        my_list.appendLeft(get_data("추가할 값(정수, 문자)을 입력하세요."))
    elif command == 2:
        my_list.append(get_data("추가할 값(정수, 문자)을 입력하세요."))
    elif command == 3:
        data = get_data("검색할 값을 입력하세요.")
        if data in my_list:
            print(f"{data}(이)가 리스트에 있습니다.")
        else:
            print(f"{data}(이)가 리스트에 없습니다.")
    elif command == 4:
        print(my_list.popLeft())
    elif command == 5:
        print(my_list.pop())
    elif command == 6:
        index = get_data("값을 추가할 인덱스를 입력하세요.")
        my_list.insert(index, get_data("추가할 값을 입력하세요."))
    elif command == 7:
        data = get_data("삭제할 값을 입력하세요.")
        if my_list.remove(data):
            print(f"{data}(을)를 정상적으로 삭제했습니다.")
        else:
            print(f"{data}(이)가 리스트에 없습니다.")
    elif command == 8:
        my_list.reverse()
        print("리스트를 뒤집었습니다.")
    elif command == 9:
        break

댓글 공유

연결리스트 - 개념 및 설명

카테고리 Python, DataStructure, LinkedList

연결리스트

노드로 감싸진 요소를 인접한 메모리 위치가 아닌 독립적으로 저장한다.

각 노드는 next 또는 next,prev 라는 포인터로 서로 연결된 선형적인 자료구조

  • 참조: O(n)
  • 탐색: O(n)
  • 삽입 / 삭제: O(1)

연결리스트에 접근하기 위해서는 첫 노드를 가리키는 head가 반드시 있어야 한다.

노드란, data와 next로 이루어진 구조체이다. 값을 담고 있는 data, 노드와 노드를 잇는 next라는 포인터로 이루어져 있다.

싱글연결리스트

스크린샷 2023-07-15 오후 12.17.18.png

next 포인터만 존재하여 한 방향으로만 데이터가 연결된다.

원형연결리스트

마지막 노드와 첫번째 노드가 연결되어 원을 형성한다.

싱글연결리스트 또는 이중연결리스트로 이루어진 2가지 타입의 원형 리스트가 있다.

싱글연결리스트로 구성된 원형연결리스트

스크린샷 2023-07-15 오후 12.18.41.png

이중연결리스트로 구성된 원형연결리스트

스크린샷 2023-07-15 오후 12.18.50.png

랜덤접근과 순차적 접근

스크린샷 2023-07-15 오후 12.21.39.png

랜덤접근(random access, 직접접근)

  • 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때, 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
  • vector, array는 랜덤 접근 가능하여 n번째 요소에 접근 시 O(1)

순차적 접근(squential access)

  • 데이터를 저장된 순서대로 검색하며 순차적으로 접근
  • 연결리스트, 스택, 큐는 순차적 접근만 가능하여 n번째 요소 접근 시 O(n)

📌 배열과 연결리스트 비교

배열

  • 배열은 indexing으로 원소에 접근은 쉽다. O(1)
  • 하지만 맨 끝을 제외한 위치에서 원소를 추가 / 삭제 하는 것은 연속한 메모리 공간을 확보하고 원소를 이동시켜야하므로 시간이 오래 걸린다. O(n)

연결리스트

  • 연결리스트는 이전 노드들을 순차적으로 접근해야 하므로 접근은 오래 걸린다. O(n)
  • 하지만 삽입 / 삭제는 노드를 생성하고 next, prev 포인터로 이전, 다음 노드만 연결해주면 되므로 시간 복잡도가 적다. O(1)
  • 자료의 양이 정해져 있지 않아서 추가 및 삭제하는 일이 많은 경우 연결리스트가 적합하다.

댓글 공유

메모리와 포인터

카테고리 Python, DataStructure

1. 메모리와 주소

1
2
// 정수는 4byte
int i;

C++에서 변수를 만들면 변수에 메모리 주소를 할당(예약)한다.

이 때, 변수 i의 메모리 주소는 변수가 사용하는 메모리 주소 첫번째를 가리킨다.

  • &(ampersand,앰퍼샌드) 연산자로 메모리 주소를 얻을 수 있다.

2. 포인터

  • 자바, 파이썬, 자바스크립트는 개발자가 직접 변수에 메모리를 할당하거나 해제할 수 없고 GC를 통해 이를 수행한다.
  • C, C++ 하위레벨 언어는 GC가 없는 대신, 개발자가 직접 필요한 메모리를 예약 및 해제할 수 있다.

포인터란, 변수의 메모리 주소를 담는 타입이다.

  • 메모리 동적할당
  • 데이터 복사하지 않고 매개변수로 사용
  • 클래스 및 구조체 연결

ex) 연결리스트의 노드

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int i;
string s = "kundol";
int main(){
	i = 0;
	int * a = & i;
	cout << a << '\n';
	string * b = &s;
	cout << b << '\n';
	return 0;
}
  • & i : 변수의 메모리 주소
  • “타입 * 형태” 로 포인터를 정의한다.

포인터의 크기

  • OS가 32bit라면 4byte, 64bit라면 8byte로 고정
  • 어떤 타입(string,int, char 등) 상관없이 무조건 위 수치대로 고정
  • 포인터는 메모리 주소를 담는 것이지 변수 자체를 담는 것이 아니다.
    • 집 주소(포인터)의 크기와 집(메모리)의 크기는 상관이 없다!

ex) 1byte 짜리 char 타입의 변수의 포인터 크기는 1byte가 아니다.

3. 역참조연산자

  • (에스터리스크) 기호를 포인터와 사용하여 역참조로 해당 메모리 주소의 할당된 값을 참조할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
	using namespace std;
	int main(){
	  string a = "abcda";
	  string * b = &a;
	  cout << b << "\n";
	  cout << *b << "\n";
	  return 0;
	/*
	0x6ffdf0
	abcda
	*/
}
  1. a 라는 변수(메모리)에 ‘abcda’ 라는 string 값이 할당
  2. string * b 로 포인터를 정의하여 a 변수의 메모리를 할당
  3. *b 로 포인터를 역참조하여 포인터의 메모리 주소에 할당된 값을 출력

4. array to pointer decay

배열을 변수에 할당하여 해당 변수(주소값)을 T * 라는 포인터에 할당하게 되면, T[N] 이라는 배열의 크기 정보 N이 없어지고 첫번째 요소의 주소가 바인딩되는 현상

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
	using namespace std;
	  int a[3] = {1, 2, 3};
	  int main(){
	  int * c = a;
	  cout << c << "\n";
	  cout << &a[0] << "\n";
	  cout << c + 1 << "\n";
	  cout << &a[1] << "\n";
	  return 0;
}
  1. vector(동적배열)은 안되고 array(정적배열)만 가능
  2. int * c 포인터에 a array를 할당
    1. array to pointer decay 현상 발생
  3. c 를 출력하면 array의 첫번째 요소의 메모리 주소가 출력 (c == &a[0])
  4. 포인터 c에 1을 더하면 array의 두번째 요소를 의미한다.

댓글 공유

배열 - 정적배열과 동적배열

카테고리 Python, DataStructure, Array

정적배열 - Array

  • 연속된 메모리 공간에 위치한 같은 타입의 요소들의 모음
  • 한번 정해진 크기는 변경불가
    • 가득찬 공간에 원소 추가하려면 더 큰 배열 생성 후 기존 배열의 원소를 복사한 후 새 원소 추가
  • 숫자 인덱스를 기반으로 랜덤 접근이 가능하고 중복을 허용한다.
  • vector와 달리 메서드가 없다.

C++ 선언타입

C스타일

1
2
3
4
int a[10]

// 할당
int b[] = {1,2,3}
  • 배열의 크기를 정하여 선언 가능
  • 크기를 정하지 않고 선언하면서 중괄호 요소들을 할당할 수 있다.

std스타일

1
array<int, 10> a;

동적배열

  • 정적 배열의 특징을 가지면서 가변적인 특징이 더해짐
  • 참조: O(1)
  • 탐색: O(n)
  • 맨끝에서 삽입 / 삭제: O(1)
  • 맨 끝 제외 삽입 / 삭제: O(n)

ex) 파이썬의 리스트

C++ 선언방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<타입> 변수명;

vector<int> b;

// 크기 미리 정하거나 해당 크기의 어떤 값으로 초기화 가능
#include <bits/stdc++.h>
using namespace std;
vector<int> v(5, 100);
int main(){
	for (int a : v) cout << a << " ";
	cout << "\n";
	return 0;
}
/*
100 100 100 100 100
*/

댓글 공유

loco9939

author.bio


author.job