목록전체 글 (278)

유블로그

[알고리즘] 리스트

순서를 가진 데이터의 집합을 가리키는 추상자료형 동일한 데이터를 가지고 있어도 상관없다. 종류 배열을 기반으로 구현된 리스트인 순차리스트 메모리의 동적할당(JVM의 객체 생성)을 기반으로 구현된 리스트인 연결리스트 1차원 배열에 항목들을 순서대로 저장한다. 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 만들 수도 있다. 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. 문제점 단순 배열을 이용해 순차리스트르 구현해 사용하는 경우, 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요하다. 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가한다. 배열의 크기가 정해..
알고리즘 2020. 8. 9. 20:42
[알고리즘] 탐욕(Greedy) 알고리즘

최적해를 구하는 데 사용. 하지만 최적해를 반드시 구한다는 보장이 없다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식. 선택 시점 때 최적이어도 최종해가 최적이라고는 할 수 없다.
알고리즘 2020. 8. 6. 15:55
이클립스 디버깅 키

F11 : 디버그 실행 F5 : 함수 내로 들어가면서 실행 F6 : 함수 내로 들어가지않고 알아서 실행 후 다음 라인으로 감 F7 : F5로 함수 잘못들어가면 나오기(이전 메소드로 돌아감) F8 : 제어위치에서 다음 breakpoint 까지 자동실행
기타 2020. 8. 6. 15:41
이클립스 workspace내 프로젝트와 깃허브연동

1. git bash에서 cd로 workspace 내의 원하는 프로젝트에 간다. 2. $ git init -> 끝에 (master) 생긴다. 3. 원래 있던 파일들을 임시로 잠시 옮겨 그 폴더를 비운다. 4. github에 repository 를 하나 만든다. repository에 https://www.toptal.com/developers/gitignore 이 링크에서 java, eclipse, window 입력해서 나오는 거 복사해서 .gitignore 파일 만들어 붙여넣기한다. 5. repository의 code (초록색버튼) 눌러서 링크복사누른다. 6. git bash 로 돌아와서 $ git clone -> 로컬 폴더에 .git 폴더가 생긴다. 7. 3번에서 옮겼던 파일들을 다시 로컬 폴더에 넣는..
Git 2020. 8. 6. 15:26
[알고리즘] JAVA 정렬 API

java.lang.Comparable int compareTo(T other) 자신과 인자로 전달 받는 타 원소와 비교하여 정수 리턴 a.compareTo(b) 음수 : a가 더 작다. 그대로 0 : a = b 양수 : b 가 더 크다. 자리 바꾼다 오름차순 정렬 됨 class A implements Comparable { int num; A(int num){ this.num = num; } @Override public int compareTo(A o){ return this.num - o.num;// 정렬 기준은 하나 밖에 안됨. // 양수와 음수가 섞여있을 때 오버플로우 방지하려면 // return Integer.compare(this.num, o.num); 하면 됨 } } public static..
알고리즘 2020. 8. 6. 11:28
[알고리즘] 최소 신장 트리(MST) - KRUSKAL 알고리즘

그래프에서 최소 비용 문제 모든 정점 연결 간선들 가중치 합이 최소가 되는 트리 두 정점 사이 최소 비용 경로 찾기 신장 트리 : n개 정점 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 : 서로소 집합 사용 간선을 하나씩 선택해서 MST 를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬(최대신장트리는 내림차순) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택(union 연산 실패 상황) n-1 개의 간선이 선택될 때까지 2를 반복 ..
알고리즘 2020. 8. 6. 10:23
[알고리즘] 이진트리 순회(traversal)

.
알고리즘 2020. 8. 6. 09:39
[알고리즘] BFS, DFS

너비 우선 탐색 루트 노드가 자식 노드들을 먼저 차례로 방문후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 '큐' 를 활용함 BFS() 큐 생성 루트 v를 큐에 삽입 while(큐가 비어 있지 않은 경우) { t = 큐의 첫 번쨰 원소 반환 t 방문 for(t와 연결된 모든 간선에 대해) { u = t의 자식 노드 u를 큐에 삽입 } } end BFS() 깊이 우선 탐색 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색..
알고리즘 2020. 8. 4. 23:35
이전 Prev 1 ··· 30 31 32 33 34 35 Next 다음