CS

큐(queue)

큐 스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과 반대로 가정 먼저 넣은 데이를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조를 가진다.예: 놀이공원에서 보통 줄 서는 구조 큐에 데이터를 넣을 떄는 인큐(enqueue), 큐에서 데이터를 꺼낼 때는 디큐(dequeue) 함수를 정의 데이터를 직접 꺼내는 것이 아니라 두개의 포인터(front, rear) 를 사용해서 위치를 나타낸다. 코드 # 고정 길이 큐 구현하기 with 링 버퍼. # 기존의 리스트로 dequeue 구현 시 시간 복잡도가 O(n) 으로 상당히 비효율적이다. # 이를 해결하기 위해 링 버퍼를 사용. from typing import Any class FixedQueue: class Empt..

스택(Stack)

스택 데이터를 임시 저장할 때 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조로 되어있다.데이터를 넣을 때는 push, 데이터를 꺼낼 때는 pop을 사용한다. 파이썬에서는 보통 스택을 구현하지 않고 리스트로 만들고 append 해서 데이터를 넣거나 pop으로 데이터를 꺼낸다.아래의 코드는 스택을 클래스로 구현해본 것이다. 코드 class Stack: class Empty(Exception): """스택이 비어있을 때 pop 또는 peek 를 수행할 때 예외 처리""" print("야") pass class Full(Exception): """스택이 가득일 때 push 를 수행할 때 예외 처리""" pass def __in..

컴파일 언어 vs 인터프리터 언어

📔 정의 인터프리터 원시코드(사용자가 작성한 코드)를 기계어로 변환하는 과정 없이 한줄씩 해석하여 바로 실행하는 언어 대표적인 언어: python, javascript, ruby, ... 컴파일 원시코드를 기계어로 모두 변환시킨 후 변환된 코드를 실행하는 언어 대표적인 언어: C, C++ 📔 차이점 속도 보통 인터프리터 언어가 컴파일 언어보다 실행 속도가 느리다 ( 알고리즘 문제 풀 때 파이썬이 느린걸 알 수 있음) 이 기준은 런타임 기준이다. 인터프리터: 한 줄씩 해석하며 실행시키기 때문에 느림 컴파일: 모두 해석해 놓은 뒤 실행시키기 때문에 빠름 📔 예외 자바 자바는 컴파일언어이면서 인터프리터 언어라고한다 컴파일러가 원시코드를 바이트 코드로 컴파일 한다. 인터프리터가 바이트코드를 특정 OS환경에 맞게..

프로세스와 쓰레드(process, thread)

📔 기본 용어 정리 프로그램: 실행할 수 있는 파일 (카카오톡, 크롬, 롤 같은 것) 프로세스: 실행중인 프로그램 또는 실행하고 있는 상태(위와 같은 프로그램을 실행함) 프로세서: 프로세스가 동작할 수 있도록 하는 하드웨어(CPU) 스레드: 프로세스 내에서 실행되는 작업 단위 📔 프로세스 프로세스는 컴퓨터의 자원(코드, 데이터, 힙, 스택)을 받아 한번에 하나의 일을 처리함 코드: 프로그램의 코드 데이터: 전역변수 힙: 동적으로 할당되는 메모리 스택: 호출된 함수, 매개변수, 지역변수 등 임시적인 자료 하지만 우리는 음악들으면서 코딩하고, 검색도 한다. 실제로 동시에 이루어지는 것도 있고, 동시에 이루어지는것처럼 보이는 것도 있다. 동시성(Concurrency): 프로세서 하나가 여러 작업들을 조금씩 돌..

병합 정렬(merge sort)

📔 병합 정렬(merge sort) 이란 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵정렬과 비슷 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법. 보통 재귀함수 호출을 이용하여 구한다. 퀵정렬과 다른 점이 있다면 퀵정렬의 경우 pivot값에 따라 편향되게 분할 될 수 있는 가능성이 있기 때문에 최악의 경우 O(n^2)의 시간복잡도를 가진다. 그러나 병합정렬의 경우 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간복잡도를 보장한다. 만약 8개의 숫자를 정렬한다고 하자. 8에서 4로 나누고, 4에서 2로 나누고, 2에서 1로 나눈다. 즉 3번 나눴다. 그러므로 나누는 것은 3 = log8 이므로 logn이다. 나..