CS12 [알고리즘] 분할정복(divide and conquer) 분할정복이란 ? 분할정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적인 예로는 정렬 알고리즘 중 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고리 푸리의 변환(FTT) 문제들이 대표적입니다. 정렬 알고리즘 선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)로 입력하는 배열의 크기가 크다면 정렬하는데 시간이 오래 걸릴 수 있습니다. 반면 분할정복 알고리즘을 사용하는 합병정렬의 실행시간은 O(nlogn)으로 퀵 정렬은 최대 O(n^2)지만 최선이나 평균의 경우 O(nlogn)으로 비교적 빠른 시간을 갖는 것을 볼 수 있습니다. 정렬 알고리즘 최대 실행 시간 최소 실행 시간 평균 실행 시간 선택 정렬 O(n^2) O(n^2) O(n^2) 삽입 정렬 .. 2022. 9. 21. [알고리즘] 백트래킹 (Backtracking) 백트래킹(Backtracking)이란 ? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 깊이 우선 탐색 (DFS) vs. 백트래킹 (Backtracking) DFS DFS는 가능한 모든 경로를 탐색합니다. 그러므로 불필요한 경로를 사전에 차단하는 등의 행동이 없으므로 경우의 수를 줄일 수 없습니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능합니다. 백트래킹 해를 찾아가는 도중 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다. 하지만 만약 N! 의 경우의 수를 가진 문제에서.. 2022. 9. 14. [네트워크] TCP 3-way handshake / 4-way handshake TCP 3-way handshake란 ? 연결하고자 하는 두 장치 간의 논리적 접속을 성립하기 위해 사용하는 연결 확인 방식으로 3번의 확인 과정을 거친다고 해서 3-way handshake라고 합니다. 간단하게 표현하자면 다음과 같습니다. A → B : 내 말 들려 ? B → A : 잘 들려. 내 말은 들려 ? A → B : 잘 들려. SYN (synchronize sequence numbers) 연결 확인을 위해 보내는 무작위의 숫자값입니다. 무작위의 숫자값을 사용하는 이유는 ? Connection을 맺을 때 사용하는 포트는 유한 범위 내에서 사용하고 시간이 지남에 따라 재사용됩니다. 그러므로 두 통신 호스트가 과거에 사용된 포트 쌍을 사용할 가능성이 존재합니다. 서버 측에서 패킷의 SYN을 보고 패.. 2022. 9. 13. [자료구조] 해시 함수(Hash Function) / 해시 테이블(Hash Table) 해시 함수(Hash Function)란 ? 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때, 매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시값, 매핑하는 과정을 해싱이라고 합니다. 해시 함수는 해시값의 개수보다 많은 키값을 해시값으로 변환하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌이 발생하게 됩니다. 이러한 해시 충돌 발생 가능성이 있음에도 불구하고 해시 테이블을 사용하는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위함입니다. 해시 함수는 항상 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기와 상관없이 데이터에 빠르게 접근할 수 있으며 색인은 상수 시간으로 작동하기 .. 2022. 9. 8. [네트워크] TCP vs. UDP TCP와 UDP란 ? 데이터를 보내기 위해 사용하는 프로토콜입니다. TCP란 ? 인터넷상에서 데이터를 메세지의 형태로 보내기 위해 IP와 함께 사용하는 프로토콜입니다. TCP는 IP를 함께 사용하는데 IP가 데이터를 처리한다면, TCP는 패킷을 추적 및 관리합니다. TCP는 연결형 서비스로 인터넷 환경에서 기본으로 사용합니다. 패킷이란 ? 인터넷 내에서 데이터를 보내기 위한 경로배정(라우팅)을 효율적으로 하기 위해 데이터를 여러 개의 조각들로 나누어 전송합니다. 이 때, 나누어진 이 조각을 패킷이라고 합니다. TCP는 어떻게 패킷을 추적 및 관리할까요 ? 데이터는 패킷 단위로 나누어 같은 목적지인 IP계층으로 전송됩니다. 이 때, 패킷에 번호를 부여하여 패킷의 분실 확인을 하여 목적지에서 재조립을 합니다.. 2022. 9. 8. 이전 1 2 3 다음
