학교 수업
-
Trie학교 수업/자료구조 2020. 9. 9. 18:23
Trie(트라이)- 개념 : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조- 사용 목적 : 문자열 탐색 ex) 검색어 자동완성, 사전에서 찾기, 문자열 검사- 구현 코드 예시문제 ) [프로그래머스] 자동완성https://programmers.co.kr/learn/courses/30/lessons/17685 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #include #include using namespace std; #define ALPHA 26 str..
-
sql문 연습사이트학교 수업/데이터베이스 2020. 6. 26. 18:30
sql문제를 직접 풀고 정답을 확인해볼 수 있는 사이트들. 1. 프로그래머스 : https://programmers.co.kr/learn/challenges?tab=sql_practice_kit 문제도 한국어로 되어있고, 다른 사람들의 풀이를 질문하기 영역에서 참고할 수 있다. 간단하게 전반적인 sql문을 연습하기에 좋았다. 2. SQLZOO : https://sqlzoo.net/wiki/SQL_Tutorial 문제도 설명도 다 영어로 되어있긴 하나, 다양하게 문제를 풀 수 있다. select문이나 join문을 좀 더 연습하기에 좋았다. 모르는 문제라면, 구글에 문제 검색시 git에 풀이를 적어둔 외국인들이 많아서 그것을 참고하면 된다.
-
TCP와 IP data format학교 수업/네트워크 2020. 6. 22. 18:00
이전 포스팅에서 data format에 대해 설명하지 못했어서 따로 설명한다. IP : Network layer에 존재하는 프로토콜 IP 통신단위 : Packet (Datagram이라고 명칭) Datagram formatHeader : routing과 delivery에 필요한 정보를 포함한다. 구조① Ver: IP버전을 기록, IPv4인지 IPv6인지② HLEN: header의 길이저장. 기본 Header 크기 20bytes + option있을 경우 -> header크기를 정확히 모르므로 데이터 시작부분을 알기 위해 저장. 전체길이/4의 몫을 저장한다.③ Service type④ Total length: Header 뿐만 아니라 데이터를 포함한 IP패킷 즉 Datagram의 전체 길이를 바이트단위로 표시..
-
Process학교 수업/유닉스 2020. 6. 20. 18:02
Process 프로세스- OS의 process 관련 포스팅에서 개념들은 다뤘다. (참고주소 : https://comyoung.tistory.com/97?category=854787) 그 외의 unix에서의 process 설명들을 설명해보겠다. 1. 프로세스 구조 ① 텍스트 영역: 실행 코드를 저장한다. 텍스트 영역은 프로세스 실행 중 크기가 변하지 않는 고정 영역에 속한다. ② 데이터 영역: 프로그램에서 정의한 전역 변수를 저장한다. 전역 변수는 프로그램을 작성할 때 크기가 고정되므로 고정영역에 할당된다. (컴파일 때 배열 크기가 정해진다.) ③ 힙(heap): 프로그램 실행 중에 동적으로 메모리를 요청하는 경우에 할당되는 영역으로, 빈 영역→할당→할당 해제처럼 상태가 변하는 가변 영역이다. (runti..
-
알고리즘 ch13 NP-complete Problems학교 수업/알고리즘 2020. 6. 16. 17:56
Optimization problem : 최적의 답를 찾는 문제 ex) shortest pathDecision problem : 답이 yes or no 인 문제 Class P - 어떤 decision 문제에 대해 polynomial time에 그 문제에 대한 해결법을 찾아낼 수 있다면, 그 문제는 클래스 P에 속한다. 즉, 다항시간내에 풀 수 있는 decision 문제들의 class를 class P라고 한다. 다항시간(polynomial time) : O(n^k) 다항시간내에 풀 수 있는 문제들은 tractable하다고 한다.문제의 어떤 알고리즘이 다항시간내에 풀린다면 efficient 알고리즘이라고 한다. Class NP- 어떤 문제가 non-deterministic polynomial time alg..
-
알고리즘 ch11 String match학교 수업/알고리즘 2020. 6. 16. 15:21
String- 문자의 나열- Substring : 연속되는 부분 문자열, Subsequence : 연속되지않는 부분 문자열 예시로 ACDEF와 ABKEF가 있다고 하자.substring = EF ACDEF ABKEF subsequence = AEF ACDEF ABKEF- Prefix : 문자열의 첫번째 문자부터 시작되는 부분문자열, Suffix : 문자열의 마지막문자부터 거꾸로 보는 부분문자열예시로 문자열 ALGORITHM이 있다고 하자prefix = AALALGALGO...ALGORITHMsuffix = MHMTHMITHM...ALGORITHM 본인 자기자신의 문자열을 제외하면 proper prefix, proper suffix라고 한다.예시로 설명하자면 ALGORITHM 을 제외한 것 String m..
-
알고리즘 ch10 Dynamic Programming학교 수업/알고리즘 2020. 6. 15. 19:29
Dynamic Programming- 큰 문제를 작은 문제로 나눠서 푸는 문제- Optimization problem 푸는 방법 중 하나이다. * divide and conquer과 다른점 : 메모리를 이용해 중복 계산을 하지 않는다. - 풀이 과정 ① 문제 특성을 파악 ② 점화식 정의 ③ 점화식대로 계산 수행 - 두가지 방식으로 나뉨 1) Top-down 방식 : recursion -> memoization 2) Bottom-up 방식 : Loop - dp로 풀수있는 optimization problem 예시) Matrix-Chain Multiplication problem : 두 개 이상의 행렬의 순서가 주어질 때 행렬의 곱셈에서 곱셈 연산의 수를 최소화하는 방법을 찾는 것 행렬의 곱 ABCD 에 대..
-
알고리즘 ch8 Greedy algotithm학교 수업/알고리즘 2020. 6. 15. 18:50
Optimization Problem- 여러개의 가능한 답 중에 가장 최적의 답 또는 최적의 답과 가까운 답을 고르는 문제- 비용을 최소화 한다거나 이익을 최대화 하는 답을 고르는 문제 Greedy Algorithm- 최적해를 구하는 데에 사용되는 근사적인 방법. - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함) Optimization problem 중 greedy 방법을 사용하는 문제1. Minimum Spanning Tree (MST) - Spanning tree 중 사용된 간선들의 가중치 합이 최소인 트리 즉, 그래프 내에 있는 모든 정점들을 가장 적은 수..