seoarc의 등록된 링크

 seoarc로 등록된 티스토리 포스트 수는 43건입니다.

[Algorithm] 플로이드-워셜(Floyd-Warshall) [내부링크]

플로이드-워셜(Floyd-Warshall)? 플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다. 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다. 구현 설명 플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와..

[Baekjoon] 1654: 랜선 자르기 [내부링크]

문제 다양한 길이를 가진 n개의 랜선을 가지고 일정한 길이를 가진 k개의 랜선을 만들 때 만들 수 있는 최대 길이를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q1654 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk..

[Algorithm] 상계/하계(Upper Bound/Lower Bound) [내부링크]

상계/하계(Upper Bound/Lower Bound)? Lower Bound와 Upper Bound는 이진 탐색을 기반으로 하여 경곗값을 찾는 알고리즘이다. 이진 탐색을 기반으로 하기 때문에 당연히 데이터가 정렬되어 있어야 한다. 값을 찾을 때, 원하는 값이 없을 때 못찾았다는 신호(-1, false 등)를 반환하는 일반적인 이진 탐색과 달리 Upper Bound와 Lower Bound를 이용하면 찾고자 하는 값 또는 그 값의 초과값이 처음 나타나는 위치를 찾을 수 있다. 때문에 주로 특정 값을 어느 위치에 삽입해야 하는지 탐색할 때 많이 사용한다. 상계 (Upper Bound) Upper Bound는 찾고자 하는 값(target)보다 큰 값의 처음 위치를 반환한다. 구현 public class Upp..

[Algorithm] 이진 탐색(Binary Search) [내부링크]

이진 탐색(Binary Search)? 이진 탐색이란 데이터가 정렬되어 있는 상태에서 탐색 범위를 줄여나가며 특정한 값을 탐색하는 알고리즘으로, 탐색할 때마다 탐색 범위가 반으로 줄어들기 때문에 속도가 빠르다는 장점이 있다. 구현 코드 public class BinarySearch { public static void main(String[] args) { int[] array = {1, 3, 4, 6, 7, 9, 10, 11, 14, 16, 17, 20}; int target = 16; int left = 0; int right = array.length - 1; while (left right가 되므로 종료한다) 시간 복잡도 선형 탐색의 경우 O(n)이지만 이진 탐색의 경우 O(log n)이므로 대부..

[Java] Integer.valueOf(127) == Integer.valueOf(127)은 true? [내부링크]

Integer.valueOf(127) == Integer.valueOf(127)은 true? Integer.valueOf(127) == Integer.valueOf(127)은 true가 출력된다고 한다. 뭔가 이상하다. 배운대로라면 Integer는 클래스, 즉 참조 타입이기 때문에 다른 객체가 생성되어 false가 떠야 맞는 것 같은데 그렇지가 않다. 그럼 다른 객체로 생성이 안된다는 얘기일까? 한 번 살펴보자. 다음 코드의 실행 결과를 한 번 예상해보자. public class IntegerCacheCheck { public static void main(String[] args) { System.out.println(Integer.valueOf(128) == Integer.valueOf(128)); ..

[Baekjoon] 7662: 이중 우선순위 큐 [내부링크]

문제 삽입 연산과 삽입된 값들 중에 최대값과 최소값 삭제 연산을 통해 최종적으로 남아있는 최대값과 최소값을 출력하는 문제이다. 문제 제목 자체가 이중 우선순위 큐로 힌트를 주기 때문에, 좀 더 풀이가 쉽지 않았나 생각한다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q7662 { private static BufferedReader br; private static StringBuilder sb; public static void main(String[] args) throws IOException { br =..

[Algorithm] 위상 정렬(Topological Sort) [내부링크]

위상 정렬(Topological Sort)? 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘으로, 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다. 실생활을 예로 들면, 인터넷 검색을 하기 위해선 다음과 같은 순서로 행동해야한다. 컴퓨터 전원 키기 -> 브라우저 키기 -> 검색 엔진 포털 진입 -> 검색 위 순서가 바뀐다면 검색을 할 수 없을 것이다. 위상 정렬은 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다. 여기서 주의할 점은 E가 수행되기 위해선 B와 D가 모두 수행되어야 한다는 점이다. 비순환 방향 그래프 (DAG: Di..

[Baekjoon] 1167: 트리의 지름 [내부링크]

문제 트리에서 두 점 사이의 거리가 가장 긴 길이를 트리의 지름이라 하는데 트리의 지름을 구하는 문제이다 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1167 { private static List tree; private static boolean[] visited; private static int maxVertex; private static int max; public static void main(String[] args) throws IOException { BufferedReader br = new..

[Baekjoon] 2533: 사회망 서비스(SNS) [내부링크]

문제 문제가 조금 복잡하다. 간단히 설명하자면, 주변의 모든 친구가 얼리어답터이면 자신은 얼리어답터가 될 필요가 없는데, 이때 최소 얼리어답터의 수를 구하는 것이다. 풀이 대표 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Q2533 { private static List graph; private static int[][] dp; private static boolean[] visited; public static void main(String[] args) thro..

[Baekjoon] 1655: 가운데를 말해요 [내부링크]

문제 수가 순차적으로 주어지면 입력된 수 들 중에서 중간값을 계속 출력해나가는 문제이다 -> 짝수개 일 시 더 작은 값 출력 풀이 내 풀이 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuild..

[Baekjoon] 2170: 선 긋기 [내부링크]

문제 선을 정해진 횟수만큼 긋고 최종 길이를 구하는 단순 스위핑 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; public class Q2170 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer..

[Baekjoon] 9935: 문자열 폭발 [내부링크]

문제 대상 문자열과 삭제할 문자열이 주어지면, 대상 문자열에서 삭제할 문자열이 더 이상 없을 때까지 계속 삭제해나가는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main9935 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); // 대상 문자열 String deleteStr = br.readLin..

[Baekjoon] 16934: 게임 닉네임 [내부링크]

문제 닉네임의 접두사를 계속 체크하여 중복없이 별칭을 만들도록 하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Main16934 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..

[Algorithm] 프림 알고리즘(Prim's algorithm) [내부링크]

프림 알고리즘(Prim's algorithm)? 프림 알고리즘은 임의의 정점부터 시작하여 해당 정점에 연결된 가장 작은 가중치의 간선을 선택하며 확장해나가서 최소 신장 트리를 만드는 알고리즘이다. 구현 탐색을 시작할 임의의 정점을 하나 선택한다. 선택한 정점과 인접하는 정점 중 최소 비용의 간선을 갖는 정점을 선택한다. 모든 정점이 선택될 때 까지(n-1 개의 간선을 가질 때 까지) 반복한다. 동작 과정 코드 다음 코드는 baekjoon: 1197 - 최소 스패닝 트리를 기준으로 작성하였다. 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B..

[Baekjoon] 1138: 한 줄로 서기 [내부링크]

문제 각 index 번째에 있는 사람들의 왼쪽에 자기보다 큰 사람이 몇 명 있는지 주어지면, 각 사람들의 번호를 위치 순서로 출력하는 문제이다. 풀이 내 풀이 public class Q1138 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); List numbers = new ArrayList(); int n = Integer.parseInt(br.readLine()); String[] leftCounts = br.readLine().split(" "); for (int i = n - 1; i >= 0; i--) ..

[Algorithm] 다익스트라(Dijkstra) [내부링크]

다익스트라(Dijkstra)? 다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다. 특징 그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를..

[Algorithm] 유니온-파인드(Union-Find) [내부링크]

유니온-파인드(Union-Find)? Union-Find는 여러 개의 노드가 존재할 때, 어떤 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 방법 같은 그래프에 속하는지 어떻게 판별할까? 다음 그림을 보고 쉽게 이해하자 먼저 8개의 노드가 위와 같이 있다고 가정한다. 각 노드는 자기 자신을 가리키며 이는 자기 자신이 곧 루트 노드임을 의미한다. 여기서 5와 2가 연결되었다고 해보자. 그럼 다음과 같이 표현할 수 있다. 5번 노드에 2번 노드를 가리키는 값 2가 들어간다. 일반적으로 합칠 때는 더 작은쪽으로 합치며 이를 Union이라 한다. 그 다음 2와 1이 연결되었다고 해보자. 2번 노드는 1번 노드를 가리키며 이를 의미하는 값 1이 들어간다. 그럼 여기서 5번과 1번이 같은 그래프에 속하는..

[Data Structure] 4. 최소 신장 트리(MST, Minimum Spanning Tree) [내부링크]

신장 트리(Spanning Tree)? Spanning Tree는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 최소 신장 트리(MST, Minimum Spanning Tre..

[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm) [내부링크]

크루스칼 알고리즘 (Kruskal Algorithm)? 크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 알고리즘으로, 탐욕적인(greedy) 방법을 통해 구현할 수 있다. greedy? 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다. 크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. 구현 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의..

[Algorithm] 백트래킹(BackTracking) [내부링크]

백트래킹? 백트래킹은 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS는 큐의 크기가 매우 커질 수 있고 속도도 차이가 없기 때문에 경우의 수 구하기는 일반적으로 DFS가 편리하다. 출처: 나무위키 DFS & 백트래킹 백트래킹은 DFS를 사..

[Algorithm] 비트마스킹(bitmasking) [내부링크]

비트마스킹? 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비트 마스크를 이용하면 더 빠른 수행시간, 간결한 코드, 적은 메모리 사용의 효과를 얻을 수 있다. 비트 연산자 a & b: AND 연산 a | b: OR 연산 a ^ b: XOR 연산 ~a: NOT 연산 a > b: a를 b비트 만큼 오른쪽으로 시프트 집합 표현 비트마스크를 이용하면 집합을 쉽게 표현할 수 있다. 원소 추가 현재 상태 cur이 있을 때, p번째에 원소를 추가한다고 하면 다음과 같다 cur = cur | (1

[Java] abstract class vs interface [내부링크]

abstract class에 대해 공부하다가 interface와의 차이점이 궁금하여 작성하였다. 추상 클래스(Abstract class) vs 인터페이스(Interface) 추상 클래스(Abstract class) 먼저 추상 클래스(abstract class)는 클래스 내에 추상 메서드가 하나 이상 포함된 클래스를 말한다. 클래스 안에 메서드가 하나 이상 있다면 그 클래스 앞에는 반드시 abstract 클래스명으로 표기되어야 하며 abstract와 final 키워드를 동시에 표기할 수 없다. 일반 클래스에서 추상 클래스를 상속을 받는다면 추상메서드가 있을 경우 모두 구현해주어야 한다. 인터페이스(Interface) 반면 인터페이스(interface)는 모든 메서드가 추상 메서드인 경우이다. 간단히 생각하..

[Java] stream vs for [내부링크]

이전에 한번 확인했던 내용이지만, 자바를 통해 프리코스를 수행하던 도중 다시 또 궁금증이 생기고 기억이 흐릿하여 작성해본다. 아마 자바를 공부해본 사람이라면 다 고민해봤을 내용이다. ※ 해당 내용은 우아한Tech 유튜브 채널의 "[10분 테코톡] 크리스, 로마의 stream vs for" 내용을 참고하였다 해당 영상의 자세한 내용은 https://www.youtube.com/watch?v=by8hb75i9X4 이 링크를 통해 보면된다. 코드 먼저 다음 코드는 Java 1부터 지원한 기본적인 for문이다. public static void main(String[] args) { List list = List.of(1, 2, 3, 4, 5); for (int i = 0; i < list.size(); i++..

[Baekjoon] 17298: 오큰수 [내부링크]

문제 각 원소 A_i에 대해 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 구하는 문제이다. (없을 경우 -1) 예를들어 3 5 2 7 이라는 수열이 있으면, 3의 오큰수는 5, 5의 오큰수는 7, 2의 오큰수는 7, 7의 오큰수는 없으므로 5 7 7 -1 이라는 결과가 나오게 된다. 풀이 내 풀이 import sys input = sys.stdin.readline n = input() arr = list(map(int, input().split())) result = [0] * len(arr) stack = [0] for i in range(1, len(arr)): while stack and arr[i] > arr[stack[-1]]: result[stack.pop()] = arr..

[Baekjoon] 3190: 뱀 [내부링크]

문제 어릴 때 많이 했던 뱀 게임을 구현하는 문제이다. 풀이 내 풀이 import sys from collections import deque n = int(sys.stdin.readline()) apple_count = int(sys.stdin.readline()) board = [[0 for i in range(n)] for i in range(n)] board[0][0] = 1 for i in range(apple_count): r, c = map(int, sys.stdin.readline().split()) board[r-1][c-1] = 2 directs = deque([]) for i in range(int(sys.stdin.readline())): s, d = sys.stdin.readlin..

[Baekjoon] 11054: 가장 긴 바이토닉 부분 수열 [내부링크]

문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * n for i, v in enumerate(seq): for j in range(i-1, -1, -1): if seq[j] < v: dp[i] = max(dp[i], dp[j]+1) for i, v in enumerate(seq): for j in range(i-1, -1, -1): if seq[j] > v: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 이 문제는 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제에서 변형된 문제이다. 아이디어는 11053번 문제..

[Baekjoon] 1912: 연속합 [내부링크]

문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [0] * n dp[0] = arr[0] for i in range(1, len(arr)): dp[i] = max(dp[i-1] + arr[i], arr[i]) print(max(dp)) 이 문제는 단순하게 생각하여 현재까지 합들보다 현재 값이 크면 시작점을 현재 인덱스로 바꾸면 해결되는 문제이다. 이 문제에선 다음을 고려하여 풀이를 진행하면 해결법이 생각날 것이다. 음수 값이 포함되어도 합이 최대 일 수 있다는 점 그렇지만 음수는 합에 영향을 준다는 점 (모두 0 이상인 수라면 전체 합이 최대이다) 한 번 다음 ..

[Baekjoon] 11055: 가장 큰 증가 부분 수열 [내부링크]

문제 가벼운 11053: 가장 긴 증가하는 부분 수열에서 변형된 가벼운 dp 문제이다 풀이 내 풀이 import sys n = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = seq[:] dp[0] = seq[0] for i, v in enumerate(seq): for j in range(i-1, -1, -1): if seq[j] < v: dp[i] = max(dp[i], v+dp[j]) print(max(dp)) 해당 문제는 제일 큰 수의 합을 기억하며 나아가는 해법을 찾아가야 한다. 처음 제출했을때 dp 리스트를 모두 0으로 채워놓고 시작했는데, 현재 값보다 작은 값이 발견이 안됐을 때 0으로 처리되어..

[Data Structure] 3. 세그먼트 트리(Segment Tree) [내부링크]

세그먼트 트리? 여러 개의 데이터가 존재할 때 특정 범위의 합을 구하는데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진트리의 형태이다. 0 1 2 3 4 5 6 7 8 9 5 6 9 3 8 2 5 1 4 7 위의 데이터에서 1부터 7까지의 합을 구한다 했을 때, 일반적으로 데이터를 하나씩 돌면서 더하면 O(N)의 시간이 걸린다. 하지만 세그먼트 트리를 사용하면 O(logN)의 시간에 구할 수 있다. 구현 세그먼트 트리 생성 먼저 전체 원소를 더한 값을 최상단 노드에 넣는다. 이때, 최상단 노드의 인덱스는 1을 부여한다. 트리를 구현하다보면 알겠지만, 양쪽 자식노드의 인덱스를 부여할 때 0부터 시작하는 것보다 1부터 시작하는 것이 편하다. 왼쪽자식노드 = 부모노드*2, 오른쪽자식노드 = 부모노드 * ..

[Java] 3. Iterator [내부링크]

Iterator? Iterator는 컬렉션에 저장된 요소에 접근하는데 사용되는 인터페이스이다. Iterator의 구버전으로 Enumeration이 있고, 기능을 향상 시킨 ListIterator가 있다. iterator()는 Collection 인터페이스에 정의된 메서드이므로 List와 Set에도 포함되어 있다. Map Iterator 처리 Map 인터페이스를 구현한 컬렉션 클래스는 key와 value를 쌍으로 저장하고 있기 때문에 iterator()를 직접 호출할 수 없다. 대신 keySet()이나 entrySet()과 같은 메서드를 통해서 key와 value를 각각 따로 Set의 형태로 얻어 온 후에 다시 iterator()를 호출해야 Iterator를 얻을 수 있다. Iterator it = map..

[Data Structure] 2. 이진 탐색 트리(Binary Search Tree) [내부링크]

이진 탐색 트리(Binary Search Tree)? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. 각 노드에 중복되지 않는 키가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다. 이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다. 이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다. 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만..

[Data Structure] 1. 우선순위 큐(Priority Queue) & 힙(Heap) [내부링크]

우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐의 요소는 모두 우선순위를 가지고 있으며, 우선순위가 같은 경우에는 큐의 순서에 따라 처리한다. 우선순위 큐는 여러 방식으로 구현할 수 있지만 힙(heap)이 가장 효율을 보이기 때문에 일반적으로 힙을 이용하여 구현한다. 방식 시간 복잡도 배열 O(N) 연결 리스트 O(N) 힙 O(logN) 힙(heap) 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드는 자식노드 사이에 대소관계를 가지고 있다. 중복된 키를 허용한다. 힙의 종류 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙 최소 힙(min heap): ..

[Java] 2. List [내부링크]

List? List는 컬렉션 프레임워크에서 제공하는 컬렉션 클래스 중 하나이다. 컬레션 프레임워크의 핵심 인터페이스에는 대표적으로 List, Set, Map이 있는데 여기서 List는 순서가 있고 데이터의 중복을 허용하는 특징이 있다. List 인터페이스의 구현 클래스에는 ArrayList, LinkedList, Stack, Vector 등이 있다. ArrayList ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스이다. ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리과 기능적인 측면에서 동일하며 Vector는 기존에 작성된 소스와의 호환을 위해 남겨두고 있을 뿐이기 때문에 가능하면 ArrayList를 사용하는 것이 좋다. ArrayList를 생성할..

[정보처리기사] 2. 현행 시스템 분석 [내부링크]

현행 시스템 파악 "현행 시스템이 어떤 하위 시스템으로 구성되어 있고 제공 기능 및 연계 정보는 무엇이며 어떤 기술 요소를 사용하는지를 파악하는 활동" 현행시스템 파악 절차 구성/기능/인터페이스 파악 → 아키텍처 및 소프트웨어 구성 파악 → 하드웨어 및 네트워크 구성 파악 소프트웨어 아키텍처(Software Architecture) "여러 가지 소프트웨어 구성요소와 그 구성요소가 가진 특성 중에서 외부에 드러나는 특성, 그리고 구성요소 간의 관계를 표현하는 시스템의 구조나 구조체" 소프트웨어 아키텍처 프레임워크(Software Architecture Framework) "소프트웨어 집약적인 시스템에서 아키텍처가 표현해야 하는 내용 및 이들 간의 관계를 제공하는 아키텍처 기술 표준" 소프트웨어 아키텍처 프..

[정보처리기사] 1. 소프트웨어 개발 방법론 [내부링크]

소프트웨어 생명주기 모델 "시스템의 요구분석부터 유지보수까지 전 공정을 체계화한 절차" 소프트웨어 생명주기 모델 프로세스 요구사항 분석 → 설계 → 구현 → 테스트 → 유지보수 소프트웨어 생명주기 모델 종류 종류 설명 장점 단점 폭포수 모델 각 단계를 확실히 마무리 지은 후에 다음 단계로 넘어가는 모델 이해가 용이, 관리가 편이 요구사항 변경이 어려움 프로토타이핑 모델 고객이 요구한 주요 기능을 프로토타입으로 구현하여, 고객의 피드백을 반영하여 소프트웨어를 만들어나가는 모델 요구분석 용이, 타당성 검증 가능 프로토타입 폐기에 따른 비용 증가 나선형 모델 위험을 최소화하기 위해 점진적으로 완벽한 시스템으로 개발해 나가는 모델 위험성 감소와 변경에 유연한 대처 단계 반복에 따른 관리 어려움 반복적 모델 구축..

[Unix Programming] ipcs & ipcrm [내부링크]

ipc 설비의 상태를 출력하는 ipcs와 ipc의 설비를 제거하는 ipcrm 명령어에 대해 알아보자. 먼저 ipcs는 위와 말한 것과 같이 IPC 설비의 현재 상태정보를 출력하는 명령어이다. 위와 같이 상태정보를 확인할 수 있다. 다음으로 ipcrm은 시스템으로부터 IPC 설비를 제거하는 명령어로 작성 형태는 다음과 같다. ipcrm 옵션에 따라 제거할 수 있는 IPC를 정할 수 있다. Message Queue: -q Shared Memory: -m Semaphores: -s

[Java] 1. Collections Framework [내부링크]

Collections Framework? JDK1.2부터 Collections Framework가 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 표준화된 방식으로 다룰 수 있도록 체계화되었다. Collections Framework에서는 컬렉션데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다. 그리고 인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의하였다. 각 인터페이스 특징 List 순서가 있는 데이터의 집합, 데이터의 중복을 허용함 ArrayList, LinkedList, Stack, Vector 등 Set 순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허..

[정보처리기사] 0. 목차 [내부링크]

요구사항 확인 소프트웨어 개발방법론 소프트웨어 개발방법론 비용산정, 일정관리 모형 현행 시스템 분석 현행 시스템 파악 개발 기술 환경 정의 요구사항 확인 요구사항 요구사항의 시스템화 타당성 분석 분석 모델 확인하기 분석 모델 검증 분석 모델의 시스템화 타당성 분석 화면 설계 요구사항 확인 UI 요구사항 확인 UI 표준 UI 지침 스토리보드 UI 프로토타입 제작 및 검토 UI 설계 UI 설계를 위한 UML UI 흐름 설계 UI 상세설계 UI 설계 도구 데이터 입출력 구현 논리 데이터 저장소 확인 데이터 모델 논리 데이터 모델 검증 물리 데이터 저장소 설계 물리 데이터 모델 설계 물리 데이터 저장소 구성 데이터베이스 기초 활용하기 데이터베이스 종류 통합 구현 연계 데이터 구성 연계 요구사항 분석 연계 데이터..

[Unix Programming] Shared Memory [내부링크]

Shared Memory는 여러 process가 동시에 접근할 수 있는 메모리로, 두 개 이상의 process가 물리적 메모리의 일부를 공유한다. 여기서 주의할 점은 아무 process가 접근할 수 있는 것이 아니라, 잘 제어된 함수를 통해 요청한 process만 접근이 가능하다. Shared Memory는 앞에서 봤던 IPC 기법들 중에서 가장 빠르고 효율적이다. Shared Memory 기법의 사용 방법에 대해 간략히 살펴보면, 먼저 shmget 함수를 통해 접근 가능한 메모리 공간 할당을 요청한다. 그다음 shmat 함수를 통해 논리 메모리에 shmget을 통해 얻은 물리 메모리를 mapping 시켜준다. 마지막으로 사용하지 않으면 shmdt 함수를 호출하여 논리 메모리를 통해 물리 메모리에 접근하..

[Unix Programming] Semaphore [내부링크]

synchronization 기법 중 하나인 semaphore에 대해 알아본다. Semaphore는 공유된 자원에 대한 접근을 제어 하는 방식으로 1개의 공유되는 자원에 제한된 개수의 process나 thread가 접근할 수 있도록 한다. 다시 말해서, process간의 message 전송 또는 shared memory를 통해 특정 데이터를 공유하게 되는 경우 여러 개의 process가 동시에 접근하면서 문제가 발생할 수 있는데 이 접근을 제어하는 것이 semaphore이다. 이는 mutex와 유사한 기능을 수행하지만, 다음과 같은 차이가 있다. 하나의 process/thread의 접근을 제어하는 mutex와 달리, semaphore는 공유자원에 접근할 수 있는 process/thread의 수를 나타내는..

[Unix Programming] Message Passing [내부링크]

Message Passing은 IPC 기법 중 하나로 memory protection을 위해 커널의 도움을 받아 message를 전달한다. 여기서 message는 문자나 byte의 열이라고 생각하면 된다. Message Passing의 방식은 한 process가 msgsnd를 하게되면 사용자의 주소 공간으로부터 message queue에 message가 저장되고, 다른 process가 msgrcv를 하게되면 message queue에 있는 message를 사용자의 주소 공간으로 가져오게된다. 앞에서 본 것과 같이 Message Passing은 커널에 message queue를 만들어서 통신을 한다. message queue는 msgget 함수를 통해 만들어지며 message의 임시 버퍼로 쓰인다. 그럼 ..

[Unix Programming] IPC 기본 개념 [내부링크]

IPC 기법에는 여러가지의 종류가 있는데 우선 다음의 기법에 대해 알아보도록 하자. - message passing - shared memory - pipe 우선 위 기법에 대해 알아보기 전, facility key와 get 연산에 대해 먼저 알아야 한다. IPC에는 facility key라는 것이 있는데 이것은 IPC 객체를 유일하게 식별하기 위해 사용되는 수이다. 소켓 통신을 할 때 IP와 Port 번호로 소켓을 유일하게 식별하는 것처럼, IPC 통신에서는 facility key를 사용하여 객체를 식별하는 것이다. facility key 값을 integer 형식의 숫자로 부여해도 되지만 숫자는 중복될 가능성이 높기 때문에 이 위험을 방지하기 위해 ftok이라는 함수를 쓴다. ftok은 파일 이름을 키..

[Unix Programming] Record Locking [내부링크]

Record Locking은 두 명 이상의 파일 사용자가 동시에 정보를 업데이트하려고 할 때 발생할 수 있는 오류, 즉 경쟁상태를 방지하기 위해 파일 또는 파일의 일부를 잠그는 것이다. Record Locking read lock - 여러 프로세스들이 같은 구역 동시에 설정 가능(write lock 적용 불가) write lock - 다른 프로세스들의 읽기나 쓰기 록을 불허 record lock을 걸기 위해서 fcntl이란 함수를 사용한다. #include int fcntl(int filedes, int cmd, struct flock *ldata); 여기서 filedes는 file descriptor를 의미하고, cmd는 F_GETLK, F_SETLK, F_SETLKW 을 넣어 설정할 수 있다. str..