내 세상

Inserting Sort - N 크기의 배열 - 두 번째 index부터 시작해서, 앞 부분에 자신보다 작은 값이 있을 때까지 지나가는 값을 (현재 위치+1)로 이동시킴 - 시간복잡도 O(N^2) Counting Sort - N 크기의 배열, K 크기의 배열 (counting 용도) - 배열 내 각 값들의 개수를 counting → counting된 array를 누적해가며 index 계산 → N 크기 배열 순회하며 배치 - 시간복잡도 O(N+K) - reference) http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html Quick Sort - N 크기의 배열 - Divide and Conquer 방법 - 과정 (..

Topological Sort - DAG(Directed Acyclic Graph)를 활용해 노드들 사이에 선후관계를 중심으로 정렬하는 알고리즘 - DFS(Depth-First Search, 깊이우선탐색) 사용 → 결과를 역으로 나타냈을 때 위상정렬 결과와 동일함. - '그래프'를 정렬하는 것으로 정렬 기준은 '진입 차수(해당 노드로 들어오는 간선의 개수)의 비 내림차순' 순서 - 진입차수가 0인 노드들 제거 - 진입차수가 0이 아닌 노드들은 점점 0으로 수정되며 제거 # 참고 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/21/Topological/

DFS (Depth-First Search, 깊이 우선 탐색) - 방식 : - 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. - 역추적(Backtracking) 과정이 있어 Stack / Recursion을 사용 - 자기 자신을 호출하는 순환 알고리즘의 형태 - 사용 예시 - 미로 생성 - Cycle Detection - Topological Sorting - 시간복잡도 (정점 N, 간선 E) - 인접 리스트로 표현된 그래프 O(N+E) - 인접 행렬로 표현된 그래프 O(N^2) - 장점 - 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. - 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있음. → 임의로 지정한 ..

Image Retrieval - 이미지 검색 Person Re-Identification과 같은 유사 여부를 판단하기 위해선 'Similarity' 또는 'Distance'를 계산해야 한다. similarity/distance를 구하는 방법은 다양하지만, 그 중 Euclidean Distance와 Cosine Distance 등이 있다. 이러한 함수를 Metric이라 표현한다. Metric - 집합 내 한 쌍의 원소의 거리를 측정하는 함수 - metric f(x, y)는 항상 아래의 4가지 조건에 만족해야 한다. 1. Non-negativity : f(x, y) >= 0 2. Identity of Discernible : f(x, y) = 0 x = y 3. Symmetry : f(x, y) = f(y,..

Process Scheduling CPU를 사용하려고 하는 Process들 사이의 우선 순위를 관리하는 일 처리율/CPU 이용율 증가, 오버헤드/응답시간/반환시간/대기시간 최소화 장기 스케줄링 - 어떤 process를 커널에 등록할 것인가를 정함 중기 스케줄링 - 어떤 process에게 메모리를 할당할 것인가를 정함 단기 스케줄링 - 어떤 process에게 CPU를 할당할 것인가를 정함. Process state에 변화가 있을 때 작동함. Preemptive / Non-preemptive Preemptive, 선점형 Scheduler가 절대적인 권한으로 사용중인 CPU를 뺏을 수 있음. 빠른 응답시간을 요하는 대화식 시스템에 적합함. SRT(Shortest Reamining Time), RR(Round ..

Interrupt 실행중인 process가 예기치 못한 상황이 발생되어 더 이상 실행하기 어렵거나 먼저 처리해야할 우선순위가 높은 일이 생긴 경우 Interrupt가 발생하면 실행중이던 process가 CPU의 사용을 멈추고 Interrupt 처리가 된 후에 다시 CPU 점유 Interrupt Process Routine(인터럽트 처리 루틴, IPR) Interrupt 발생 원인을 찾아 ISR 호출 Interrupt 발생 시점부터 Interrupt 처리가 종료되는 시점까지를 말함 Interrupt Service Routine(인터럽트 서비스 루틴, ISR) Interrupt에 대한 실제 처리를 담당 Interrupt 처리를 시작하는 시점부터 Interrupt 처리가 종료되는 시점까지를 말함. Proces..

Process? - 보조기억장치에 있던 프로그램이 주기억장치에 적재되어 실행 중일때, 이를 '프로세스'라고 한다. 프로세스 상태 Create - Process가 생성되는 단계 주기억장치 적재 여부 및 자원 확보 여부 Ready Process 생성 후 주기억 장치에 적재되고, 실행하는데 필요한 자원을 모두 얻은 상태 Asleep 주기억장치에 적재되었지만, 필요한 자원을 얻지 못한 상태 Suspended Ready 주기억장치에 적재되지 않았지만, 필요한 자원을 얻은 상태 Suspended Blocked 주기억장치에 적재되지 않았고, 필요한 자원도 얻지 못한 상태 Running - Process가 CPU를 점유하여 실행중인 상태 Terminated - Process가 종료된는 상태 상태 전이 Dispatch ..

Graph는 기본적인 형태이다. 방향의 여부, 가중치의 여부, 연결의 여부, 순환의 여부 등에 따라서 이름이 변경되고 결정된다. 예를 들어, Minimum Spanning Tree의 의미를 하나씩 분석해보자. Tree? 순환(Cycle)이 없어야 함. 1개의 Root Node를 갖는다. Spanning Tree? 순환(Cycle)이 없어야 함. 1개의 Root Node를 갖는다. Spanning : (다리를) 놓다, ~의 양 끝을 연결하다 '모든 정점(노드)를 잇는다'로 해석할 수 있음. Minimum Spanning Tree? 순환(Cycle)이 없어야 함. 1개의 Root Node를 갖는다. Spanning : (다리를) 놓다, ~의 양 끝을 연결하다 '모든 정점(노드)를 잇는다'로 해석할 수 있음...

1. Stack Last Input First Out, LIFO, 후입선출 가장 나중에 저장된(push) data가 가장 먼저 인출(pop)되는 구조 용도 DFS(Depth First Search, 깊이우선탐색) 함수 호출의 순서 제어 Interrupt 처리 수식 계산 2. Queue First Input First Out, FIFO, 선입선출 가장 먼저 저장된(push) data가 가장 먼저 인출(pop)되는 구조 용도 BFS(Breadth First Search, 너비우선탐색) 운영체제 작업 스케줄링 대기행렬 처리

백준 13460번 구슬 탈출 2 https://www.acmicpc.net/problem/13460 문제 풀이 해당 문제는 bfs 느낌보다 dfs 느낌으로 접근하여 진행함 !!!!!!!! 1. 보드 - 크기 NxM (세로 N, 가로 M) - 가장 바깥 행과 열은 막혀져 있음. - 구멍이 하나 있음. - 입력 데이터 "O" - 상, 하, 좌, 우 4가지 방향으로 기울이기 가능함. (최대 10회) 2. 빨간 구슬 - 구멍에 들어가야 함. - 입력 데이터 "R" 3. 파란 구슬 - 절대 구멍에 들어가선 안됨. - 입력 데이터 "B" 주의 사항 1. 보드를 기울이면 파란 구슬과 빨간 구슬이 동시에 움직임 → 파란 구슬을 끝까지 이동시킨 후 빨간 구슬을 끝까지 이동시킨다 (X) → 파란 구슬과 빨간 구슬을 동시에..

https://www.acmicpc.net/problem/14503 문제 풀이 복잡한 설명이지만 굉장히 간단하게 생각해야한다. 후진의 경우도 방향을 그대로 살려서 각 방향에 따라 진행하는 방향의 반대로 가기 때문에 현재 좌표에서 빼줌으로써 해결하면 좋음 :) 문제에서 유일하게(?) 조심해야할 점은 일반적으로 "동,서,남,북" 이라고 말하고 쓰는데, "북, 동, 남, 서"를 기준으로 문제를 해석해나가야함 ! 시뮬레이션 부분에서 예전보다 많이 어려움을 느끼는 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

https://www.acmicpc.net/problem/2146 문제 풀이 초기에는 특정 섬에서 다른 섬까지 이동하는 경로를 dfs로 구현했음. 하지만 굉장히 바보같이 무식한 생각이라는 걸 뒤늦게 깨달은 후 좌표만으로 계산하여 문제를 해결함. 문제를 보면 최단거리를 찾는 문제로 착각하기 쉬운데, 이러한 트릭을 잘 해결하는 머리를 가지도록 해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 7..

kill $(ps aux | grep '[찾을 내용]' | awk '{print $2}') ps aux- 전체 프로세스의 목록을 보여줌 ps aux | grep '[찾을 내용]'- 전체 프로세스에서 grep 명령어로 원하는 키워드가 있는 프로세스를 찾음. ps aux | grep '[찾을 내용]' | awk '{print $2}'- 전체 프로세스에서 grep 명령어로 원하는 키워드가 있는 프로세스를 찾은 후 2번째 열을 뽑아냄.

백준 14890번 경사로https://www.acmicpc.net/problem/14890 문제 풀이- 경사로 조건 1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸의 높이가 동일해야함. 2. 낮은 칸과 높은 칸의 차이는 오직 1이어야 함. - 경사로를 놓는 2가지 경우 1. 이전 칸이 현재 칸보다 1 낮은 경우 (이전 칸 높이 현재 칸 높이) - 현재 칸에서 뒤의 칸까지 총 L개가 높이가 동일한지 확인해야함...

백준 15683번 감시https://www.acmicpc.net/problem/15683 총 5종류의 CCTV가 있는데, 각 CCTV 별로 지켜볼 수 있는 방향이 정해져 있음. - 1번 : 상, 하, 좌, 우 중 1방향 - 2번 : (상, 하) or (좌, 우) 중 하나 - 3번 : 상, 하, 좌, 우 중 2 방향 (대신, 선택된 두 방향은 인접해야함) - 4번 : 상, 하, 좌, 우 중 3방향 - 5번 : 상, 하, 좌, 우 모든 방향 그 외에 6번은 '벽'이고, cctv 영상은 벽까지만 볼 수 있으며 벽을 건너서는 볼 수 없음.이러한 CCTV 별 특성으로 인하여 각 별개로 처리를 해주어야 함. 문제 풀이1. 초기에 데이터를 입력 받음과 동시에 각 cctv를 배열에 저장함. 이때, 5번 cctv는 별도..

백준 14889번 스타트와 링크https://www.acmicpc.net/problem/14889 팀원들 한명씩 돌면서 start팀으로 사용할까 말까를 구현해서 코딩하면 됨.확인은 안해봤지만, 아래와 같은 경우는 똑같은 계산을 2번 하게 되는 문제가 생길 수 있음 ex) 4명의 사원(1~4) start팀(1,2) link팀 (3,4) start팀(3,4) link팀 (1,2) 그래서 미리 전체 조합수(totalCase)를 계산해서 그 절반까지만 계산을 하도록 하였음. (Line 41)어차피 순차적으로 앞에서부터 한명씩 고르기 때문에 총 진행에 절반만큼만 하면 중복되는 경우는 하지 않기 때문입니다. 참 쉽쥬? 123456789101112131415161718192021222324252627282930313..