내가보려고만든 메자노트

(정점=노드 같은 뜻! 혼용해서 사용할 시 혼동 방지!) 그래프에서 각 정점끼리 사이의 최단 거리를 구하는 알고리즘 방법은 여러 가지가 있다. 문제에 따라 효율적인 방법이 다르므로 잘 선택해서 사용해야 한다. 문제의 종류 하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 각 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 응용으로 한 중간 정점을 거쳐서 가는 최단경로 등 다양한 문제의 종류에 적용하여 사용할 수 있다. 알고리즘 종류 하나의 정점에서 다른 모든 정점까지 최단경로를 구하는 문제 -간선의 가중치가 모두 같은 그래프일 경우 BFS -간선의 가중치가 각각 다른 그래프일 경우 다익스트라 벨만-포드 → 음수 가중치..

문제 보러 가기 이 문제는 정확도와 효율성 2가지를 만족해야 하는 문제였다. 행 개수 n 0) { curNode = curNode.next; } for (int i = 0; i < cmd.length; i++) { String[] s = cmd[i].split(" "); if (s.length == 1) { if (s[0].equals("C")) {//삭제C curNode.prev.next = curNode.next; curNode.next.prev = curNode.prev; zNode.push(curNode); //root가 삭제될경우 next노드가 root노드가됨 if (curNode == root) { root = curNode.next; curNode = root; } //tail노드가 삭제될 ..

DP란? 부분 문제의 결과 값을 이용해 전체 문제를 풀어나가는 알고리즘 방법이다. 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제 (overlapping subproblems)라고 한다. 이를 한 번만 계산하여 저장하고 다음에는 이 결괏값을 이용해서 풀이하면 된다. 메모이제이션(Memoization) 이미 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션(Memoization)이라 한다. 1) 특정 함수가 호출되었을 때, 배열에 해당 값이 저장되어 있는지 확인. 존재한다면, 해당 값을 return. 2) 존재하지 않는다면, 값을 계산하고 배열에 저장한 뒤 해당 값을 return. - 메모이제이션은 입력이 고정되어 있을 때, 그 결과가 항상 같은 함수, 참조적 투명 함수(referent..

문제 보러 가기 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 이 문제는 MST(최소 신장(스패닝) 트리)를 이용하여 풀 수 있었다. 크루스 칼, 프림 두 개의 알고리즘으로 풀이가 가능했고 나의 경우 프림 알고리즘으로 풀었다. 문제풀이 2개의 도시로 분할해야 하므로 프림 알고리즘을 통해 MST를 만든 후 가장 비용이 높은 간선 하나를 제거하면 2개의 도시로 나눠지고 최소 비용을 구할 수 있다. - 임의의 시작 노드를 Queue에 넣고 연결된 NodeList를 Priori..

문제 보러 가기 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 이 문제는 유니온 파인드를 이용해 풀이할 수 있는 문제였다. 유니온 파인드를 이렇게 사용할 수 있다는 걸 알았던 문제. 문제풀이 - G개의 게이트 P개의 비행기가 주어질 때 첫 번째 비행기가 아래와 같이 2번 게이트에 도착하게 된다 -조건 1. 각 게이트당 한 개의 비행기만 도착하여 도킹할 수 있음 2. 1~gi의 게이트에 도킹이 가능 ex) 3번 게이트에 도착한다면 1,2,3번 게이트에 도킹 가능 - 이미 2번 ..

문제 보러 가기 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 이 문제는 예전에 풀려다가 실패하고 까먹었었던 문제인데 이번에 다시 풀어보았다. bfs 탐색을 하며 빨간 구슬 R이 구멍이 O에 들어갈 수 있는지 확인하는 문제이다. * 놓칠 수 있는 조건들 1. 10번 이상 움직여야 하는 경우 구슬을 탈출시킬 수 없다고 판단. -1을 return 해야 함 2. 구슬의 위치를 바꿨다면 이전 구슬의 위치는 삭제 후 탐색해야 함 3. 구슬 두 개의 위치로 방문 체크를 ..

문제 보러 가기 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 이 문제는 익숙한 게임을 이용한 문제이다. 아래의 규칙을 통해 게임이 몇 초동안 지속될 수 있는지를 구하면 된다. 문제풀이 -map [][]에서 사과가 있는 인덱스는 1로 , 뱀이 위치하는 부분은 2로 기록한다. - Deque snake에 뱀의 위치를 기록한다. -> 사과를 먹으면 사과를 먹은 머리 부분이 늘어남 => addFirst() -> 사과가 없다면 꼬리 부분이 줄어듦 => pollLast() -뱀이 사과를 먹으면 해당부분은 뱀이 위치하므로 ->..

* COUNT() : SQL에서 사용되는 집계 함수로 행의 개수를 출력하는 데에 사용된다. ※ COUNT 외 집계 함수로는 SUM, AVG, MIN, MAX 등이 있다. - 전체 행의 개수 SELECT COUNT(*) FROM TABLE_NAME : 이 결과에는 NULL이 포함되어서 세어진다. - NULL을 포함하지 않는 행의 개수 SELECT COUNT(COLUMN_NAME) FROM TABLE_NAME : 칼럼의 이름을 사용하면 그 칼럼의 NULL인 값을 제외한 개수가 반환된다. - 중복 값을 제외한 행의 개수 SELECT COUNT(DISTINCT COLUMN_NAME) FROM TABLE_NAME - 값을 치환하여 구하기 SELECT COUNT(IFNULL(COLUMN_NAME,0)) FROM T..