Computer Science
-
[Network] HTTPS란 무엇일까?Computer Science/Network 2021. 4. 2. 15:22
HTTPS 동작하는 방식 이번 글에서는 왜 HTTP가 아닌 HTTPS를 사용 하는 것이며 HTTPS는 어떠한 동작방식으로 작동하는지에 대해서 알아보겠습니다. 평상시에 인터넷을 하면서 HTTP, HTTPS에 대해서는 많이 들어봤을 것입니다. 일반적인 웹 사이트들을 보면 위와 같이 http://, https://와 같이 되어 있을 것입니다. http에는 자물쇠가 잠겨있지 않고, https에는 자물쇠가 잠겨있는 것을 보아 https가 좀 더 안전해보입니다. 왜 더 안전하고 http에는 어떠한 단점이 존재하는지 먼저 알아보겠습니다. HTTP의 약점 평문(암호화 하지 않은) 통신이기 때문에 도청 가능 통신 상대를 확인하지 않기 때문에 위장 가능 완전성을 증명할 수 없기 때문에 변조 가능 HTTP는 좋은 점과 편리..
-
[Network] TCP와 UDP의 구조와 특징Computer Science/Network 2021. 4. 1. 10:35
TCP와 UDP의 구조 정리 이번 글에서는 먼저 신뢰성/정확성을 우선으로 하는 연결형 통신 프로토콜인 TCP에 대해 알아보겠습니다. 캡슐화, 역캡슐화에 대해서 알고 있을 것입니다. 캡슐화: 응용 계층부터 물리 계층까지 계층별로 데이터를 전달할 때 헤더를 붙이는 것입니다. 역캡슐화: 물리 계층부터 응용 계층까지 계층별로 데이터를 전달할 때 헤더를 제거하는 것입니다. 이 중에서 TCP로 전송할 때 붙이는 헤더를 TCP 헤더라고 하고, 이 TCP 헤더가 붙은 데이터를 세그먼트(segment)라고 합니다. TCP 헤더에 목적지까지 데이터를 제대로 전송하기 위해 필요한 정보를 가지고 있습니다. TCP는 연결형 통신에 사용되는 프로토콜이라고 설명했습니다. 연결형 통신은 꼼꼼하게 상대방을 확인하면서 데이터를 전송합니..
-
최장 공통 부분 수열(LCS : Longest Common Subsequence)란?Computer Science/Algorithm 2020. 6. 21. 02:49
최장 공통 부분순서란? LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. Subsequence는 부분 수열이라는 뜻으로 연속적이지 않아도 되는 부분 문자열이다. 한마디로 두 문자열을 비교할 때 공통적으로 나타나는 부분 순서들 중 가장 긴 것이다. 예를들어 "ABCBDAB"와 "BDCABA"의 LCS를 구하면 "BCBA"가 나오게 된다. 그리고 LCS는 최적화를 해야 하는 문제이기 때문에 동적계획법(DP)를 사용하여야 가장 효율적으로 구할 수 있다. 그러면 간단하게 LCS를 구하는 예시를 보면서 어떤 느낌인지 생각해보자. 문자열 "CAT"와 "CRAB"의 LCS를 구하여 보자. 위의 c[i][j]의 배열의 의미는 예를들어 c[1][2]라면 "CAT"에서는 C까지..
-
레드블랙트리(Red-Black-Tree)란?Computer Science/Data_Structure 2020. 6. 20. 02:45
https://devlog-wjdrbs96.tistory.com/42?category=824010 이진 탐색 트리(binary search tree) 란? 이진 탐색 트리(binary search tree)는 이진 트리 기반의 탐색을 위한 자료 구조이다. 탐색은 내가 생각하기에도 코딩테스트와 같은 곳에서도 자주 출제가 되며 또한 컴퓨터 프로그램에서도 많이 �� devlog-wjdrbs96.tistory.com 기본적으로 레드블랙트리를 알기 위해서는 이진탐색트리가 무엇인지 알고 있어야 한다. 따라서 잘 모른다면 위의 글을 먼저 읽어보는 것을 추천하고, 안다는 가정하에 글을 써보려 한다. 이진 탐색 트리의 분석 위와 같은 이진탐색트리 연산은 트리의 높이가 log2n이기 때문에 평균적인 경우의 시간복잡도는 O..
-
시간복잡도 (Time Complexity)란?Computer Science/Data_Structure 2020. 2. 18. 22:35
1. 알고리즘 복잡도 계산 항목 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 2. 알고리즘 성능 표기법 Big O (빅-오) 표기법: O(N) 알고리즘 최악의 실행 시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이다. 3. 시간복잡도 가장 널리 사용되는 알고리즘의 수행시간 기준 더보기 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현 시간 복잡도가 높다는 것은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 증가한다는 의미이다. 하지만 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다. 입력의 크기가 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도..
-
소수 찾기(에라토스테네스의 체)Computer Science/Algorithm 2020. 2. 9. 21:51
일반 방법으로 "소수찾기" 알고리즘 문제를 풀면 시간초과를 경험하는 일이 많기 때문에 에라토스테네스의 체를 이용해서 소수를 구해보자. 2부터 n까지의 모든 수를 나열한다. 2는 소수이므로 소수로 입력한다. 후에 2의 배수들은 소수가 아니게 되므로 n까지의 자기 자신을 제외한 2의 배수를 모두 지운다. 3은 소수이기에 체크하고, 똑같이 3의 배수를 모두 지운다. 다음 소수인 5도 지워지지 않았기에, 5의 배수를 모두 지운다. 위의 과정을 n의 제곱근전의 최대 소수까지 반복을 해준다 (Math.sqrt())를 이용하자. https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 | 프로그래머스 1부터 입력받은 숫자 n 사이에 있는 소수..
-
이진 탐색(Binary Search) 란?Computer Science/Data_Structure 2020. 1. 30. 15:50
정렬된 배열에서의 이진 탐색 정렬된 배열의 탐색에는 이진 탐색(binary search)이 가장 적합하다. 이진 탐색은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. 이러한 방법에 의해 매 단계에서 검색해야 할 배열의 크기를 반으로 줄인다. 10억명의 정렬된 배열에서 이진 탐색을 이용하여 특정한 이름을 찾기 위해서는 단지 30번만 비교하면 된다. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를..
-
백 트래킹 (Backtracking) 이란?Computer Science/Algorithm 2020. 1. 30. 14:21
1. 백 트래킹 (Backtracking) 백트래킹 (Backtracking) 또는 퇴각 검색 (Backtrack)으로 불린다. 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현 각 후보를 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바..