알고리즘
부울대수
A+(B+C) = (A+B)+C
A 라는 생각에 (B+C)를 추가한거나, (A+B)라는 생각에 C를 추가한거나 같다
알고리즘
주어진 문제를 해결하기 위한 절차
컴퓨터에서의 알고리즘은👀??
주어진 문제를 단위 작업으로 나누고 문제를 해결하기 위한 처리 순서를 정하는 과정 !
🎈 알고리즘의 종류
정렬 / 검색 / 문자열 패턴 매칭 / 계산
🎈 알고리즘의 구조화
전체 알고리즘을 다음과 같이 세부분으로 나눔
1. 홀수합, 짝수합을 구하는 부분(add)
2. 출력하는 부분(output)
3. Main 함수(main)
자료구조
컴퓨터 자료형의 전체 구조
기본 자료형
숫자로 인식 : int, float, short 등
문자로 인식 : 0과 1조합을 아스키코드 값에 해당하는 문자로 인식
논리값으로 인식 : T of F 인지 인식
사용자정의 자료형
배열 : 동일한 기본 자료형을 여러개 모은 것
ex. int 10개를 모아서 자료형으로 선언
구조제 : 기본 자료형을 여러개 모은 것
클래스 : 구조체에 함수까지 모아서 자료형으로 선언한 것
재정의 자료형 : enum, def 등을 이용하여 이름을 재정의
자료구조의 종류
자주 사용하는 자료구조
- 리스트
- 연결 리스트
- 배열
- 스택
- 큐
- 데크
- 트리와 힙
- 그래프
스택, 큐, 데크, 트리는 리스트 or 연결 리스트로 구현 가능
실제 자료구조를 구현하는 기술은 리스트와 연결 리스트 두가지!
즉!!!💡💡리스트/연결 리스트를 이용하여 다양한 자료구조가 만들어진다!
=============
1. 리스트
연속적인 저장의 형태를 가짐
배열 : 크기가 변하지 않는 리스트형 자료구조
리스트 : 크기가 변하는 자료구조
2. 연결 리스트
저장하는 각 데이터(기본 데이터, 배열, 구조, 클래스)가 데이터 외에 다음과 이전의 데이터를 가리키는 정보를 가지고 있는 구조
3. 해쉬 테이블의 구현
해쉬 테이블 : 데이터를 저장할 때, 저장할 위치를 해쉬 함수를 이용해서 생성하고, 생성된 위치에 데이터를 저장하는 방식에서 사용하는 주소테이블
순서 리스트와 연결 리스트 자료구조를 조합하여 사용함.
ex.
이수현 > 배열의 0번지에 저장
직장인 > 배열의 1번지 저장
서울 > 배열의 1번지에 저장하면서 직장인과 연결 리스트로 연결
4. 순서 리스트와 자료구조
리스트 기반의 자료구조
5. 배열 자료구조
📍 프로그램 언어의 기능 중에서 가장 많이 사용!!
동일한 형태 의 자료를 연속해서 저장하는 구조를 가짐
일상생활의 예로 들면!
은행에서 계좌를 관리하는 경우 계좌정보는 고객과 상관없이 동일한 모습을 지님!
6. 스택 자료구조
- 데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조
- 스택형태의 데이터 구조를 LIFO(last in first out)형이라고 함
- 스택에 데이터 넣는 것을 push, 꺼내는 것을 pop
ex. 컴퓨터가 사용하는 수식(후위 표기법)으로 변환과 연산
우리가 흔히 하는 계산 : 중위표기법
컴퓨터가 사용하는 수식 : 후위표기법
(A*B)-(C/D)
- 중위표기법을 후위표기법으로 변경
괄호 무시 > A 출력 > *은 스택에 푸쉬 > B 출력
스택에 있던 * 출력 > AB 스택으로 푸쉬
AB* 출력
괄호 무시 > C 출력 > / 스택에 쌓기 >> - 위에 / 쌓여 있음
D출력
'AB*CD/-' >>> 후위표기법
- 후위표기법 연산
AB*CD/-
AB 순차적으로 스택에 푸쉬 > AB를 * 로 연산한 값을 변수 X 에 저장
CD 스택에 푸쉬 > / 스택에 푸쉬 > C와 D를 / 로 연산. 연산한 값을 변수 Y에 저장
'-' 스택에 푸쉬 > 그럼 X Y - 로 쌓여있는 상태 > X 와 Y를 - 연산 그 결과를 Z 스택에 저장
7. 큐 자료구조
-
데이터가 입력되면 입력되는 순서대로 쌓고, 먼저 들어온 것부터 먼저 사용하는 자료구조
-
큐 형태의 데이터 구조 FIFO (First In First Out)형
-
큐의 구현 : 배열 이용 (순환 큐) 연결 리스트 이용(링크드 큐)
8. 데크 자료구조
-
리스트의 양쪽에서 삽입과 삭제가 모두 이루어지는 자료구조
-
스택과 큐를 혼합한 구조로 하나의 배열을 선언 한 후, 2개의 포인터로 양쪽 끝을 가리킴. 이것을 이용하여 양쪽에서 삽입, 삭제 연산 수행
데크 자료구조 종류
1. 입력 제한 데크(스크롤) 삽입이 한쪽에서만 일어남
2. 출력 제한 데크(셀프) : 삽입이 한쪽에서만 일어나는 테크
