| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 23 | 24 | 25 | 26 | 27 | 28 |
- falsePosition
- MySQL
- 개발순서
- 1차예선
- chapter01
- vector미분
- 로지스틱 회귀
- Perceptron Convergence theorem
- 선형분류
- secant
- SCPC
- 알고리즘
- 자바ORM표준JPA프로그래밍
- graphical models
- 이것이 MySQL이다
- 5397번
- Numerical optimization
- 알고리즘대회
- CH01
- Fisher discriminant analysis
- 근구하기
- undirected graphical model
- bisection
- 스터디
- directed graphical model
- chapter02
- 인공지능
- 선형판별분석
- 2018
- 델타 rule
- Today
- Total
computer_study
[Python, C++] 알고리즘을 위한 대표적인(기본적인) 자료구조 본문
1. 배열(array)
-
array 장단점 (기술 대비)
- 장점 : 빠른 접근이 가능하다.(처음 주소를 알면 다음 애들을 순차적으로 접근가능)
- 단점 : 1. 연관된 데이터 추가나 삭제가 어렵다. (ex, 추가 시에는 공간을 새로 생성, 삭제 시에는 빈공간이 생김.)
2. 미리 최대 길이를 지정해야된다.
-
파이썬에서 배열 : list를 사용한다.
1. 리스트에 요소 추가 ( append )
x = [1, 2, 3]
x.append(4)
# x = [1, 2, 3, 4]
x.append([5,6])
# x = [1, 2, 3, 4, [5, 6]]
2. 리스트에 요소 삭제 ( del )
x = [1, 2, 3]
del x[1]
# x = [1, 3]
3. 리스트 정렬 ( sort )
x = [1, 4, 2, 3]
x.sort()
# x = [1, 2, 3, 4]
x = ['a', 'c', 'b']
x.sort()
# x = ['a', 'b', 'c']
-
c++에서 배열
c언어와 같이 int arr[num] , double arr[num] 식으로 사용한다.
1. 배열의 초기화
int arr[3] = {}; // 모두 0으로 초기화
int arr[3] = {1, 2, 3}; // 0번 index부터 1,2,3으로 초기화
int arr[] = {1, 2, 3}; // 초기화를 하면 []안은 생략가능
2. enum을 사용한 배열
// 숫자로 표기하면, 어느 학생이 어느 점수를 받았는지 헷갈리므로 enum사용.
enum StudentNames {
KENNY, // 0
KYLE, // 1
STAN, // 2
MAX_STUDENTS // 3
};
int main() {
int scores[MAX_STUDENTS]; // allocate 3
integers scores[STAN] = 76;
return 0;
}
3. 배열 parameter
// value를 parameter로 넘기면 복사본이 넘겨저 값이 변하지않지만,
// array를 parameter로 넘기면 실제 array가 넘겨져 값이 변한다.
#include <iostream>
using namespace std;
void passValue(int value){ // value는 인수의 복사본이다.
value = 99; // 여기에서 값을 변경해도 인수의 값은 변경되지 않는다.
}
void passArray(int prime[3]){ // prime은 실제 배열이다.
prime[0] = 11; // 여기에서 요소의 값을 변경하면 실제 배열의 요소의 값이 바뀐다.
prime[1] = 7;
prime[2] = 5;
}
int main() {
int value = 1;
cout << "before passValue: " << value << "\n";
passValue(value);
cout << "after passValue: " << value << "\n";
int prime[3] = { 2, 3, 5 };
cout << "before passArray: " << prime[0] << " " << prime[1] << " " << prime[2] << "\n";
passArray(prime);
cout << "after passArray: " << prime[0] << " " << prime[1] << " " << prime[2] << "\n";
return 0;
}
/*
before passValue: 1
after passValue: 1
before passArray: 2 3 5
after passArray: 11 7 5
*/
추가적인 배열에 관한 정보는 ' https://boycoding.tistory.com/194?category=1009770 [소년코딩] ' 에서 확인할 수 있다..
c++에선 배열 대신 자동으로 메모리가 할당되는 vector 컨테이너를 사용할 수 있다.
blockdmask.tistory.com/70 에서 개념 및 사용법을 확인할 수 있다.
2. 큐(queue)
-
파이썬에서 queue 라이브러리
1. 일반적인 fifo
import queue
data_queue = queue.Queue() # 생성
data_queue.put("test") # enqueue string
data_queue.put(1) # enqueue 숫자
data_queue.qsize() # queue의 크기
data_queue.get() # dequeue (fifo에 따라 선택된다.)
2. Lifo 라이브러리(Last-in, First-out)
import queue
data_queue = queue.LifoQueue() # 생성
# size, put, get 똑같이
3. priorityQueue만들기 ( 번호가 낮은것이 우선순위가 높다. )
import queue
data_queue = queue.priorityQueue() # 생성
data_queue.put((10,"test")) # (우선순위, data)
data_queue.put((5,1))
# get, size는 똑같다.
# get시 우선순위가 높은게 나온다.
-
c++에서 queue
1. <queue> 헤더파일을 include하여 사용할 수 있다.
2. fifo 방식으로 동작한다.
3. list와 dequeue 에 붙여서 사용가능하며 vector container와는 함께 사용할 수 없다.
(vector는 앞에서 빼는 동작이 없으므로)
#include <iostream>
#include <queue>
using namespace std;
int main(){
queue<int> q; // queue 생성
cout << "size : " << q.size() << endl; // queue의 size
cout << "empty : " << q.empty() << endl; // 비어있으면(size가 0이면) true
q.push(1); // 원소를 queue의 마지막에 넣는다.
q.push(2);
q.push(3);
cout << "front : " << q.front() << endl; // 첫번째 원소 (pop시 나올 원소)
cout << "back : " << q.back() << endl; // 마지막 원소 (방금 push한 원소)
q.pop(); // q.front()에 있던 원소가 나온다.
return 0;
}( 출처 : blockdmask.tistory.com/101 )
3. 스택(stack)
스택은 단순하고 빠른 성능을 위해 사용도므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.
ex) 파이썬은 재귀함수가 1000번까지 가능하다.
-
stack 장단점 (기술 대비)
- 장점 : 구조가 단순해서 구현이 쉽고 데이터 저장/읽기 속도가 빠르다
- 단점 (일반적인 스택 구현시) : 데이터의 최대 개수를 미리 정해야 하기 때문에 저장공간의 낭비가 발생할 수 있다.
(일반적인 stack의 단점이고, 만약 linked list를 이용하여 stack을 구현한다면 데이터의 최대 개수를 미리 정하지 않아도 된다.)
-
파이썬에서 스택
1. 리스트에서 제공하는 메서드로 스택. append(push), pop 사용
data_stack = list()
data_stack.append(1) // push
data_stack.append(2)
data_stack.pop() // pop
2. pop, push 구현하기
stack_list = list()
def push(data):
stack_list.append(data)
def pop():
data = stack_list[-1] // stack_list배열의 마지막 표현법
del stack_list[-1] // 값 삭제
return data
-
c++에서 stack
1. <stack> 헤더파일을 include하여 사용할 수 있다.
2. LIFO ( Last In First Out ) 방식으로 동작한다.
#include <iostream>
#include <stack>
using namespace std;
int main(){
stack<int> s; // stack 생성
s.push(3); // top에 원소 추가
s.push(2);
s.push(1);
cout << "top : " << s.top() << endl; // 현재 top 가져오기
s.pop(); // top에 있는 원소를 뺀다. 1이 삭제
s.pop(); // 2가 삭제
cout << "size : " << s.size() << endl; // 현재 stack의 size를 알 수 있다.
cout << "empty : " << s.empty() << endl; // stack이 비어있다면 true
return 0;
}
4. 링크드리스트(linked-list)
-
linked list 장단점(기술 대비)
- 장점 : 미리 데이터 공간을 할당하지 않아도 된다. (cf, 배열은 미리 공간을 할당해야된다.)
- 단점 : 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지않다
연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다(head부터 순서대로 탐색해야되므로)
중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다
-
파이썬으로 linked list 만들기
+) python에서 class 사용하는 이유
python은 객체지향 문법으로, class를 사용하여 변수나 함수를 재 선언하여 발생하는 오류를 해결할 수 있다.
(참고 : server-talk.tistory.com/220 )
1. node 구현
class Node:
def __init__(self, data): # 이 class를 이용해 객체를 만들 때 마다 node가 하나씩 생성된다.
self.data = data
self.next = None인자로 data만을 받는다.
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next위 구현과 다른방법(class 문법 사용해서 의미있게)
-> 인자로 data와 next 주소를 받게한다. (next가 none이면 그대로 none으로 들어간다)
2. node와 node 연결하기(포인터 활용)
node1 = Node(1) # node 생성
node2 = Node(2)
node1.next = node2 # node1다음에 node2연결
head = node1 # 처음 node 저장
3. 링크드 리스트로 데이터 추가하기 (마지막에 추가)
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def add(data):
node = head
while node next: # 마지막 node를 찾는다
node = node.next
node.next = Node(data) # 마지막에 새로운 node생성
4. linked list로 데이터 추가(중간에 추가) (ex. 1,2,3,4,5 중 1, 2 사이에 1.5를 추가하고 싶다면)
node3 = Node(1.5)
node = head
search = True
while search: # 1을 찾아서 그 다음에 추가하기 위함
if node.data == 1:
search = False
else:
node = node.next
node_next = node.next
node.next = node3
node3.next = node_next # 가르키는 주소값을 바꾼다.
5. delete
def delete(self, data):
if self.head == '':
print("there's no head")
return
if self.head.data == data: # head 삭제
temp = self.head
self.head = self.head.next
del temp
else: # 삭제 할 data가 head가 아닌경우 (마지막노드 학제 & 중간노드 삭제)
node = self.head
while node.next:
if node.next.data == data: # 삭제 할 data라면
temp = node.next
node.next = node.next.next
del temp
return
else:
node = node.next
6. 파이썬 객체지향 프로그래밍으로 linked list 구현하기
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class NodeMgmt: # management
def __init__(self,data): # head가 가진 data까지 받아서 head로 지정해준다.
self.head = Node(data)
def add(self, data): # 무조건 마지막에 추가하는 경우
if self.head == '': # head가 비어있다면
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
def desc(self): # linked list 순회하며 출력
node = self.head
while node:
print(node.data)
node= node.next
def delete(self, data): # 삭제
if self.head == '':
print("there's no head")
return
if self.head.data == data: # head 삭제
temp = self.head
self.head = self.head.next
del temp
else: # 삭제 할 data가 head가 아닌경우 (마지막노드 학제 & 중간노드 삭제)
node = self.head
while node.next:
if node.next.data == data: # 삭제 할 data라면
temp = node.next
node.next = node.next.next
del temp
return
else:
node = node.next
def main(): # 사용법
linkedlist1 = NodeMgmt(0) # linked list 생성
for data in range(1,10)
linkedlist1.add(data)
linkedlist1.desc(). # -> 0~9 까지 출력된다.
linkedlist1.delete(9) # 9가 삭제된다
if __name__ == "__main__":
main()
7. double linked list
양쪽으로 연결이 되어있어, 양쪽으로 탐색이 가능하다.
class Node:
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
class NodeMgmt: # management
def __init__(self,data):
self.head = Node(data)
self.tail = self.head # 뒤에서부터도 찾을 수 있게하기위함. (처음엔 head == tail)
def insert(self, data):
if self.head == None: # head가 비어있다면
self.head = Node(data)
self.tail = self.head
else: # 마지막에 추가 후 tail 바꿔주기
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node # 마지막 추가된 new가 앞부분인 node를 가르키도록 한다.
self.tail = new # 새롭게 만들어진 new가 마지막 node이므로, 이를 tail로 저장해준다.
def desc(self): # linked list 순회하며 출력
node = self.head
while node:
print(node.data)
node= node.next
def search_from_head(self, data): # head 부터 검색
if self.head == None: # head가 없으면
return False
node = self.head
while node: # head부터 해당 data찾기
if node.data == data:
return node # 찾으면 그 node return
else:
node = node.next
return False # 못찾으면 False return
def search_from_tail(self, data): # tail 부터 검색
if self.tail == None: # tail이 없으면
return False
node = self.tail
while node: # tail부터 해당 data찾기
if node.data == data:
return node # 찾으면 그 node return
else:
node = node.prev
return False # 못찾으면 False return
def insert_before(self, new_data, target_data): # before_data앞에 data를 추가한다
if self.head == None: # head가 없으면 data를 추가로 생성
self.head = Node(new_data) # 특정 data앞에 추가한다는 조건 무시하게된다.
return True
else:
node = self.tail # 현재 node.data가 입력받은 before_data와
while node.data != target_data: # 같을 때 까지 앞으로 이동
node = node.prev
if node == None: # 해당 node가 없으면
return False
# 위 과정은 search_from_tail로 대체 가능.
# node = search_from_tail(target_data)
# 이쪽으로 빠지면 현재 node.data가 target_data
new = Node(new_data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new
return True
def __main__: # 사용법
double_linked_list = NodeMgmt(0) # double linked list 생성
for data in range(1,10):
double_linked_list.insert(data)
double_linked_list.insert_before( 1.5 , 2 ) # 2 앞에 1.5 넣겠다.
node_3 = double_linked_list.search_from_tail(1.5) # 뒤에서부터 찾기 시작하여 1.5를 찾는다'알고리즘 > 개념정리' 카테고리의 다른 글
| [python/c++] (key, value)로 변수저장하기 (dictionary, map) (0) | 2020.08.12 |
|---|---|
| [c++] 문자 입력 방법 ( get line( ) ) (2) | 2020.08.11 |
| [알고리즘] counting sort (계수 정렬) (0) | 2020.08.07 |
| Recursion (0) | 2020.07.07 |
