👾

목차 Docker란? VM(가상 머신) vs Docker Image(이미지) Docker Architecture Docker란? 컨테이너 기반의 오픈소스 가상화 플랫폼 사람들이 일반적으로 생각하는 화물 수송용 박스(컨테이너)의 개념을 SW에 적용 다양한 프로그램, 실행환경을 컨테이너로 추상화하여 동일한 인터페이스 제공 프로그램의 배포 및 관리를 단순화 VM(Virtual Machine) vs Docker VM Container Host OS 위에 Guest OS 전체를 가상화 프로세스를 격리 메모리 과도 점유(OS 코드 때문에) 훨씬 적은 메모리 점유 다수 VM 실행하면 급격한 성능 저하 container engine을 사용하여 성능 저하 적음 Scale up(성능 향상) 어려움 Scale up(성능 향..

목차 BFS의 개념 BFS의 장단점 BFS의 시간 복잡도 BFS의 구현 BFS(너비 우선 탐색)이란? BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄 BFS의 동작 과정 탐색 시작 정점을 큐에 삽입하고 방문 처리를 합니다. 큐에서 정점을 꺼낸 뒤에 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리를 합니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. BFS의 장단점 장점 시작 정점에서 목표 정점까지의 최단 길이 경로를 보장한다. 단점 경로가 매우 길 경우, 탐색 가지가 급격히 증가함에 따라 많은 기억 공..

목차 DFS의 개념 DFS의 장단점 DFS의 시간 복잡도 DFS의 구현 DFS(깊이 우선 탐색)이란? DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수를 이용함 DFS의 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 존재하면 그 노드를 스택에 넣고 방문 처리를 합니다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼냅니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. DFS의 장단점 장점 현재 경로 상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 답을 빨리..

문제 링크: www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 설명 적록색약인 사람과 아닌 사람의 matrix를 따로 만들어서 생각합니다. 저는 적록색약의 matrix는 G를 모두 R로 바꿔서 문제를 풀었습니다. 각각의 matrix를 BFS를 이용해 상, 하, 좌, 우로 연결된 같은 색을 모두 탐색합니다. 이때 상, 하, 좌, 우 인덱스를 편하게 계산하기 위해 dx, dy를 정의해서 사용했습니다. 방문한 matrix의 원소는 0을 대입해서 방문 처..

문제 링크: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 단순히 DFS와 BFS를 수행하면 됩니다. 저는 (N + 1) X (N + 1) 크기의 matrix를 이용해 정점 간의 간선을 표시했습니다. 또한 dfs를 할 땐 방문한 노드를 1로 표현하고 bfs를 할 땐 0으로 표현해서 visited를 따로 초기화할 필요 없이 바로 사용할 수 있도록 했습니다. 소스코드 def dfs(v): # 방문 노드 1로 표현..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 설명 모든 경우의 수를 DFS(깊이 우선 탐색)으로 확인해서 타겟 넘버를 만드는 경우를 셌습니다. 소스코드 answer = 0 def dfs(idx, numbers, total_sum, target): global answer n = len(numbers) # 마지막 원소까지 계산했다면 return if ..

문제 링크: www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 설명 면접자들을 서류 점수가 높은 순서대로 정렬한 뒤, 면접 점수에 대해 생각합니다. 서류 점수가 1등인 사람은 무조건 뽑히고, 2등인 사람은 1등보다 면접 순위가 높으면 뽑힙니다. 3등은 1, 2등보다 면접 순위가 높이면 뽑히고 나머지 사람들도 비슷하게 계산합니다. 따라서 서류 순위가 높은 순서대로 면접자를 정렬하고, 각 면접자들의 면접 순위가 면접 커트라인보다 더 높은..

문제 링크: www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 설명 만약 n이 1이나 3이 주어진다면, 2원과 5원으로는 거슬러 줄 수 없으므로 -1을 반환합니다. 나머지는 최소 개수의 동전으로 거슬러줘야 하므로 5원을 먼저 거슬러주는 방법을 선택했습니다. n을 5로 나눴을 때 나머지는 다음과 같이 5가지입니다. (x: n을 5로 나눈 몫) 나머지가 0일 경우 5원으로만 거슬러 줄 수 있으므로 answer = x 나머지가 1일 경우 5원을 하나 빼고 2원 3개를 추가해야 합니다. => 5x + 1 = 5(x - 1) + (2 * 3) 따라서 anwer = (x - 1) + ..

목차 Greedy 알고리즘 개념 Greedy 알고리즘 예시 Greedy 알고리즘 다른 문제들 그리디(Greedy) 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법 즉, 전후 결정에 관계없이 당시 "가장 최고"라고 생각되는 것을 선택해서 최적의 해를 구하는 방법 대표적인 예시로 MST(최소신장트리) 알고리즘, 다익스트라(Dijkstra) 알고리즘, 거스름돈 문제가 있다 그리디 알고리즘 쉬운 예시 점원이 계산을 마치고 거스름돈을 돌려주는 상황을 생각해봅시다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 충분히 많이 존재한다고 가정합니다. 손님에게 N원을 거슬러 줘야 할 때, 최소 개의 동전으로 거스름 돈을 줄 방법을 구하세요. 단, 거슬러 줘야 할 돈 N은 항상..

1. 윈도우에서 EC2 인스턴스 접속 방법 정리 PuTTY 설치 PuTTY key Gen을 이용해 pem를 ppk로 변환 변환된 키를 통해 인스턴스에 ssh 접속 2. PuTTY로 EC2 인스턴스 접속하기 1) PuTTY 다운로드 PuTTY 사이트(www.chiark.greenend.org.uk/~sgtatham/putty/latest.html)에 접속해서 putty-64bit-0.74-installer.msi 를 다운로드합니다. 2) PuTTY 설치하기 디폴트 값들을 유지하고 Next를 클릭한 뒤, "Install"을 클릭해서 설치합니다. 3) PuTTYgen 실행 AWS에서 다운 받은 키는 .pem 형식인데, 이를 PuTTY에서 이용하기 위해서는 .ppk형식으로 변환해야 합니다. PuTTYgen을 이..