맨들맨들 돌덩이

티스토리 생일 : 2020.11.18. 모든 문의 : highcw@naver.com

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. REST 의 등장 배경 HTTP는 GET, POST, PUT, DELETE 등의 다양한 HTTP 메서드를 지원한다. -실제로는 서버가 각 메서드의 기본 설명을 따르지 않더라도 프로그램을 개발할 수 있음. -하지만 저마다 다른 방식으로 개발하면 문제가 될 수 있어서 기준이 되는 아키텍처가 필요하다. REST(Representational State Transfer)는 '각 자원에 대해 자원의 상태에 대한 정보를 주고받는 개발 방식'을 의미한다. REST의 구성 요소 1) 자원(Resource) : URI 이용 2) 행위(Verb) : HTTP메서드 이용 3) 표현(Representations) : 페이로드 이용. 클라이언트 : 사용자(자원..

2022. 4. 24.

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 벨만 포드 알고리즘 음수 간선이 포함된 상황에서의 최단 거리 문제. BOJ 의 '타임머신' 문제 https://acmicpc.net/problem/11657 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C 벨만 포드 최단 경로 알고리즘 음수 간선에 대해 최단 경로 문제는 다음과 같이 분류할 수 있음. 1) 모든 간선이 양수인 경우 2) 음수 간선이 있는 경우 2-1) 음수 간선 순환이 없..

2022. 4. 24.

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 바이너리 인덱스 트리 (BIT, Binary Indexed Tree) 데이터 업데이트가 가능한 상황에서의 구간 합 (Interval Sum) 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면12가 될 것이다. 바이너리 인덱스 트리 사용 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있는 자료구조를 의미. == 펜윅 트리(..

2022. 4. 24.

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 최소 공통 조상 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 최소 공통 조상(LCA) 문제는 '두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제' 기본적인 최소 공통 조상 알고리즘 최소 공통 조상 찾기 알고리즘 원리 1) 모든 노드에 대한 깊이를 계산함. 2) 최소 공통 조상을 찾을 두 노드를 확인함. 2-1) 먼저 두 노드의 깊이가 동일하도록 거슬러 올라갑니다. 2-2) 이후에 부모가 같아질 때까지 반복..

2022. 4. 24.

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 이진 탐색 트리 트리란 트리는 가계도와 같은 "계층적인 구조"를 표현할 때 사용할 수 있는 자료구조. [트리 관련 용어] 루트 노드 : 부모가 없는 최상위 노드 단말 노드 : 자식이 없는 노드 크기 : 트리에 포함된 모든 노드의 개수 깊이 : 루트 노드부터의 거리 높이 : 깊이 중 최댓값 차수 : 각 노드의 (자식 방향) 간선 개수 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개임. 이진 탐색 트리 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종임. 이진 탐색 트리의 특징 : 왼쪽 자식 노드

2022. 4. 22.

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 우선순위 큐 우선순위 큐는 '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조'이다. 우선순위 큐는 데이터를 '우선순위에 따라' 처리하고 싶을 때 사용한다. 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우 자료구조 추출데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입된 데이터 (비교적 공평한 자료구조) 우선순위 큐 우선순위가 높은 데이터 우선순위 큐를 구현하는 방법은 다양함. 1) 단순히 '리스트를 이용한 구현' 2) '힙을 이용한 구현' 데이터의 개수가 N개 일 때, 구현 방식에 따라 시간 복잡도를 비교한 내용은 다음과 같다. 우선순위 큐 구현 방식 삽입시간 삭제 시간 리스트 O(1)..

2022. 4. 22.

개발/이코테

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 서버와 클라이언트 클라이언트가 요청을 보내면 서버가 응답을 함. 웹 클라이언트 ㅡㅡ(1)요청==>ㅡㅡㅡ 웹서버

2022. 4. 22.