지난 시간에는 프론트엔드/백엔드의 차이점을 간단하게 살펴보았습니다. 이 두개가 모두 웹 개발 분야인데 그렇다면 웹이란 무엇일까요?? 웹이란? 웹에 대해서 자세히 알아보기 전에 간단한 OX퀴즈를 내보겠습니다. 인터넷은 웹이다? O/X 인터넷은 네트워크와 네트워크 사이를 연결해서 통신을 합니다. 이 인터넷에서 파일이나 메일, 문서 등을 주고받습니다. 이때 중요한게! 요청하는 쪽이 클라이언트고 제공하는 쪽이 서버입니다. 만약에 서버와 클라이언트가 서로 호환이 안된다면?? 문제가 생기겠죠 이를 위해서 약속을 정의합니다. 파일 = FTP , 문서 = WWW(http) 이런 방식으로요. 즉 웹(WWW)은 인터넷에서 문서를 주고받기 위한 규약이므로 정답은 X입니다. 역사적으로 발전해오면서 웹은 현재와 같은 형태를 갖..
전체 글
웹 백엔드 개발자는 프론트엔드처럼 사용자에게 직접적으로 보이는 부분이 아닌 서버와 관련된 작업을 합니다. 여기에는 데이터베이스 작업이 포함될 수 있죠. 이때 서버와 클라이언트의 연결이 소켓 같은 방식이 아닌 웹을 기반으로 진행한다는 게 중요합니다. 사용자가 웹에서 어떤 정보를 입력 후 전송한다면 그 정보를 이용해 저장도 하고 연산 후 사용자에게 다시 보여주는 작업을 할 수 있죠. 사용자(클라이언트)가 요청하면(GET/POST) 이를 서버에서 응답하는 일련의 과정이 필요합니다. HTML/CSS/Javascript 등으로 웹 페이지를 꾸미고 동적이게 만드는 부분이 프론트엔드고 그 뒤의 부분들이 백엔드의 영역으로 서버 프로그래밍이 됩니다. 백엔드 개발을 위해서는 Java 언어와 SQL 등 기본적인 내용을 숙지..
그리디 알고리즘이란? 그리디 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 되는데, 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이아니라 현 시점의 정보를 바탕으로 가장 이익이 되는 원소들을 선택하는 방법이라고 할 수 있다. 복잡한 과정을 거치지 않고, 상황을 종합적으로 판단하는게 아니기 때문에 매우 빠른 알고리즘이라고 할 수 있다. 이러한 그리디 알고리즘은 최적화 문제를 해결하기 위한 방법이다. 2878번: 캔디캔디 문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는..
신장 트리란 그래프 중 모든 정점이 간선으로 연결되어 있되, 간선간의 사이클이 없는 그래프 최소 비용 신장 트리 각 간선에 비용(가중치 합)이 있을때 최소화 하는 신장트리를 말함 크루스칼 알고리즘 1. 간선들을 가중치의 오름차순으로 정렬 2. 사이클을 형성하지 않는 간선 선택 3. 해당 간선을 현재의 집합에 추가 즉 간선을 중심으로 탐색을 합니다. 아래는 이해하기 쉽게 gif 이미지를 가져왔다. be간선을 연결하려고 하면 이는 사이클을 형성하기에 제외하는 것을 볼 수 있다. MST의 대표 알고리즘인 프림 알고리즘과 크루스칼 알고리즘을 비교하면 아래와 같다. 크루스 알고리즘 프림 알고리즘 간선을 기반으로 하는 알고리즘 정점을 기반으로 하는 알고리즘 전단계에서 만들어진 신장트리와는 상관없이 무조건 최저 간선..
그래프(Graph)의 종류 무방향 그래프 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A) 동일 방향 그래프는 는 다름 간선에 방향성이 존재하는 그래프, A -> B로만 갈 수 있는 간선은 로 표시한다. 가중치 그래프 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’ 라고도 한다. 그래프 표현 방법 인접 행렬먼저, 인접행렬(adjacency matrix) 방법이 있다. 인접 행렬은 그래프를 nxn의 행렬로 표현하는 방법이다. 인접 행렬 방법에서, i 번째행 j 번째 열을 Aij 라고 할 때 정점 i와 j 사이에 엣지가 있으면 1, 없으면 0으로 표시한다. 인접 리스..
개요 Dynamic Programming은 흔히 생각하는 동적 프로그래밍(ex 동적 할당)과는 거리가 있다. 따라서 동적 계획법이라고 번역하는 것이 맞다고 한다. 동적 계획법에서는 어떤 문제를 더 작은 문제들로 나누고 각 조각의 답을 계산하고, 이 답들로 원래 문제의 답을 계산한다. 다만 어떤 부분 문제가 여러번 계산이 될 가능성을 없애기 위해 각 문제의 답을 메모리에 저장해 둔다. 가장 대표적인 동적 프로그래밍을 이용가능한 예인 피보자치 수열로 설명한다. 보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다. function fib(n) if n = 0 return 0 else if n=1 return 1 else return fib(n-1) + fib(n-2) 이때, fib(5)를 구한다고 한다면..
해시 테이블 해시 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다. 해시 함수 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시 테이블 상의 주소를 리턴하며 다음의 두 가지 성질을 가지도록 만들어야 한다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 1) 나누기 방법 나누기 방법은 원소를 해쉬 테이블의 크기로 나누어 나머지의 값을 테이블의 주소로 사용하여 저장하는 방법이다. 위의 예제는 해쉬 테이블의 크기가 13 일때 해쉬함수에 25, 13, 16, 5 ,7 의 입력값이 주어진 경우..
개요 K-D 트리 (K-Dimensional Tree라고도 함)는 각 노드의 데이터가 공간의 K 차원 포인트인 이진 검색 트리다. 즉, K 차원 공간의 점을 구성하기위한 공간 분할 구조이다. K-D 트리의 비 잎 노드(non-leaf node)는 공간을 두 부분으로 나눈다. 루트는 x- 정렬 된 평면을 가질 것이고, 루트의 자식들은 모두 y- 정렬 된 평면을 가질 것이고, 루트의 손자들은 모두 x- 정렬 된 평면들을 가질 것이며, 루트의 증손자들은 모두 y- 정렬 된 평면들을 가질 것이다. 그래서 이해가능한 적당한 이미지를 찾기 힘들었다. 보통은 위의 2차원의 kdtree 이미지들이 많이 보이지만 이를 일반 트리처럼 표현하면 아래처럼 된다. 아래 좌표랑 위의 그래프랑 비교해보면 쉬울듯하다. 삽입 다른 검..