Priority Queue 우선순위 큐일반적인 큐의 구조(FIFO)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야함Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 우선순위가 높은 객체를 추출 해줌.Heap을 이용하여 구현하는 것이 일반적임(자바)특징높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한..

최단 경로말 그대로 가장 짧은 경로를 찾는 알고리즘 종류다익스트라 알고리즘플로이드 워셜 알고리즘벨만 포드 알고리즘다익스트라 최단 경로 알고리즘그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘'음의 간선'이 없을 때 정상적으로 동작일종의 그리디 알고리즘 -> 매번 가장 비용이 적은 노드를 선택하는 과정을 반복각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 계속 갱신간단한 구현 1각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인시간 복잡도 O( V²) - V: 노드 수import java...

1.4.1 논리 메모리와 물리 메모리논리 메모리 영역(또는 가상 메모리 영역)프로세스가 보는 메모리 영역물리 메모리 영역실제로 사용되는 메모리 영역(RAM)CPU가 프로세스를 실행하며 보는 주소 값을 논리 주소 또는 가상 주소실제 메모리에서 사용되는 주소는 물리 주소-> 값이 다르므로 CPU가 프로세스를 실행할 때 논리 주소를 물리 주소로 변환해야 함-> 메모리 관리 장치(MMU, memory management unit)가 함CPU에 위치CPU에서 메모리에 접근하기 전에 MMU에 거쳐 논리 주소에 해당하는 물리 주소를 얻는다.보호해야하는 메모리 영역에 대한 접근을 제한해 메모리를 보호1.4.2 연속 메모리 할당연속 메모리 할당멀티 프로세스 환경에서 여러 프로세스를 메모리에 연속적으로 로드하는 방법고정 ..

다이나믹 프로그래밍DP(Dynamic Programming)중복되는 연산을 줄이는 방식문제를 작은 하위 문제로 나누어 해결한 결과를 저장해 두었다가, 동일한 하위 문제가 다시 나타날 때 이를 재사용하는 방식다이나믹 프로그래밍의 기본 원리중복된 하위 문제:문제를 작은 하위 문제로 나누었을 때, 동일한 하위 문제가 여러 번 반복해서 나타나는 경우.예를 들어, 피보나치 수열 계산에서는 F(n) = F(n-1) + F(n-2)와 같은 형태로, 동일한 계산이 반복된다.최적 부분 구조:문제의 최적해가 하위 문제들의 최적해로 구성될 수 있는 경우.예를 들어, 최단 경로 문제에서는 전체 경로의 최적해가 부분 경로의 최적해들로 구성된다.다이나믹 프로그래밍의 두 가지 접근법1. 탑다운(Top-Down) 접근법 (메모이제이..

이진 탐색순차 탐색리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법순차 탐색 자바 코드 구현// 순차 탐색 소스코드 구현public static int sequantialSearch(int n, String target, String[] arr) { // 각 원소를 하나씩 확인하며 for (int i = 0; i  이진 탐색반으로 쪼개면서 탐색하기배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘배열이 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음시작점, 끝점, 중간점을 사용하여 탐색찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교해서 원하는 데이터를 찾음재귀를 활용한 이진 탐색// 이진 탐색 소스코드 구현(재귀 함수)pu..

1.1.1 운영체제(OS: Operating System)란하드웨어 위에 설치되어 하드웨어 계층과 다른 소프트웨어 계층을 연결하는 소프트웨어 계층컴퓨터 시스템의 자원 관리사용자가 컴퓨터를 사용할 수 있는 환경을 제공Ex) 윈도우, 맥OS, 리눅스, 유닉스1.1.2 운영체제의 목적처리 능력 향상 - 자원 관리를 통해 일정 시간 내에 시스템이 처리하는 일의 양을 향상시킴.반환 시간 단축 - 사용자가 시스템에 요청한 작업을 완료할 때까지 소요되는 시간을 단축시킴.사용 가능도 향상 - 시스템 자원을 얼마나 빨리 제공할 수 있는가를 의미. 사용자가 컴퓨터를 사용해야할 때 자원을 즉시 사용할 수 있게 함.신뢰도 향상 - 입력 값에 대한 정확한 결과 값을 줄 수 있도록 신뢰도를 향상해야 함.1.1.3 CPU와 메모리..

정렬1. 선택정렬가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬연산 횟수는 N+(N-1)+(N-2)+ … +2 = (N² + N)/2 번시간 복잡도는 O(N²)이므로 알고리즘 문제 풀이에 사용하기에는 느림2. 삽입정렬첫 번째 데이터가 정렬되어 있다고 가정하고 두 번째 데이터부터 탐색하여 첫번째 데이터보다 작으면 앞, 크면 뒤에 삽입한다.삽입 정렬은 데이터가 거의 정렬 되어 있을 때 훨씬 효율적삽입 정렬의 시간 복잡도는 시간 복잡도는 O(N²)지만 데이터가 거의 정렬되었을 때는 빠르게 동작하여 최선의 경우 O(N)의 시간 복잡도를 가짐3. 퀵정렬피벗을 선정하여 피벗보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 분..

[자료구조] Stack, Queue 그리고 DequeStack, Queue, Deque스택(Stack)박스 쌓기에 비유할 수 있다.선입후출(FILO) 구조 또는 후입선출 구조스택의 메서드큐대기 줄에 비유할 수 있다.선입선출(FIFO) 구조큐의 매서드 간단한 스택과 큐 구현publjaemin0604.tistory.com이전 글에서 공부한 스택, 큐, Deque를 활용하여 DFS/BFS를 알아보고자한다. 들어가기전에.... 인접행렬 vs 인접리스트인접행렬2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 장점:두 정점 사이에 간선이 존재하는지 O(1) 시간에 확인할 수 있다.구현이 단순하고 직관적이다.단점:공간 복잡도가 O(V^2)이다. 따라서 정점의 수가 많아지면 비효율적이다.간선의 수가 적은 그래프(희..

Stack, Queue, Deque스택(Stack)박스 쌓기에 비유할 수 있다.선입후출(FILO) 구조 또는 후입선출 구조스택의 메서드큐대기 줄에 비유할 수 있다.선입선출(FIFO) 구조큐의 매서드 간단한 스택과 큐 구현public static void main(String[] args) { Stack st = new Stack(); Queue q = new LinkedList(); st.push("0"); st.push("1"); st.push("2"); q.offer("0"); q.offer("1"); q.offer("2"); while(!st.isEmpty()) { System.out.print(st.pop()); } whi..

구현- 떠올린 아이디어를 코드로 구현하기 1. 완전 탐색- 모든 경우의 수를 주저 없이 계산하는 해결 방법 2. 시뮬레이션- 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법 예시 - 상하좌우 문제좌표가 주어지고 이동방향이 주어졌을 때 도착할 지점의 좌표를 출력하는 문제static int n;static char[] plans; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); StringTokenizer st = new St..