본문 바로가기

CS Study/자료구조

 (6)
[자료구조] 메모리 구조 1. 코딩 실행 파일 동작 방식 1) 개발을 할 때 C, C++, Java 등의 언어들을 이용하여 코딩을 하고 실행파일로 만든다.(ex. .exe 파일 등 ) 2) 이러한 실행파일을 사용자는 클릭을 하는 등의 방법으로 실행한다. 3) 메모리에 로드되면서 코드에서 작성한 동작에 따라 메모리에 데이터들을 쓰고 읽게되는데 이는 운영체제가 해준다. 운영체제가 프로그램의 정보들을 읽고 메인 메모리에 공간을 할당해주고, 프로그램의 코드(변수, 함수 등)을 메모리에 읽고 쓰면서 동작을 하게 된다. 2. 메모리 구조 낮은 주소를 갖는 순서대로 나열하였다. [TEXT] 코드를 실행하기 위해 저장되어있는 영역이다. 흔히 코드 영역이라고 하는데 프로그램을 실행시키기 위해 구성되는 것들이 저장되는 영역이다. 명령문들이 저장된..
[자료구조] DFS & BFS 0. DFS, DFS 학습 전 알아야 할 것 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식 파이썬에서도 2차원 리스트로 구현한다. 연결이 되어 있지 않은 경우에는 논리적으로 정답이 될 수 없는 큰 값 중 999999999 등의 값으로 초기화해서 사용한다. INF = 999999999 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0,7,5], [7,0,INF], [5,INF,0] ] 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식, 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 인접 리스트는 연결 리스트를 사용하면 되는데, 연결 리스트의 경우 파이썬은 기본 자료형인 리스트 자료형이 append 등 메소드를 제공하기 때문에 단순히 2차원 리스..
[자료구조] 큐, 스택 자료 구조: 데이터를 표현하고 관리하고 처리하기 위한 구조이다. 그 중 스택과 큐는 자료구조의 기초 개념 ! 스택과 큐에서의 핵심 함수는 삽입(Push), 삭제(pop)이며 오버 플로와 언더 플로를 주의해야한다. 오버 플로: 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 찬 상태에서 삽입 연산 수행 언더 플로: 데이터가 들어 있지 않은 상태에서 삭제 연산 수행 1. 스택 first in first out 이다. 박스를 쌓았다가 내리는 상황을 생각하면된다. 파이썬에서는 스택을 이용할 때 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop()을 이용하면 된다. stack = [] stack.append(5) stack.append(4) stack.append(3) sta..
힙 정렬 힙정렬이란 ? 리스트나 배열을 먼저 최소힙이나 최대힙으로 바꾸고 원소들을 순서대로 정렬하는 방법이다. 최소힙은 최소값을 구할 때, 최대힙은 최대값을 구할 때 사용한다. 최대힙이란? 완전 이진 트리이면서, 부모노드는 자식 노드보다 크다. 삽입) 새 노드에 삽입이 되고 나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복한다. 부모 노드보다 값이 클 경우, 서로 교환하면서 위로 올라가는 과정을 반복 삭제) 힙의 루트에서 삭제한다. 그러면 루트가 비어있는 상태가 되고, 가장 마지막 노드를 루트 노드로 올린다. 이후 새로 올린 노드가 제자리를 찾아갈 수 있도록 연산을 반복한다. *완전 이진 트리 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다. 2. 최소힙이란? 완전 이진 트리이면서, 각 노드의 키 값이..
기본 정렬 알고리즘 정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬하여 출력하는 알고리즘이다. 많은 종류의 알고리즘이 있고, 시간 복잡도와 공간 복잡도가 다 다르다. 대표적으로 많이 사용하는 몇가지만 우선적으로 학습할 예정이다. 1. 선택 정렬 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다. progress 1) 주어진 배열 중 최소값을 찾는다. 2) 그 최소값을 가장 앞에 위치한 값과 바꾼다. 3) 가장 앞에 위치한 값 뺀 나머지 배열에서 동일한 동작을 반복한다. 8 7 2 5 4 ➡️ 최소값 2와 가장 앞에 위치한 8을 바꾼다. 2 7 8 5 4 ➡️ 2는 자리가 고정된 상태이다. 이는 제외하고 동일한 과정을 반복한다. 최소값 4와 가장..
DFS vs BFS 그래프를 탐색하는 방법에는 DFS, BFS가 있다. DFS는 Depth-First Search 즉 깊이 우선 탐색을 말하고, BFS는 Breadth-First Search 너비 우선 탐색을 말한다. (그래프란 node와 node를 잇는 edge로 이루어진 자료구조를 말한다.) 그럼 DFS와 DFS의 차이점을 알아보자. ✅ DFS의 개념 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 먼저 다 탐색하는 방식을 말한다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. BFS보다 간단하지만 느리다. ✅ BFS의 개념 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다. 루트 노드에서 시작해서 인접한 노드를 먼저 탐색을 하는 방식이다. 시작 정점으로부터 가까운 정점을 먼저..

티스토리툴바