가자미의 개발이야기

힙 힙을 알기 위해서는 트리에 대한 기본적인 지식이 필요하다. 힙의 특성 어떤 특정 값을 찾아내는 기능은 지원하지 않지만, 값을 삽입하고, 최대값(최소값)을 찾거나 삭제하는데 큰 강점을 가진 자료구조. 만약 최소값을 찾거나 삭제하고 싶으면 힙성질을 반대로 설정하면 된다. 간단한 용어 설명 트리 표현법 표현법 1: level 0 부터 해당 노드 자리에 노드가 있으면 노드이름을 쓰고, 없으면 None이라고 써서 가능한 모든 자리만큼 원소를 갖는 리스트로 표현. 표현법 2: 트리의 수직적 관계를 리스트 속 리스트를 활용해 표현하기. [부모노드, [부모노드의 왼쪽 서브트리], [부모노드의 오른쪽 서브트리]]. 이때 빈 노드나 서브트리는 빈 리스트 []로 표현한다. 표현법 3: 노드 클래스 활용 각 노드를 노드클..

응용 프로그램? 응용 프로그램은 우리가 흔히 사용하는 엑셀이나 크롬같은 소프트웨어를 말한다. (그렇다고 모든 소프트웨어가 응용 프로그램인건 아니다. 우리가 공부하고 있는 운영체제도 소프트웨어 중 하나다.) 즉 응용 프로그램은 소프트웨어 중 운영체제를 제외한 모든 소프트웨어를 의미한다. 운영체제와 응용 프로그램 간의 관계 운영체제는 응용 프로그램을 관리한다. 응용프로그램을 실행시킨다. 응용 프로그램간의 권한을 관리한다.(관리자 권한으로 실행) 응용 프로그램을 사용하는 사용자도 관리한다.(로그인 과정) 응용 프로그램의 잚못된 작동을 저지한다. 응용 프로그램이 잘못 동작해서, 프로그램을 정지시킨다. 모든 파일 삭제를 막는다.(권한/사용자 관리) 한 응용프로그램이 지나친 cpu소모를 막는다. 결국 이 둘의 관계..

운영체제 역할1: 시스템 자원(System Resource) 관리자 operating system 혹은 os라고 부름 시스템 자원 = 컴퓨터 하드웨어 cpu(중앙처리장치), 메모리(dram, ram) IO devices (monitor, mouse, keyboard, network...) 저장매체: SSD, HDD 컴퓨터의 하드웨어는 혼자서 뭘 혼자 하지 못한다. 운영체제가 이를 운영한다. 대표적인 운영체제 windows os, mac os, unix unix는 현대 os의 기술을 최초로 구현한 운영체제. 윈도우즈와 맥 운영체제도 영향을 받았음 unix 계열 os unix 사용법이나 os구조가 유사(리눅스가 대표적.) 운영체제 역할2: 사용자와 컴퓨터간의 커뮤니케이션 지원 운영체제 역할3: 컴퓨터 하드웨..

a. 해시테이블 해시 테이블은 일종의 정보를 저장하는 서랍장. a는 2층에 b는 3층에 c는 1층에 넣어두는 방식... b를 보고 싶으면 어떤 서랍에 넣었는지 알아내서, 3층 서랍에 있는 내용 중에 b와 일치하는 것을 찾는 것. 해시테이블은 삽입, 삭제, 검색 연산을 빨리 처리할 수 있다. 만약 순서대로 정보를 서랍장에 넣었을 경우, 어떤 정보를 찾으려 할 때 일일히 순차적으로 찾아야 된다. 하지만 해시테이블은 그런 식으로 연산하지 않는다. 바로 해시 함수라는 것을 이용하기 때문에 보다 빠른 연산속도를 갖는다. 해시테이블 자료구조에서 가장 핵심은 각 정보들을 어떤 서랍에 넣을지를 결정하는 것!!! 정보를 어떤 서랍장(슬롯)에 넣을지를 결정하는 것이 바로 해시 함수!!!(f()로 표현) 예를 들어, 해시 ..

a. 왜 양방향 연결 리스트가 필요한가? 한방향 연결 리스트는 다음 노드를 연결하는 링크만 존재, 이전 노드를 알려면 head부터 다시 탐색을 해야된다... 이런 불필요한 연산을 줄이고자 이전 노드를 연결하는 링크가 있는 양방향 연결 리스트를 구현하고자 한다. 양방향 연결 리스트의 주요 개념은 다음과 같다. 이전 노드로의 링크(prev)를 포함해 이전 노드로 이동 가능 마지막 노드와 첫 노드가 서로 연결된 원형 리스트를 가정 첫 노드(head)는 항성 dummy 노드가 되어야 함 (dummy 노드는 리스트의 처음을 구분해주는 마커 기능을 하는 특별한 노드다.) b. 노드 클래스 class Node: def __init__(self, key=None): self.key = key self.next = se..

a. 연결리스트 기본 개념 연결리스트는 노드가 링크에 의해 기차처럼 연결된 순차 자료구조. 노드는 실제 값을 가지고 있는 data 정보와 인접 노드로 향하는 link 정보로 구성된 클래스로 구현한다. 다른 값에 접근하려면 링크에 따라 원하는 노드의 데이터에 접근한다. 다만, 배열처럼 index로 접근할 수 없다. 어떤 값을 찾으려면 처음부터 순차적으로 찾아야한다. 배열과 연결리스트의 차이를 그림으로 파악해보자! b. 한방향 연결리스트 노드들이 한 방향으로 연결된 리스트 가장 앞에 있는 노드를 head 노드라고 부르자. 가장 마지막 노드는 다음 노드가 없으므로 마지막 노드의 next 링크는 None이다. b-1. 노드 클래스 구현하기 class Node: def __init__(self, key=None,..

a. 큐 Queue 가장 최근에 저장된 값 다음에 저장. 반환은 가장 먼저 저장된 값부터. FIFO(First in First out)원칙. enqueue 큐의 오른쪽에 삽입(push와 같음) dequeue 가장 왼쪽에 저장된 값을 삭제 후 리턴 front 가장 왼쪽에 저장된 값을 삭제하지 않고 리턴 isEmpty 큐가 비어져있는지 참거짓 len 큐의 요소 갯수 반환 class Queue: def __init__(self): self.items=[] self.front_index=0 #다음 dequeue될 값의 인덱스 def enqueue(self, val): self.items.append(val) def dequeue(self): if len(self.items)==0 or self.front_ind..

a. 스택 Stack 차례대로 삽입하고 최근에 저장된 값을 삭제(FILO) push 스택에 값 추가 pop 가장 나중에 push된 값을 스택에서 제거하고 반환 top 가장 나중에 push된 값을 제거하지 않고 반환 __len__ 스택의 저장된 요소 갯수를 반환 isEmpty 스택에 요소가 존재하는지 참거짓 # stack_queue.py 에 저장 class Stack: def __init__(self): self.items = []# 데이터 저장을 위한 리스트 준비 def push(self, val): self.items.append(val) def pop(self): try:# pop할 아이템이 없으면 return self.items.pop() except IndexError:# indexError 발생..

a. 배열(array) 데이터를 연속적인 메모리 공간에 저장 주소를 통해 매우 빠르게 접근 배열의 시작 주소, 저장된 값의 종류, 인덱스 세가지 정보로 원하는 값의 주소를 계산 가능. 읽기와 쓰기 연산에 O(1)시간이 걸림 고정된 길이를 가지며, 읽기와 쓰기만 지원하는 경우가 많다. b. 리스트 (파이썬) c의 배열에는 실제 데이터가 저장된 형식이지만, python의 리스트에는 데이터가 저장된 주소가 저장된다. 항상 객체의 주소만 저장하기 때문에 셀의 크기를 8바이트(혹은 4바이트)로 고정. 모든 셀의 크기가 같기 때문에 index에 의해 O(1)시간 접근이 가능 읽기/쓰기 외에 여러 연산들 지원 a.append(val) 맨 뒤에 val 삽입 a.pop(i) a[i]값을 지운 후 리턴 pop()은 가장 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12901 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 내 풀이 주어진 월을 고려하여 지난 달의 일 수를 switch문으로 일자에 더한다. 더해진 일자를 요일에 따라 7로 나누어 요일을 반환 class Solution { public String solution(int a, int b) { while(a!=1){ switch(a){ case 2: b+=31; brea..