코딩배우는고양이

다익스트라 알고리즘 단일 시작점 최단 경로 알고리즘으로 하나의 정점에서 출발하였을 때 다른 모든 정점으로의 최단 경로를 구한다. 1을 기준으로 잡고 최단 경로를 구한다고 할 때, 4의 경우 1 -> 4로 가는 비용보다 1 -> 3 -> 4로 가는 비용이 더 적기 때문에 더 적은 비용을 갱신할 수 있다. 구현 방법 BFS와 유사한 형태로, 시작점에서 가까운 순서대로 정점을 방문한다. 가중치가 있는 그래프에서는 BFS를 그대로 적용하기 어렵기 때문에 우선순위큐를 사용하여 해결한다. 각 정점까지의 최단 거리를 저장하는 배열 dp[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사한다. 간선 (u, v)를 검사한다고하면 u까지의 최단 거리에 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾는다...

문제링크 📝 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장..

Deque란? 스택(Stack) 자료구조의 하나로서 후입선출(Last In First Out)를 의미한다. 자바에서는 Stack을 class 형태로 지원해주고 있다 큐(Queue) Queue의 경우는 선입선출(First In First Out)를 의미한다. 자바에서 Queue는 인터페이스로 구현이 되어 있어 보통 LinkedList를 사용해서 구현하곤 한다. 덱, 데크(Deque) 자바 1.6부터 지원하게 된 Deque는 Queue 인터페이스를 확장하여 만든 인터페이스이다. 덱은 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 넣고 뺄 수 있는 자료구조이다. 하나의 자료구조에 Queue와 Stack을 합쳐놓은 형태라고 생각하면 된다. 인덱스를 통해 검색, 추가, 삭제가 불가능하다. D..

관계의 정의 관계 (Relationship) : 엔터티의 인스턴스 사이의 논리적인 연관성으로써 존재의 형태로써나 행위로써 서로에게 연관성이 부여된 상태 관계는 엔터티와 엔터티간 연관성을 표현하기 때문에 엔터티의 정의에 따라 영향을 받기도 하고, 속성 정의 및 관계 정의에 따라서도 다양하게 변할 수 있다. 관계 페어링 관계는 엔터티 안의 인스턴스가 개별적으로 관계를 가지는 것(페어링)이고, 이것의 집합을 관계로 표현한다는 것이다. 따라서 개별 인스턴스가 각각 다른 종류의 관계를 가지고 있다면 두 엔터티 사이에 두 개 이상의 관계가 형성될 수 있다. 관계의 분류 어떤 목적으로 연결되었는지에 따른 두 가지 분류 존재의 의한 관계 : 부서 - 사원 (사원은 부서에 항상 소속되어 있다.) 행위에 의한 관계 : 고..

문제링크 📝 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아..