본문 바로가기

Wook's 개척일기234

[자료구조] 그래프란? (feat. Java) 그래프란? 그래프는 정점(노드)의 집합과 정점(노드)를 이어주는 간선의 집합으로 이루어진 자료구조이다. 그래프의 종류 1. 방향 그래프 / 무방향 그래프 2. 가중치 그래프 3. 비연결 그래프 / 연결 그래프 4. 사이클 / 비순환 그래프 5. 완전 그래프 이렇게 나뉜다. 그럼 이제 각각의 그래프에 대해서 알아보자. 1. 방향 그래프 / 무방향 그래프 방향 그래프는 간선에 방향성이 존재하는 그래프로 A -> B라면 A에서 B로만 갈수 있는 그래프이다. 따라서 (A,B)와 (B,A)는 서로 다르다. 하지만 무방향 그래프는 하나의 간선을 통해서 양방향으로 갈수 있다. 따라서 A - B 라는 간선이 존재한다면 (A - B) 와 (B - A)는 서로 같다. 2. 가중치 그래프 가중치 그래프는 간선에 값이 주어진.. 2021. 6. 18.
[Java] ArrayList 란? 우리는 배열을 선언하게 된다면 항상 그 배열의 크기를 설정해주어야만 한다. 그래서 값을 넣을때 배열의 크기만큼 값을 넣어주지 못하게된다면 배열의 크기를 매번 수정해줘야 한다. 그리고 값을 삭제하게되더라도 마찬가지로 배열의 크기를 변경 해주어야 하고 그리고 삭제한 값의 index를 메꾸기 위해서 index도 수정해주어야 한다. 그래서 이런 수고스러움을 덜어내기 위해서 Java에서 제공하는 클래스가 ArrayList 클래스이다. ArrayList는 크기를 따로 지정해주지도 않아도 되기도 할뿐더러 안에 값을 삭제하더라도 저절로 index를 수정하고 크기도 수정해준다. ArrayList 선언 ArrayList list = new ArrayList(); //타입을 따로 지정하징낳으면 Object로 선언됨 Arra.. 2021. 6. 18.
[Java] LinkedList 란? LikedList란? LinkedList는 아래 사진처럼 각각의 노드가 그림처럼 연결되어 있는 형태로 저장이 되는 방식이다. 그래래서 각각의 노드들은 자기와 연결되어 있는 노드들에 대한 정보만 가지고 있지 전체적인 노드들에 대한 정보를 가지고 있지 않은 형태를 가지고 있다. 위의 그림처럼 서로 다음 노드를 가르키고 있기때문에 값을 추가할땐 새롭게 또 다른곳을 가르키게해 값을 추가할때 용이하고 삭제할때도 마찬가지로 link되어 있는것을 자르기만 하면 되기때문에 삭제에도 매우 용이하다. 하지만 위에서 말했듯이 LinkedList는 다음 노드에 대한 정보만을 가지고 있기 때문에 특정 노드를 검색하기 위해선 모든 경로를 순회해야 된다. 따라서 LinkedList로 검색을 하게 되면 성능 저하를 일으키기 때문에 .. 2021. 6. 18.
[프로그래머스 : 레벨 3] 등굣길 : Dynamic Programing(Java) 이번 문제도 DP 알고리즘을 적용하니 금방 풀리는 문제였다. 문제 자체에서 가로세로의 변수 설정 부분이 이상해서 자꾸 틀려서 한번 가로와 세로 변수를 바꾸니 금방 적용이 잘되었다. 문제를 살펴보자. 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움.. 2021. 6. 17.

티스토리툴바