분류 전체보기
-
Stack, Queue, Deque ( 스택, 큐, 덱 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:20
✔️ Stack ( 스택 ) ◾ 먼저 들어간 데이터가 나중에 나오는 자료구조 ◾ LIFO ( Last-In, First-Out ) ◾ 후입선출 ( 後入先出 ) ⏱️ 시간복잡도 ◾ Push : O(1) ◾ Pop : O(1) 💾 소스 코드 더보기 #include #include #define STACK_SIZE 100 int stack[STACK_SIZE]; int top = -1; void push(int item) { if (top >= STACK_SIZE - 1) { printf("Stack is Full.\n"); return; } stack[++top] = item; } int pop() { if (top == -1) { printf("Stack is Empty.\n"); return 0; } r..
-
Array, Linked List ( 배열, 연결리스트 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:19
✔️Array ( 배열 ) ◾ 논리적인 순서와 물리적인 순서가 같기 때문에 데이터에 엑세스 하기쉽다. (인덱스로 쉽게 탐색 가능) ◾ 삽입, 삭제 연산 후에 연속적인 물리적 순서를 유지하기 위해 나머지 원소들을 이동 시키는 오버헤드가 발생한다. ⏱️ 시간복잡도 ◾ 탐색 : index를 통해 O(1)에 해당 원소로 접근 가능 ◾ 삽입 : 원소를 삽입하려면 배열내의 원소를을 shift 해줘야한다. O(n) 시간 ◾ 삭제 : 삭제한 원소보다 큰 index를 갖는 배열내의 원소들을 shift 해줘야한다. O(n) 시간 💾 소스 코드 더보기 #include int main() { int arr[10] = { 0,1,2,3,4,5,6,7,8,9 }; for (int i = 0; i < 10; i++) { print..
-
Big-O (시간 복잡도, 공간 복잡도)Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:17
✔️ 개요 ◾ 우리는 잘 동작하는 알고리즘은 물론이거니와 좋은 성능의 알고리즘을 설계 해야한다. 따라서 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. ◾ 알고리즘을 평가하는 요소는 두 가지 요소는 '속도'와 '메모리 사용량'이다. ◾ '속도'에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 '시간 복잡도(time complexity)라고 한다. ◾ '메모리 사용량'에 대한 분석결과를 가리켜 '공간 복잡도(space complexity)'라고 한다. ◾ 일반적으로는 알고리즘을 평가할 때 메모리 사용량보다 실행속도에 초점을 둔다. ◾ 우리는 '속도'를 측정하기 위해 알고리즘의 연산 횟수를 센다. 그리고 처리해야할 데이터의 수 n에 대한 연산횟수의 함수를 구성한다. ◾ Big-O는 '데이터 수..
-
Divide and Conquer ( 분할 정복 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 00:56
✔️ 분할 정복 ◾ 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산하는 알고리즘 기법 ◾ 분할 정복은 대개 아래와 같이 3가지의 구성요소를 가지고 있다. ◾ 문제를 더 작은 문제로 분할하는 과정(Divide) ◾ 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge) ◾ 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base Case) ✔️ Binary Seach(이분 탐색) ◾ 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘 ⏱️ 시간 복잡도 ◾ 탐색 : 리스트의 크기가 N일때 O(logN)의 시간이 걸린다. 💾 소스 코드 더보기 int binarySear..
-
Hash Table ( 해쉬 테이블 )Computer Science/Data Structure and Algorithm 2020. 4. 1. 13:31
✔️ 테이블 자료구조 ◾ 저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다. ◾ 키(key)가 존재하지 않는 값은 저장할 수 없다. ◾ 모든 키(key)는 중복되지 않는다. ◾ 테이블 자료구조는 사전구조 혹은 맵(map)이라 불리기도 한다. ✔️ 해쉬 함수와 충돌💥 ◾ 해쉬 함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다. ◾ 위 그림의 f(x)는 mod 100 연산을 하는 함수이다. 위 해쉬 함수를 사용하여 8자리의 키를 2자리의 키로 바꾸었다. ◾ 위 그림에서 보이듯이 서로 다른 두 개의 키가 해쉬 함수를 통과했는데, 그 결과가 03으로 동일하다. 이러한 상황을 가리켜 충돌(Collision)이라고 한다. ✔️ 좋은 해쉬 함수의 조건 ◾ 위 그림은 테이블의 메모리 ..
-
[Back End] Spring JDBCWeb Development/부스트코스 - Back-End(Java) 2020. 3. 30. 22:05
✔️ Spring JDBC ◾ JDBC를 이용해서 프로그래밍을 하게 되면 반복적인 코드가 많이 발생한다. ◾ 반복적인 코드는 개발자의 생산성을 떨어뜨리는 주된 원인이다. ◾ 반복적인 JDBC의 모든 저수준 세부사항을 Spring JDBC가 처리해준다. ◾ Spring JDBC를 사용하여 개발자는 필요한 부분만 개발하면 된다. ◾ Spring JDBC 외에 JPA, MyBatis 등의 기술들이 존재한다. 1️⃣ Spring JDBC 패키지 ◾ org.springframework.jdbc.core - JdbcTemplate 및 관련 Helper 객체 제공 ◾ org.springframework.jdbc.datasource - DataSource를 쉽게 접근하기 위한 유틸 클래스, 트랜젝션매니져 및 다양한 D..
-
[백준] 16234 인구이동Problem Solving/Baekjoon Online Judge 2020. 3. 26. 16:39
[문제이해] 1. NxN 크기의 땅이 있다. 각각의 땅에는 나라가 하나씩 존재한다. 2. r행 c열에 있는 나라는 map[r][c] 명이 살고 있다. 3. 모든 나라는 1x1 크기이고 모든 국경선은 정사각형 형태이다. 4. 인구이동이 시작된다. 인구 이동은 아래와 같은 방법으로 진행된다. 더 이상 인구 이동이 없을때까지 지속된다. 국경선을 공유하는 두 나라의 인구차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 하루동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 하루동안은 연합 이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수)/(연합을 이루고 있는 칸의 개수)가..
-
[백준] 17141 연구소 2Problem Solving/Baekjoon Online Judge 2020. 3. 26. 14:48
[문제이해] 1. NxN 크기의 연구소가 있다. 연구소는 빈칸(0), 벽(1), 바이러스가 위치할 수 있는 후보 공간(2)으로 표현된다. 2. 승원이는 연구소의 특정 위치에 바이러스를 M개 놓을 것이다. 3. M개가 놓여진후 바이러스는 상,하, 좌, 우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초의 시간이 걸린다. 4. 연구소의 상태와 M이 주어졌을 때 모든 연구소 빈 칸에 바이러스가 퍼지는 최소 시간을 구해라 5. 첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다. 6. 둘째 줄에 연구소의 상태가 주어진다. [설계] 1. 연구소에는 바이러스가 위치할 수 있는 후보 공간들이 존재한다. 2. 이 후보 공간들에서 M개를 뽑아서 바이러스를..