스택 - 파이썬으로 스택(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
*/

댓글 공유

배열 - 제시된 합을 가진 부분 배열 찾기

카테고리 Python, DataStructure, Array

제시된 합을 가진 부분 배열 찾기

정렬되지 않은 양의 정수로 이루어진 배열 A가 있다. 연속된 원소를 더한 값이 제시된 값 S와 같은 부분 배열을 찾아라. (인덱스 기준은 1이다.)

  • 입력: arr = [1, 2, 3, 7, 5], s = 12, 출력: [2, 4]
    • 인덱스 2부터 4까지의 합: 2 + 3 + 7 = 12
  • 입력: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], s = 15, 출력: [1, 5]

방법

1. 이중 반복문 사용

1
2
3
4
5
6
7
def solution(arr,s):
    for i in range(len(arr)):
        sum = s
        for j in range(i,len(arr)):
            sum -= arr[j]
            if (sum == 0):
                return [i+1,j+1]

2-1. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(arr,s):
    sum = s
    index = 0
    position = 0
    while sum != 0:
        if position == len(arr) - 1:
            return [-1]
        sum -= arr[position]
        if sum < 0:
            index += 1
            position = index
            sum = s
            continue
        position += 1
    return [index+1,position]
  • sum에 s를 할당하여 position 위치의 요소를 하나씩 빼면서 sum 값이 0 보다 작은지 체크
  • 0 보다 작다면 연속되는 부분합이 아니므로 리셋시켜주고 시작 index도 우측으로 이동시킨다.
  • 만약 시작 index가 배열의 끝까지 도달했는데도 sum이 0이 되지 않으면 연속되는 부분합을 만들 수 없다.

2-2. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
def solution(arr,s):
    left,sum = 0,0
    for right in range(len(arr)):
        sum += arr[right]
        while (left < right and sum > s):
            sum -= arr[left]
            left += 1
        if sum == s:
            return [left+1,right+1]
    return [-1]
  • 배열의 첫번째 요소부터 하나씩 sum에 더해준다.
  • sum이 s보다 작거나 같으면 계속 배열의 요소를 더해준다.
  • sum > s를 만족하면, sum에 left 위치의 요소를 빼주면서 sum이 s보다 작거나 같으면 중단
  • 이 때, sum == s를 만족하면 [left+1, right+1]을 반환한다.
  • left == right 일 때, sum == s를 만족하지 않으면 연속되는 부분합이 없다.

댓글 공유

배열 - 0과 1로 구성된 배열 정렬

카테고리 Python, DataStructure, Array

0과 1로 구성된 배열 정렬

0과 1로 이루어진 배열이 있다. 배열 자체를 오름차순으로 정렬하라.

  • 입력: [1, 0, 1, 1, 1, 1, 1, 0, 0, 0], 출력: [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
  • 입력: [1, 1], 출력: [1, 1]

방법

1. sort() 사용

1
2
3
4
5
arr = [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]

def get_increased_arr(arr):
    arr.sort()
    return arr
  • sort() 메서드는 원본 배열을 오름차순으로 변경한다.

2. sorted() 사용

1
2
3
4
5
arr = [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]

def get_increased_arr(arr):
    answer = sorted(arr)
    return answer

3. count() 사용

1
2
3
def get_increased_arr(arr):
    arr[:] = [0] * arr.count(0) + [1] * arr.count(1)
    return arr
  • arr[:]을 사용하여 원본에 영향을 미치지 않고 복사할 수 있다.

4. 포인터 2개 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_increased_arr(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        while arr[left] == 0:
            left += 1
        while arr[right] == 1 and right >= 0:
            right -= 1
        if left < right:
            arr[left], arr[right] = 0, 1
            left, right = left + 1, right + 1
    return arr

댓글 공유

배열 - 회문(Pelindromes) 찾기

카테고리 Python, DataStructure, Array

회문(Palindrome) 찾기

주어진 문자열이 회문이면 True, 아니면 False를 반환하라.

  • 입력: madam, 출력: True
  • 입력: tomato, 출력: False

방법

1. reversed(), join(), 리스트 컴프리헨션 사용

1
2
3
4
def isPelindrome(str):
    reverse_str = "".join(list(reversed([x for x in str])))

    return str == reverse_str

2. 슬라이싱 사용

1
2
3
4
5
6
word = 'racecar'

if word == word[::-1]:
    print(True)
else:
    print(False)
  • 슬라이싱은 [startIndex:endIndex:interval]로 사용하는데, startIndex, endIndex 없이 interval만 사용하여 역순을 표현했다.

3. 포인터 2개 사용

1
2
3
4
5
6
7
8
def is_palindrome(word):
    left,right = 0, len(word) - 1

    while left < right:
        if (word[left] != word[right]):
            return False
        left, right = left + 1, right - 1
    return True

댓글 공유

loco9939

author.bio


author.job