본문 바로가기

Computer Science

 (45)
<자료구조> 스택과 큐(1) 1. 스택이란 * 스택 - 데이터를 임시 저장할 때 사용하는 자료구조이다. 후입선출 방식의 입출력 순서를 가진다. - 푸시(Push) : 스택에 데이터를 쌓아 넣는 일 - 팝(Pop) : 스택에서 데이터를 꺼내는 일 - 데이터는 겹겹이 쌓이는 방식으로 푸시하면 top에 쌓이고 pop하면 top에서부터 꺼낸다. 2. 스택의 구현 - 스택을 구현하기 위해 크기가 결정된 고정길이 스택을 클래스를 이용하여 만드려면 어떤 요소들이 필요할까. * 스택 구현 - 스택을 구현하기 위해서는 다음과 같은 요소들이 필요하다. - 스택 배열 : 푸시한 데이터를 list형 배열에 저장하도록 하면 첫번째 푸시한 데이터는 list[0]에 저장된다. - 스택포인터 : 스택에 쌓여있는 데이터의 갯수이다. 가장 마지막에 푸시한 데이터는..
<알고리즘> 검색 알고리즘(2) 1. 해시법 이번 장은 검색뿐 아니라 데이터의 추가·삭제도 효율적으로 수행할 수 있는 해시법을 알아보자. * 해시법 - 데이터를 저장할 위치인 인덱스를 새로 구하는 것이다. 이를 통해 원소의 검색과 추가·삭제를 효율적으로 수행한다. 위의 배열을 11로 나눈 나머지를 정리해보자. 위에서 나온 해시값을 인덱스로 새로 배열을 해보자. - 위를 해시테이블이라 하며 새로운 원소 37을 추가하더라도 다른원소의 이동이 없는 것을 알 수 있다. 이는 기존의 배열에서 37을 추가하려면 뒤의 원소들을 모두 한칸씩 옮겨야 했던 것보다 효율적임을 알 수 있다. - 해시함수 : 위와 같이 키를 해시값으로 변환하는 과정 - 버킷(bucket) : 해시테이블에서 만들어진 원소 * 해시충돌 - 위의 예시에서 33을 추가하려면 버킷[..
<알고리즘> 검색 알고리즘 (1) 1. 검색 알고리즘이란 * 검색 : 어떤 조건을 만족하는 데이터를 찾는 행위 - 검색과 키 ex) 전공이 경제학과인 학생을 찾아라. : 위 예시의 조건은 전공이라는 항목이다. 이렇게 조건에서 주목되는 것이 '키'이다. * 배열검색 - 선형검색 : 무작위로 늘어놓은 데이터의 집합에서 검색 수행 - 이진검색 : 일정한 규칙의 데이터 집합에서 빠른 검색 수행 - 해시법 : 추가와 삭제가 자주 일어나는 데이터의 집합에서 빠른 검색을 수행. 체인법과 오픈주소법이 있음. * 검색 알고리즘의 선택 - 단순히 검색만 잘되면 좋다고 생각한다면 계산시간이 짧은 검색 알고리즘을 선택할 수 있다. - but, 검색 뿐 아니라 데이터의 추가·삭제도 수행한다면 검색이외에 작업에 들어가는 비용을 종합적으로 평가해야한다. - 따라서..
<자료구조> 자료구조와 배열 1. 자료구조와 배열 * 배열이란 - 하나의 값이 아닌 묶음 단위의 값을 저장하는 자료구조 - 원소 : 배열에 저장된 객체 한 단위 - 파이썬에서는 주로 리스트와 튜플로 배열을 표현함. * 객체 - 파이썬은 데이터, 함수, 클래스, 모듈 등 전부 객체로 취급하기때문에 변수는 값을 갖는 것이 아니다. - 모든 객체는 메모리를 차지하며 식별번호가 따로 존재한다. - 따라서 변수는 객체를 참조하는 별명이라고 보는 것이 좋다. 예를 들어 10의 고유번호를 19991010 이라고 하자. 이 때 x = 10 이라고 선언하고 x의 식별번호를 확인하면 19991010이 나타난다. ※ 값을 비교할 때 연산자로 == 을 사용하지만 두 객체의 값과 식별번호를 함께 비교할 경우에는 is 를 사용한다. * 리스트와 튜플 - 리..
<알고리즘> 알고리즘 기초 1. 알고리즘이란 * 기초용어 먼저 두 숫자중 더 큰 숫자를 구하는 간단한 프로그램을 구현해보자. a = int(input('첫 번째 숫자를 입력하세요. :')) b = int(input('두 번째 숫자를 입력하세요. :')) large = a if b > large : large = b print(f'더 큰 숫자는 {large}입니다.') # 첫 번째 숫자를 입력하세요. : 10 # 두 번째 숫자를 입력하세요. : 25 # 더 큰 숫자는 25입니다. - 순차구조 : 위와 같이 순서대로 처리되는 구조 - 복합문 : if문과 같이 복합적으로 이루어진 구문 - 대입문 : large = a 와 같은 단순한 구문 - 조건식 : if문 바로 뒤에 따라오는 조건 - 선택구조 : 조건식으로 평가된 결과에 따라 흐름이..

티스토리툴바