본문 바로가기

컴퓨터공학기초 개념146

웹개발 기본지식(2) 1. DNS 동작원리 - 어떤 웹사이트에 접근할 때, www.abc.com과 같은 형식의 주소를 이용하여 해당 웹사이트에 접근한다. - 기존의 웹사이트 주소는 192.0.0.0과 같이 숫자 형식의 IP 주소였다. 하지만, 사용자가 모든 웹사이트의 주소를 IP 형식으로 외울 수 없기에 등장한 개념이 바로 DNS(Domain Name Server)다. - Domain Name은 사람이 쉽게 인지하고 기억할 수 있는 형태의 웹사이트 주소를 의미한다. 기존의 IP주소를 DNS라는 서버에 해당 IP주소와 대응하는 Domain Name을 함께 저장해 놓는다. - 사용자가 Domain Name을 이용하여 웹사이트의 접근을 요청하면, 해당 Domain Name이 DNS에게 전달되고 이에 해당하는 IP주소로 연결시키는 .. 2021. 1. 20.
웹개발 기본지식(1) 1. 인터넷 작동방식 - 인터넷 이전의 컴퓨터는 케이블로 연결되어 소통했다. 그러므로 컴퓨터의 개수가 늘어나면 케이블의 개수도 늘어났다. - 그러나 케이블을 통한 연결은 한계가 있다. 1:1로 연결되는 케이블은 지구 반대편까지 연결하기에는 많은 장애물이 있으며, 데이터 처리, 전송 및 비용적인 측면에서의 효율이 좋지 않다. - 이 문제를 해결해준 것이 Router라는 통신장치다. 당연히 Router와 컴퓨터는 케이블에 연결이 되어 있지만 하나의 라우터를 Hub로 주변의 다양한 컴퓨터와 연결하여 통신이 가능해졌다. 다시말해, Router에 의해 더 적은 수의 케이블을 사용하여 더 많은 컴퓨터간의 통신이 가능한, 새로운 네트워크가 형성된 것이다. 이러한 Router간의 통신까지 가능해지면서 Router간의 .. 2021. 1. 20.
Algorithm - 알고리즘 핵심정리 1. 정의 알고리즘이란? 어떤 문제를 해결하기 위해 사용되는 풀이과정을 말한다. 즉, 문제해결방법이다. 수학에서 한 문제에 대해 여러가지 풀이법이 존재하는 것처럼, 프로그래밍 또한 한 문제에 대해 여러 풀이법이 존재한다. 여러가지 풀이법 중 가장 효율이 좋은 방법을 어떤 문제에 대한 알고리즘이라고 한다. 수학의 공식처럼, 특정 형태 또는 구조를 갖는 프로그래밍 문제에는 공식화된 알고리즘이 존재한다. 2. 알고리즘의 종류 a) 정렬(Sort) 1. 버블정렬(Bubble) 인접한 두 데이터의 크기를 비교하여 정렬하는 알고리즘 2. 선택 정렬(Selection) 주어진 데이터 중 최소값을 찾아 순서대로 정렬하는 알고리즘 후보군 중 최소값을 찾아낸 후, 맨 앞의 데이터와 교체한다. 교체된 맨 앞의 데이터를 제외.. 2020. 10. 7.
Algorithm - 자료구조 핵심정리 1. 정의 a) 자료구조란? 대량의 데이터를 효율적으로 관리하기 위해, 데이터를 저장 및 정렬하는 방식을 말한다. 데이터를 어떤 방식으로 저장하고 정렬하느냐에 따라 추출 방식 등 데이터를 처리 및 조작하는데 필요한 코드가 달라진다. 2. 자료구조 (Data Structure) a) 배열(Array) 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조 각 데이터마다 index를 부여하여 데이터 검색에 용이(장점) 배열은 크기가 고정적(단점) 데이터가 삭제되면 배열 전체의 데이터를 재정렬(단점) b) 큐(Queue) FIFO(First In, First Out)방식으로 데이터를 저장 및 정렬하는 자료구조 FIFO방식으로 인해 데이터 삭제시, 재정렬이 필요없다. 운영체제(OS)에서 프로세스 스.. 2020. 10. 6.
Advanced Algorithm - Backtracking 1. 백트래킹이란? - 완전탐색 알고리즘의 하나다. - 완전탐색을 하는 도중, 현재의 탐색이 무의미하다고 판단이되면 되돌아가는 알고리즘이다. - 그래서 퇴각 검색이라 부르기도 한다. 2. 백트래킹의 로직 - 백트래킹은 제약조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략이다. 해를 찾기위해서 어떤 후보군을 대상으로 제약조건을 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단되면, 그 즉시 backtrack(다시는 해당 후보군을 체크하지 않을 것을 표시)한 후, 다른 후보군으로 넘어가는 방식으로 최종적으로 최적의 해를 찾는 전략이다. 백트래킹 전략에 의해 연산의 대상이 되는 후보군이 적어지고, 그만큼 시간복잡도가 줄어드는 것이다. a) 어떻게 구현.. 2020. 10. 5.
Advanced Algorithm - MST(Improved Prim's Algorithm)(6) 1. 개선된 프림 알고리즘이란? - 기존의 프림 알고리즘에서 파생된 알고리즘으로, 개선된 프림 알고리즘은 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식이다. 그렇다면 무엇이 개선되었을까? - 이전 포스팅에서 다뤘던 기본적인 프림 알고리즘은 간선을 기준으로, 간선의 개수에 따른 while문의 반복회수를 측정하여 E log E 만큼의 시간복잡도를 갖는다. - 이와는 다르게, 개선된 프림 알고리즘은 노드를 기준으로 하여 E log V 만큼의 시간복잡도를 갖는다. 그래프는 노드의 수 보다 간선의 수가 더 많기 때문에 그 차이만큼 반복회수가 줄어들어 알고리즘의 시간복잡도가 개선됨을 의미한다. 2. 개선된 프림 알고리즘의 로직 - 개선된 프림 알고리즘은 노드마다 key값을 갖고 있는 것이 특징이다. 로직.. 2020. 10. 4.
Advanced Algorithm - MST(Prim's Algorithm)(5) 1. 프림 알고리즘 코드구현 a) 기본그래프 구현 - 중복된 간선 정보를 제거한다. ex) (7, 'A', 'B')와 (7, 'B', 'A')는 동일하다. myedges = [ (7, 'A', 'B'), (5, 'A', 'D'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (5, 'C', 'E'), (7, 'D', 'E'), (6, 'D', 'F'), (8, 'E', 'F'), (9, 'E', 'G'), (11, 'F', 'G') ] b) 프림 알고리즘 로직구현 1. 그래프의 모든 간선정보를 저장한다. (adjacent_edges) 2. 임의의 노드를 선택하여 '연결된 노드 집합' 이라는 리스트에 삽입한다. (connected_nodes) 3. 2단계에서 선택된 노드.. 2020. 10. 3.
Advanced Algorithm - MST(Prim's Algorithm)(4) 1. 프림 알고리즘이란? - 대표적인 최소신장 알고리즘 중 하나이다.(Kruskal's Algorithm & Prim's Algorithm) a) 크루스칼 알고리즘과 프림 알고리즘의 비교 크루스칼 알고리즘은 전체 간선을 가중치 기준으로 오름차순 정렬하여, 낮은 가중치를 가진 간선이면서 동시에 사이클이 발생하지 않는 노드를 연결시켜 MST(최소신장트리)를 구하는 알고리즘이다. 프림 알고리즘은 어떤 노드와 인접한 노드의 간선만을 대상으로 하여, 인접노드 중에서 간선의 가중치가 가장 작은 간선을 선택하여 해당 인접노드를 연결하는 방식으로 MST를 구한다. 두 알고리즘 모두 탐욕 알고리즘을 기반하고 있다.(당장을 위한 최소비용을 선택하여 결과적으로 최적의 솔루션을 찾음) b) 프림 알고리즘의 로직 임의의 노드를.. 2020. 10. 2.
Advanced Algorithm - MST(Kruskal's Algorithm)(3) 1. 크루스칼 알고리즘의 구현 1) 기본 그래프의 구현 - 아래의 그림과 같은 기본 그래프를 딕셔너리를 이용하여 구현한다. mygraph = { 'vertices':['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'edges':[ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8, 'C', 'B'), (5, 'C', 'E'), (5, 'D', 'A'), (9, 'D', 'B'), (7, 'D', 'E'), (6, 'D', 'F'), (7, 'E', 'B'), (5, 'E', 'C'), (7, 'E', 'D'), (8, 'E', 'F'), (9, 'E', 'G'), (6, .. 2020. 10. 1.

티스토리툴바