Algorithm & Data Structure/개념

[Concept] 인접행렬과 인접 리스트(LinkedList, ArrayList)

DFS와 BFS 문제를 풀기위해서는 무조건 알고 있어야하는 개념이 그래프입니다. 그리고 그래프를 구현하는 방법으로 인접행렬과 인접리스트가 있습니다. 이번 글에서는 각각의 장단점과 Java로 구현하는 것으로 마무리하겠습니다. (+LinkedList와 ArrayList의 장단점) 그래프 그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조입니다. 그래프에서 쓰이는 용어는 정점 (vertex) : 노드라고도 하며 데이터가 저장되는 원소 간선 (edge) : 링크라고도 하며 정점 간의 관계 그외에도 인접 정점, 차수, 경로 등의 용어가 있습니다. 그래프 구현 그래프를 구현하는 방법은 배열(Array)을 사용하는 인접 행렬, 리스트를 사용하는 인접 리스트가 있습니다. 그리고 인접 리스트를 구현하..

[Concept] 인접 행렬과 인접 리스트

그래프 그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조입니다. 그래프에서 쓰이는 용어는 정점 (vertex) : 노드라고도 하며 데이터가 저장되는 원소 간선 (edge) : 링크라고도 하며 정점 간의 관계 그외에도 인접 정점, 차수, 경로 등의 용어가 있습니다. 그래프 구현 그래프를 구현하는 방법은 배열(Array)을 사용하는 인접 행렬, 연결 리스트를 사용하는 인접 리스트가 있습니다. 인접 행렬 그래프의 정점을 2차원 배열로 만들어서, 행과 열은 정점을 의미하며 각각의 원소들은 정점 간의 간선을 나타냅니다. 장점 2차원 배열에 모든 장점들의 간선 정보가 있기 때문에 두 정점을 연결하는 간선을 조회 시 O(1)의 시간복잡도로 가능합니다. 구현이 비교적 간단합니다. 단점 간선 수와 ..

java.lang.StringBuilder (가변적인 문자열)

StringBuilder 클래스 StringBuilder와 StringBuffer 클래스는 String 클래스와 같이 문자열을 다루는 클래스이다. But, String 클래스는 문자열을 넣을 경우, 생성자의 크기에 맞게 길이가 생성되며 한번 생성하고 나면 문자열 값을 변경하지 못하는 단점이 있다. 이를 보완하는 것이 StringBuilder와 StringBuffer 클래스이다. 즉, 한번 생성한 인스턴스 안의 문자열 (char 배열)을 추가&변경할 수 있어 String클래스의 문제를 보완한다. 두 클래스는 거의 비슷하지만(쓰임과 메소드가 같지만) StringBuffer는 동기화 처리를 할 수 있다. 즉, 여러 곳에서 동시에 같은 문자열 인스턴스에 접근할 때 중복 접근을 막을 수 있는 장치를 가지고 있다...

[Concept] 재귀 용법

재귀 용법 함수 안에서 동일한 함수를 호출하는 형태 여러 (고급정렬 포함한) 알고리즘 작성시 사용되므로, 익숙해져야 합니다. 스택의 구조와 똑같이 동작이 이루어집니다. 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 1000회 이하가 되어야 합니다. 함수를 하나 만든다. 함수(n) 은 n > 1 이면 return n X 함수(n - 1) 함수(n) 은 n = 1 이면 return n 예시 2! 1. 함수(2) 이면, 2>1 이므로, 2 X 함수(1) 2. 함수(1)은 1이므로, return 2 X 1 = 2 3! 1. 함수(3)이면, 3>1이므로, 3 X 함수(2) 2. 함수(2)이면, 2>1이므로, 3 X 2 X 함수(1) 3. 함수(1)은 1이므로, return 3 X 2 X 1 = 6 psud..

삽입 정렬

삽입정렬은 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다. 예제와 함께 보는 정렬 방식 맨 처음 두개의 값을 정렬범위로 시작합니다. 1. 1을 앞에 있는 2와 비교. (맨 첫번째 값이니 끝) => [2, 1, 5, 4, 3] 더 큰 값이네? 1과 swap => [1, 2, 5, 4, 3] 2. 한 칸을 더 확장하여 그 값을 정렬된 배열과 비교. 5를 앞에있는 2와 비교. => [1, 2, 5, 4, 3] 바꿀 필요 없으니 교환하지 않고 끝. 3. 한 칸을 더 확장하여 4를 앞에있는 5와 비교. => [1, 2, 5, 4, 3] 더 큰 값이네? 5와 swap => [1, 2, 4, 5, 3] 2와 바꿀 수 없으니 비교 종료. 4..

선택 정렬

가장 최소인 값을 맨 앞 값이랑 바꿔주는 "선택" 정렬 패턴 파악 데이터 3개 (턴 2번, 1. 최솟값과 비교 2번 2. 최솟값과 비교 1번) 1. 턴 한번 5 4 2 2 4 5 데이터 4개 (턴 3번, 1. 최솟값과 비교 3번 2. 최솟값과 비교 2번 3. 최솟값과 비교 1번) 5 4 3 1 1 4 3 5 1 3 4 5 파악되는 중요 패턴은 다음과 같다. 1. 매 턴마다 앞 자리가 정해지면서 반복 횟수가 줄어든다. 2. (매 반복에서) 맨 앞 인덱스의 값과 최솟값을 바꾼다. psudo 코드 for i in range( len(data) -1 ): min = i for j in range( i+1, len(data) ) : if data[min] > data[j]: min = j swap(data[min..