본문 바로가기
728x90

넓고 얕은 자료구조 & 알고리즘35

[JAVA] 약수 구하기 // N의 약수 구하기 for(int i = 1; i 2022. 9. 29.
검색 알고리즘(Search Algorithm) 검색 알고리즘에 대하여 데이터를 검색만 한다면 계산 시간이 가장 짧은 것을 선택하는 것이 좋다. 그러나 검색뿐만 아니라 데이터를 추가하거나 삭제하는 작업까지 수행해야 한다면 검색 이외의 작업에 소용되는 비용까지 종합적으로 고려하여 알고리즘을 선택해야 한다. 고려 대상에는 목적, 용도, 실행 속도, 자료 구조 등이 있다. 데이터 추가 비용이 많이 든다는 의미 배열 데이터의 중간에 새로운 데이터를 삽입하는 경우, 새로운 데이터가 들어가는 자리 이후의 데이터는 전부 한 칸씩 밀어내야 하는데 이 경우 데이터의 추가 비용이 많이 들게 된다. 선형 검색(linear search), 순차 검색(sequential search) 요소가 직선 모양을 늘어서 있어 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로.. 2022. 9. 27.
완전 탐색 알고리즘(Brutal-Force Algorithm) 완전 탐색 알고리즘(Brutal-Force Algorithm) 무차별적으로 대입하는 방법을 나타내는 알고리즘이다. 즉 모든 가능성을 시도하여 문제를 해결한다. 따라서 데이터 크기가 커질수록 비효율적이다. 완전 탐색 알고리즘을 사용하는 경우 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 완전 탐색 알고리즘의 한계 문제의 복잡도에 매우 민감하다. 문제가 복잡해질수록 기하급수적으로 많은 자원(시간, 컴퓨팅 자원)을 필요로 하게 된다. 완전 탐색 알고리즘을 활용하는 알고리즘 순차 검색 알고리즘(Sequential Search) 문열 매칭 알고리즘(Brutal-Force String Matching) 선택 정렬 알고리즘 버블 정.. 2022. 9. 27.
탐욕 알고리즘(Greedy) 탐욕 알고리즘(Greedy) 선택의 순간에 당장 눈앞에 보이는 최적의 상황을 선택하여 최종 해답에 도달하는 방법이다. 탐욕 알고리즘이 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 탐욕 알고리즘의 단계 선택 절차(Selection Procedure) : 현재 상태에서 최적의 해답을 선택한다. 적절성 검사(Feasiblility Check) : 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 반복 탐욕 알고리즘의 조건 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적.. 2022. 9. 27.
선형 리스트(Linear List)와 연결 리스트(Linked List) 선형 리스트(linear list) 데이터가 배열처럼 연속하는 공간에 저장되어 순서를 갖는다. 연결 리스트(linked list) 각각의 데이터 안에 다음 데이터에 대한 정보가 저장되어 있어 서로 연결된다. 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애는 방식으로 구현한다. Linked List의 구조 배열 연속된 메모리 주소값 안에 데이터를 넣는 구조로 위치를 바꾸려면 데이터가 전체적으로 이동해야 한다. 연결 리스트 흩어져 있는 공간에 노드들의 연결로 이루어져 있다. 각 노드는 다음 노드를 가리키며, 연속된 메모리 주소가 아니기 때문에 직접 주소 값을 가지도 있어야 다음 노드로 접근이 가능하다. 마지막 노드는 새 노드가 추가되기 전까지 null을 가리킨다. 연결 리스.. 2022. 9. 27.
Deque(Double Ended Queue) Deque(Double Ended Queue) 양방향 대기열이라고도 한다. 양방향으로 열려있는 구조로, LIFO, FIFO와 같은 순서에 구속되지 않는다. 실의 양쪽에 구슬을 꿰어 넣는 것과 같이 Stack과 Queue의 특성을 동시에 이용할 수 있다. Deque의 특징 Stack과 Queue를 이용한 경우의 수 한쪽에서만 데이터 추가가 가능하고, 양쪽에서 모두 데이터 삭제가 가능한 경우 양쪽에서 모두 데이터 추가가 가능하고, 한쪽에서만 데이터 삭제가 가능한 경우 양쪽에서 모두 데이터 추가와 삭제가 가능한 경우 임의의 데이터를 임의의 인덱스에 추가, 삭제는 불가능하다. 2022. 9. 27.
그래프(graph)와 트리(tree) 그래프(graph) 여러 개의 점들이 서로 연결되어 있는 관계를 표현한 자료구조 그래프에서 하나의 점을 정점(vertex), 하나의 선을 간선(edge)라고 한다. 인접 행렬 [1] = [0, 0, 1, 0, 1] // 간선이 있으면 1, 없으면 0 [2] = [0, 0, 0, 1, 0] // 무방향 그래프 [3] = [1, 0, 0, 0, 0] [4] = [0, 1, 0, 0, 0] // ex) 4 -> 5처럼 한 방향만 있으면 방향 그래프 [5] = [1, 0, 0, 0, 0] 두 정점을 이어주는 간선이 있을 때, 이 두 정점을 인접하다고 한다. 예를 들어 A, B, C라는 서로 다른 정점이 있고 A와 B가 서로 이어져 있다면 1(true), 이어져 있지 않다면 0(false)을 표시한다. 한 개의 .. 2022. 9. 26.
큐(queue) 구현해보기 큐(queue) 선입선출(FIFO: First In First Out)의 구조를 갖는 자료구조이다. // 배열을 이용한 원형 큐 구현하기 public class RingQueue { private int[] que; // 큐용 배열 private int capacity; // 큐 용량 private int front; // 맨 앞의 요소의 인덱스 private int rear; // 맨 뒤의 요소에서 하나 뒤 인덱스(인큐할 때 저장될 요소의 인덱스를 미리 준비) private int num; // 현재 데이터 개수 // front와 rear 값이 같을 때 큐가 비어있는지, 가득찼는지 구분하기 위해 만든 변수 // 실행 시 예외 : 큐가 비어있는 경우 public class EmptyQueueExcepti.. 2022. 9. 23.
728x90

티스토리툴바