한 걸음씩 기록하며

Linked List 1) Linked List (연결 리스트) 배열이 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조라면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다. 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 배열은 데이터만 가지고 있는 반면, 링크드 리스트는 데이터 + 다음 데이터의 주소 값을 가진다. 배열은 미리 셋팅하고 데이터를 넣으므로, 데이터를 추가할 수 없다 혹은 어렵다. (원래는) 링크드 리스트는 포인터가 있기 때문에 추가하기 쉽다. 장점 데이터 추가나 삭제가 쉽게 가능하고, 빠르다. ..

ArrayList(배열) *Array와 ArrayList는 거의 비슷하나 약간의 차이가 있다. 가장 큰 차이점은 길이를 조정할 수 있는가이다. Array는 고정 길이지만, ArrayList는 가변 길이이다. 가장 기본적인 자료구조로서, 같은 자료형의 변수들을 모아서데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 컴퓨터의 실제 메모리 공간을 연속적으로 사용하기에, 컴퓨터가 연산을 하기 쉬운 구조를 가지고 있음. (논리적 저장 순서와 물리적 저장 순서가 일치한다.) 장점 검색 속도가 그 어떤 자료구조보다 빠르다 인덱스를 통한 데이터 접근은 Random Access 방식 시간 복잡도 O(1) 캐시 히트의 가능성이 높다. (데이터가 군집되어 있기 때문) 단점 한번 고정적으로 선언된 배열..

1. Data Structure(자료구조)란? 자료(Data)란 현실 세계로부터 수집한 사실이나 개념의 값 또는 이들의 집합을 의미 가공되지 않은 데이터를 특정한 용도로 사용하기 위하여 처리/가공한 형태의 데이터를 정보(information)이라 한다. 자료구조는 자료의 집합으로서, 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열하여, 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 의미한다. 즉 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 Q. 어떠한 구조로 데이터를 관리해야하는가? 자료구조의 선택 기준을 무엇으로 잡아야하는가? 1) 자료의 처리 시간, 2) 자료의 크기, 3) 자료의 활용 빈도, 4) 자료의 갱신..

⛏ 문제 파악 스택(후입선출)을 구현하는 문제 주어진 괄호가 VPS인지 판별하는 문제 약간의 포인트라면 ())( 와 같이 )가 먼저 닫히는 경우 NO 라고 리턴해야하는 것? 👉🏻 답안 from sys import stdin N = int(stdin.readline()) results = [] for _ in range (N): state = 0 PS = list(stdin.readline().strip()) for check in PS: if check == "(": state += 1 elif check == ")" and state == 0: state += 100 else: state -= 1 if state == 0: results.append("YES") else: results.append(..

⛏ 문제 파악 Deque를 구현하는 문제이면서 동시에, circular Queue를 보여주기 위한? 문제 👉🏻 답안 from sys import stdin from collections import deque N, M = map(int, stdin.readline().split(' ')) nums = list(map(int, stdin.readline().split(' '))) arr = deque([]) count = 0 for i in range(1, N+1): arr.append(i) for num in nums: if num == arr[0]: arr.popleft() elif arr.index(num) < len(arr)/2: while num != arr[0]: arr.append(arr.p..

⛏ 문제 파악 문제 이해가 어려웠던 문제이다. 스택의 후입선출(LIFO, Last-In First-Out)을 생각하면 이해가 괜찮아지는 문제다. 입력은 오름 차순으로 이루어지고, 입력을 받을 때마다 다음의 상황을 고려하면서 풀면 된다. 내가 입력하려는 수가 수열에 넣어야하는 수와 같다면, 스택에 push하고 pop 해준다. 이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop을 해준다. 내가 입력하려는 수가 수열에 넣어야하는 수와 다르다면 스택에 push만 한다. 예시로 주어진 테스트 케이스 1번을 천천히 살펴보면서, 문제를 설명해보겠다. 스택에 push 하면 스택은 [ 1 ] 이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 4와 다르므로 패스 스택에 push하면 스..

⛏ 문제 파악 큐(queue)를 직접 간단하게 구현해보는 문제 큰 어려움은 없지만 제한 시간이 짧다. 👉🏻 답안 import sys from collections import deque K = int(sys.stdin.readline()) queue = deque([]) for _ in range(K): x = sys.stdin.readline().split() if x[0] == 'push': queue.append(x[1]) elif x[0] == 'pop': if len(queue) != 0: print(queue.popleft()) else: print(-1) elif x[0] == 'size': print(len(queue)) elif x[0] == 'empty': if len(queue) =..

⛏ 문제 파악 불쌍한 재민이를 도와주는 문제 특별한 것은 없다. 👉🏻 답안 import sys K = int(sys.stdin.readline()) total = [] for _ in range(K): x = int(sys.stdin.readline()) if x != 0: total.append(x) else: total.pop() print(sum(total))