전체 글
-
[Python 자료구조 #큐3] 우선순위 큐, 미로 찾기Programming 기초/Python 2023. 5. 15. 14:33
* 우선순위 큐(priority queue) 삭제 연산에서 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어지지만, 특별한 언급이 없으면 우선순위 큐는 가장 높은 우선순위의 요소가 먼저 삭제되는 최대 우선순위 큐를 의미한다. 실제로 가장 효율적인 우선순위 큐의 구현 방법은 트리 구조를 사용하는 힙(heap)이다. (여기서는 리스트를 이용해서 구현할 것임.) 단순화를 위해 데이터 자체가 우선순위를 나타낸다고 가정한다. 일반적으로는 (데이터, 우선순위) 형식의 튜플 구조가 바람직하다. from Stack import*# 이전 포스팅에서 만든 stack.py 모듈을 가져왔다. class PriorityQueue :# 우선순위 큐 클래스 생성 def __init__( self )..
-
[Python 자료구조 #큐2] 원형 덱Programming 기초/Python 2023. 5. 11. 04:05
* 덱(데크, deque) 큐가 FIFO의 단 방향으로만 삽입 삭제가 가능한 자료구조라면, 덱은 전단(front)과 후단(rear) 양쪽에서 삽입과 삭제가 가능한 자료구조이다. 원형 큐를 상속하여 원형 덱(CircularDeque) 클래스를 구현한다. 덱 ADT(추상 자료형) CircularQueue는 이전 포스팅 참고. from CircularQueue import *# CircularQueue를 포함한다. class CircularDeque(CircularQueue) : # 원형 큐의 크기는 10으로 설정했었다. # def __init__( self ) : # 여기서는 생성자를 굳이 호출할 필요가 없다. # super().__init__() # 부모의 생성자를 호출하기 위해서는 super().를 붙인..
-
[Python 자료구조 #큐1] 선형 큐, 원형 큐, 너비우선탐색Programming 기초/Python 2023. 5. 10. 23:55
* 큐(queue) 선입선출(First-In First Out: FIFO)의 자료구조이다. 실시간 비디오 스트리밍에서 다운로드 된 데이터가 비디오를 재생하기에 충분하지 않으면 큐에 순서대로 모아두었다가 충분한 양이 되었을 때 비디오를 복원하여 재생하는데 이것을 버퍼링(buffering)이라고 한다. * 선형 큐 삭제 연산(pop)의 시간 복잡도는 O(n)이다. 비효율적이다. 삭제연산을 O(1)로 동작하도록 구현한 것이 원형 큐다. items = [ ]# 선형 큐 # 선형 큐 ADT(추상 자료형) def isEmpty():# 큐가 비어있는지 확인 return len(items) == 0 def enqueue(item):# 항목 x를 큐의 맨 뒤에 추가한다. items.append(item) def dequ..
-
[Python 자료구조 #스택3] 미로 탐색Programming 기초/Python 2023. 5. 10. 02:06
* 깊이 우선 탐색(Depth-First-Search, DFS) * 너비 우선 탐색(Breadth-Firs-Search, BFS) * 미로탐색 알고리즘 from Stack import * def isValidPos(x, y): if x = MAZE_SIZE or y >= MAZE_SIZE: return False else: return map[y][x] == "0" or map[y][x] == "x"# (x,y)는 리스트에서 [y][x]가 된다. def DFS(): stack = Stack() stack.push((0, 1)) print("DFS: ") while not stack.isEmpty(): here = stack.pop() print(here, end="->"..
-
[Python 자료구조 #스택2] 스택을 이용한 중위표기 수식의 후위표기 변환Programming 기초/Python 2023. 5. 6. 14:55
* 후위표기 수식 계산 구현 def evalPostfix(expr): s = Stack() for token in expr: if token in "+-*/": val2 = s.pop() val1 = s.pop() if (token == '+'): s.push(val1 + val2) elif (token == '-'): s.push(val1 - val2) elif (token == '*'): s.push(val1 * val2) elif (token == '/'): s.push(val1 / val2) else: s.push(float(token)) return s.pop() * 연산자(Operator) 우선순위 반환 함수 def precedence(op):# op는 operator의 약자 if op == ..
-
[Python 자료구조 #스택1] 소스 파일에서 괄호 검사Programming 기초/Python 2023. 5. 6. 03:54
1. 스택을 클래스로 구현하고 2. 파일 내에서 괄호를 검사하는 checkBracketsV2() 함수를 정의. 3. 파일을 읽기모드로 열어서 줄 단위로 리스트를 만들고 4. 만들어진 리스트에 checkBracketsV2() 함수를 호출하여 검사한다. 아래 코드블럭에서는 소스파일 대신 txt파일을 불러왔다. class Stack: def __init__(self): self.top = [] def __str__(self): return str(self.top) def isEmpty(self): return len(self.top) == 0 def size(self): return len(self.top) def clear(self): self.top = [] def push(self, item): self..
-
C언어 기초#14 동적 메모리와 연결 리스트Programming 기초/C Language 2023. 5. 3. 19:49
* 동적 할당 메모리 프로그램이 메모리를 할당받는 방법에는 정적과 동적의 2가지 방법이 있다. 정적 메모리 할당(static memory allocation)이란 프로그램이 시작되기 전에 미리 정해진 크기의 메모리를 할당받는 것이다. 이 경우, 메모리의 크기는 프로그램이 시작하기 전에 결정되며 프로그램의 실행 도중에 크기가 변경될 수는 없다.int score_s[100]; //배열을 선언하면 정적으로 메모리 할당받는다.동적 메모리 할당(dynamic memory allocation)이란 프로그램이 실행 도중에 동적으로 메모리를 할당받는 것을 말한다. 필요한 만큼의 메모리를 할당받아 사용하고, 메모리를 반납한다.score = (int *) malloc(100*sizeof(int)); 그렇다면 동적 할당이 ..
-
C언어 기초#13 스트림과 파일 입출력 printf scanf 심화, fopen(), fclose(), 이진 파일 읽고 쓰기, 버퍼링, fseek(), rewind(), ftell(), foef()Programming 기초/C Language 2023. 5. 3. 19:20
* 스트림(stream) 스트림이란 모든 입력과 출력을 바이트(byte)들의 흐름으로 생각하는 것. 장점 : 장치 독립성. 입출력 장치에 상관없이 프로그램을 작성할 수 있다. 특징 : 버퍼(buffer) 사용. cpu의 속도가 입출력 장치보다 훨씬 빠르기 때문에 버퍼에 어느 정도 데이터가 쌓이면 cpu가 한 번에 데이터를 가져간다. 출력도 마찬가지. * 표준 입출력 스트림(standard input/output stream) 프로그램이 시작될 때 자동으로 만들어지고, 프로그램이 종료될 때 자동으로 소멸된다. 이름 스트림 연결 장치 관련 함수 예시 stdin 표준 입력 스트림 키보드 scan() stdout 표준 출력 스트림 모니터의 화면 printf() stderr 표준 오류 스트림 모니터의 화면 fpr..