티스토리

그냥하자

검색하기

블로그 홈

그냥하자

sungone-develop-study.tistory.com/m

제로펩시콜라 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[알고리즘] 크루스칼(Kruskal) 알고리즘이란? 크루스칼(Kruskal) 알고리즘 간선의 가중치 정보를 이용해 MST(최소신장트리)를 구현하는 알고리즘 이다. 이용되는 알고리즘은 Union Find, 우선순위 큐가 있다. 1) 전체 로직 순서 Comparable을 상속받아 Edge 클래스(정점1, 정점2, 가중치)를 선언한다. compareTo를 오버라이딩 하여 가중치를 기준으로 오름차순 정렬을 조건을 추가한다. Edge형 우선순위큐를 선언하고 주어진 간선의 정보를 이용해 새로운 edge 객체를 우선순위큐에 넣어준다. 우선순위큐에서 간선을 순서대로 빼온다. 빼온 간선에 해당하는 두 정점이 같은 Union인지 확인한다. 같은 Union이라면 -> 이미 추가된 정점들이므로 다음 간선을 빼낸다 다른 Union이라면 -> 해당 정점의 부모노드를 이용해 같은 .. 공감수 0 댓글수 0 2022. 3. 30.
[알고리즘] 최소신장트리, MST란? MST란? Minimum Spanning Tree의 약자로 최소신장트리 라고 불린다. 위 그림과 같이 그냥 Spanning Tree는 모든 정점이 연결되어 있는 Tree이다. 조금 더 구체적으로 말하면 모든 정점이 임의의 간선들을 거쳐 만날 수 있는 Tree이다. 따라서 MST는 최소한의 가중치로 모든 정점을 연결시킨 Tree이다. MST를 만들 수 있는 알고리즘은 크게 2가지가 있는데 다음과 같다. 1) 크루스칼(kruskal) 알고리즘 2) 프림(prim) 알고리즘 1) 크루스칼 알고리즘 이란? 크루스칼 알고리즘이란 주어진 간선의 가중치를 기준으로 MST를 찾는 알고리즘이다. 크루스칼 알고리즘 구현을 위해 쓰이는 자료구조 및 개념 -> 우선순위큐, Union Find 2) 프림 알고리즘이란? 프림 알.. 공감수 0 댓글수 0 2022. 3. 30.
우선순위 큐는 왜 힙 구조를 사용할까? 우선순위큐에 대해 설명하기 전에 힙에 대해 간단히 정리해보면, 힙은 완전 이진트리의 형태이며 루트노드가 최대값(max-heap기준)이고, 삽입 삭제의 연산이 logN인 특징을 갖는다. 그렇다면 우선순위큐란 뭘까? 기존에 큐(Queue) 자료구조는 넣은 순서대로 출력이 되었다면, 우선순위큐는 기준을 스스로 정할 수 있는것이다. 여기서 기준이란? 데이터를 입력한 자료구조에서 빼내올때 출력되는 순서의 기준을 뜻한다. 큐의 경우 입력순서가 될 것이다. 다시 본론으로 돌아와서 우선순위큐를 구현할 수 있는 자료구조는 많이 있는데 왜 하필 우선순위큐는 힙 구조를 사용할까? 이유는 수행시간 때문이다. 노드(데이터)수를 N이라고 했을때 heap은 삽입 삭제 연산이 모두 logN이지만 배열, 리스트와 같은 선형구조의 형태.. 공감수 0 댓글수 0 2022. 3. 1.
힙(Heap)의 구조와 동작과정 나머지는 관심없고 부모노드만 알고싶은 힙(Heap) 힙(Heap)이란 (max-heap)일 경우, 루트노드가 가장 큰 노드이고, (min-heap)일 경우, 루트노드가 가장 작은 노드이다. 따라서 루트노드를 제외하고 나머지 노드의 관계는 알 수도 없고, 중요하지도 않다. 어떻게 힙 자료구조가 동작하는지 알아보자. * 힙의 삽입 과정 (max-heap 기준) 1) 완전이진트리의 형태이므로 리프노드 자리중 다음 노드 자리에 일단 new Node 삽입 2) 부모노드와 비교했을때 삽입한 노드가 더 크다면 부모노드와 스왑, 아니면 그대로 3) 더 큰 부모노드를 만날때까지 2번을 반복한다, 루트노드까지 간다면 거기서 종료 위 과정을 그림으로 나타내면 다음과 같다. * 힙의 삭제 과정 (max-heap 기준) 1) .. 공감수 0 댓글수 0 2022. 3. 1.
트리(Tree)의 개념과 종류들 비선형 자료구조, 트리 이전까지의 자료구조들은 모두 선형 자료구조였다. 배열, 리스트, 스택, 큐 등 모두 선의 모양으로 쭉 나열된 형태의 모양이었다면 트리는 그러한 모양을 띠지 않기 때문에 대표적인 비선형 자료구조라고 불린다. 자료구조의 근본적인 모양이 이전과는 다르므로 용어자체도 다른 부분이 많다. 위 그림을 보면 용어를 알 수 있는데 정리해보면 다음과 같다. 노드(Node) : 각 데이터 간선(edge) : 각 노드를 잇는 선 부모노드: 현재 노드에서 간선을 통해 위쪽으로 연결된 노드, 1개만 가질수 있다. 자식 노드: 현재 노드에서 간선을 통해 아래쪽으로 연결된 노드 Root(+node): 가장 윗부분에 위치한 노드, 부모노드가 없다. 리프 노드: 가장 바깥쪽에 있는 노드 내부 노드: 리프노드를 .. 공감수 0 댓글수 0 2022. 3. 1.
스택(Stack)과 큐(Queue) 스택과 큐는 가장 기본적인 자료구조이다. dfs, bfs를 구현하는데에도 쓰이며, 여러가지 알고리즘 기법이나 개념등에 적용되는 자료구조이다. 선입후출의 자료구조, 스택(Stack) 스택은 바닥이 막혀있고 윗부분이 뚫려있는 자료구조 라고 생각하면 된다. 그래서 스택은 뚫려있는 위로만 데이터가 들어올 수 있다. 그렇다면 데이터를 뺄때는?? 똑같이 위로만 데이터가 나갈수가 있다. 따라서 먼저 들어온 데이터들은 들어온 순서대로 아래로 깔리게 되고 나중에 들어올수록 먼저 나가게된다. 때문에 스택은 "선입후출"의 자료구조라고 부른다. 이러한 스택의 특성을 이용하여 대표적으로 이용되는 알고리즘이 dfs구현이다. 물론 저러한 모양은 추상적으로 표현한 것일 뿐이며, stack의 내부 구현을 타고 들어가면 배열로 구현이 .. 공감수 0 댓글수 0 2022. 3. 1.
순열, 조합, 부분집합 순열, 조합, 부분집합은 탐색에서 자주 출제되는 유형이다. 항상 헷갈렸었는데 정리해보자 순열: 순서가 의미있다! 순열이란 ? 순서가 의미있는 조합이다. 즉, 순서가 달라지면 그 의미도 달라진다. 예를들어) 주사위를 3번 던졌을때 나올수있는 모든 수의 순서를 구하라 이경우에 (1,3,5)와 (3,1,5)는 다른 경우이다. 조합과 다르게 현재 선택된 수보다 작은수를 다음에 선택할수있다 -> visit배열을 이용하여 처리한다. 순열의 모든 경우를 구하려면 어떻게 해야할까? for문을 돌리며 result배열의 각 index에 수를 넣는다 import java.util.*; public class 순열_연습 { static int[] result; static int[] visit; static int[] dic.. 공감수 0 댓글수 0 2022. 2. 27.
2차원 배열 원소 한칸씩 옮기기 달팽이 배열에 이어 2차원 배열에서 원소들을 한칸씩 이동하는 경우도 있을 수 있다. 이 경우도 달팽이 배열을 찍는것과 크게 다르지 않다. 다음과 같이 원소를 한 칸씩 시계방향으로 이동시켜야 한다고 해보자. 두 변수의 값을 switching할때처럼 그냥 바꿀 수는 없고 값을 임시저장할 변수를 이용하는데 이 경우도 그 아이디어는 같다. 어느 위치의 값을 임시저장 해줄것인지는 자유이지만 여기서는 (0,0)이라고 하겠다. 여기서 (0,0)좌표의 값을 임시저장 했으므로 바로 밑에있는 (1,0)의 값을 (0,0)으로 가져와야한다. 즉, 시계방향으로 한칸씩 이동시킬 때, 현재 위치에 놓일 다음 값은 반시계 방향으로 찾으러 가야한다. 따라서 next값의 방향이 이동방향과 반대가 되는것이다. 원소 한칸씩 옮기기는 이 점.. 공감수 0 댓글수 0 2022. 2. 27.
달팽이 배열 찍기 가끔 2차원 배열 구현 문제에서 달팽이 모양으로 방문순서를 좌표에 찍도록 하는 문제가 있다. 이러한 문제유형에서 응용된 많은 문제들이 있는데 만날때마다 한숨부터 나왔다. 4방향의 범위를 오차없이 생각해내는 것부터 헷갈리고 가끔 한끝차이로 오류가 날떄는 그걸 찾느라 많은 시간을 보냈다. 어려운건 아니지만 실수를 많이 유발하는 유형이었다. 그래서 구글링을 해봤고 그 중 가장 헷갈리지 않는 방법을 찾았다!! 2차원 배열의 가로 세로 크기 입력 -> 그 모양에 맞게 달팽이 배열 만들기 내가 생각했을때 가장 쉬운 방법은 방향을 나타내는 배열을 이용하는 사방탐색의 방법을 응용하는것이다. 이 아이디어는 다음과 같다. 만약 아래 그림과 같이 방문순서대로 숫자를 배열에 입력후 출력해야 한다고 가정해보자. 사방탐색의 아이.. 공감수 0 댓글수 0 2022. 2. 27.
DFS 와 BFS의 방문처리 시점은 왜 다를까?? DFS(깊이 우선 탐색)은 재귀함수, STACK을 이용하여 구현하고 BFS(넓이 우선 탐색)은 QUEUE를 이용하여 구현한다. 기계적으로 코드를 구현하다보니 문득 궁금한점이 생겼다. 왜 두 탐색방법의 방문처리시점이 다를까? 이 궁금증을 이전에 제대로 해결하지 않은채 코테나 알고리즘 문제를 풀다 방문처리 시점을 헷갈려 시간을 낭비하게 되는 경우가 있었다. 이는 STACK과 QUEUE와 함께 dfs bfs의 근본적인 동작방식을 제대로 이해하는데도 큰 도움이 된다고 생각하여 정리해보겠다. 우선 dfs의 방문처리 시점은 실제로 그 지점을 방문한 직후에 처리를 한다. bfs처럼 이전에 하면 안되는 이유가 뭘까? dfs는 범위내에있고 방문한적이 없다면 갈수있을때까지 파고든다. 즉, 방문가능지역 검사에서 만난 순서와.. 공감수 4 댓글수 0 2022. 2. 22.
DFS, BFS의 개념과 동작방식 DFS: depth first search의 약자로 "깊이 우선 탐색"을 뜻한다. 보통 dfs, bfs는 트리 혹은 2차원 좌표상에서 구현하게 된다. 탐색 조건에 맞다면 탐색 가능할때까지 쭈욱 가는게 dfs이다. 탐색 조건이라는게 뭘까? 어떤 상황에서 구현하느냐에 따라 다르겠지만 필수적인 탐색조건은 이전에 방문했는지 여부이다. 그 외에도 2차원좌표상에서 구현한다면 좌표범위를 벗어나지 않는지, 트리상에서 구현한다면 리프노드를 벗어나지 않는지 등이 있다. 이외에도 상황별로 여러가지 조건이 추가 될 수 있다. 보기 쉽게 2차원 배열에서 dfs를 구현해보자. 만약 (3,3)의 2차원 좌표상에서 dfs를 (상, 우, 하, 좌)의 방향대로 탐색을 가정하면 다음과 같은 결과가 나오게된다. 그렇다면 dfs를 어떻게 구.. 공감수 0 댓글수 0 2022. 2. 22.
자료구조 - List 계열 List 계열 List계열은 중복을 허용하며 저장순서가 유지되는 특징이 있으며 다음과 같은 계층도를 갖는다. 여기서 ArrayList는 Vector를 보완한 것으로 기능과 구현원리가 동일하므로 ArrayList를 쓰기로 한다. 그럼 Vector는 왜 있는가? 기존에 작성된 소스들과의 호환성을 위해 남겨두었을뿐 사실상 의미는 없다. 1) ArrayList ArrayList는 이름에서부터 그렇듯, 배열과 많이 닮아 있다. index로 데이터들을 구분할 수 있기 때문에 중복된 데이터의 입력을 허용하며, index를 이용해 접근도 가능하다. 배열과의 중요한 차이점이 있는데 ArrayList는 우리가 사용하기 편하게 상황에 따라 size가 변하게 된다. 그래서 우리가 처음에 크기를 정해놓고 그만큼만 쓸수있는 배열.. 공감수 0 댓글수 0 2022. 2. 13.
자료구조 - Collection FrameWork Java Collection FrameWORK? 데이터들을 저장하는 클래스들을 표준화한 방식이라고 생각하면 된다. 원래는 컬렉션 클래스(벡터, 해시테이블 등등)를 모두 따로 정의하고 처리했으나 JDK1.2 부터는 컬렉션 클래스가 추가되어 기존의 컬렉션 클래스들을 표준화된 방식으로 다룰 수 있게되었다. 컬렉션 프레임워크에서는 기존의 컬렉션 클래스들에 크게 3가지 부류가 있다고 생각했다. 그 3가지가 List계열, Set계열, Map계열인데 각각 따로 인터페이스를 정의하였고 여기서 List와 Set은 공통적인 부분이 많아 따로 또 Collection을 추가 정의 하였다. 그래서 다음과 같은 계층도가 나오게 된것이다. List계열은 순서가 있으며 데이터의 중복을 허용한다. Set계열은 순서가 없으며 데이터의 .. 공감수 0 댓글수 0 2022. 2. 13.
자료구조, 알고리즘이란? 자료구조란? 자료구조란 말 그대로 자료, 데이터들을 저장하는 구조이다. 이렇게 자료를 저장하는 구조에 따라 탐색, 삽입, 삭제 등의 수행시간이 모두 다르다. 절대적으로 좋은 자료구조는 없으며 상황에따라 상대적으로 좋을 수는 있다. 자바에서는 다음과 같이 Collection FrameWork를 제공하며 크게 List계열, Set계열, Map계열로 분류할 수 있다. 알고리즘이란? 알고리즘이란 자료구조들을 이용하여 문제풀이를 한다고 생각하면 된다. 알고리즘에서 가장 중요한것은 1) 정확도 2) 효율성 이다. 실제 코딩테스트에서도 이 2가지를 중점적으로 본다. 1) 정확도는 어떠한 테스트케이스에도 원하는 결과값이 정확히 나오는지 따지는 것이다. 2) 효율성은 같은 결과값이 나오더라도 더 효율적인 풀이인가?를 따.. 공감수 0 댓글수 0 2022. 2. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.