코딩테스트

1. 문제https://www.acmicpc.net/problem/18352  2. 문제풀이 전략해당 문제는 BFS로도 해결 가능하지만,가중치가 있는 그래프의 일반적인 경우를 고려하면 다익스트라 알고리즘이 훨씬 더 범용적인 해결책이 된다.따라서, 다익스트라 알고리즘을 활용해서 이 문제를 풀어보겠다. 3. 다익스트라(Dijkstra) 알고리즘이란?다익스트라(Dijkstra) 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 특히 음의 가중치가 없는 그래프에서 사용된다. 참고로, 음의 가중치를 가진 간선이 있는 그래프에서 최단 경로를 찾아야 한다면 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 한다. 4. 우선순위 큐를 사용 - 시간 복잡도 O(E logV)E는 간선..

https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. Heap힙은 완전 이진 트리를 기반으로 한 자료구조로, 최댓값 또는 최솟값을 빠르게 찾아내는 데 유용하다. 힙의 주요 특징완전 이진 트리부모 노드와 자식 노드 간에 특정한 순서가 있다.중복된 값을 허용한다.형제 노드 간에는 순서가 정해지지 않는다. 2. Max Heap과 Min Heap의 차이2 - 1. Max Heap(최대 힙)부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다.루트 노드에 최댓값이 위치한다. 2 - 2. Min H..

1. 오늘의 문제 - 촌수 계산 - 백준 : 2644번https://www.acmicpc.net/problem/2644  2. 문제 풀이 전략DFS로 그래프 탐색을 하면 될 것 같고,양방향 그래프이고,사람들이 100명뿐이 안되니까 인접행렬 사용하면 될 것 같다. 3. 풀이package io.conduktor.demos.dfsbfs.hanghaecote99.middler;import java.io.*;import java.util.StringTokenizer;// 8. 촌수 계산 - 백준 : 2644 - DFS, BFSpublic class ChonNumber8 { static int N; static int targetA; static int targetB; static int M;..

1. 오늘의 문제 - 모음 사전 : 프로그래머스 (Level 2)https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  2. 문제 풀이 전략DFS로 만들 수 있는 단어를 전부 만든다.몇 번째로 만들어진 단어인지 확인한다.3. 풀이package io.conduktor.demos.dfsbfs.hanghaecote99.middler;import java.util.ArrayList;import java.util.List;// 7. 프로그래머스 - 모음 사전 - 그래프 이론public class Vowel..

1. 오늘의 문제 - 나무 자르기 - 백준 : 2805https://www.acmicpc.net/problem/2805 이분탐색!지금까지 갈고 닦은 이분탐색 실력을 뽐낼 시간이로군 2. 문제 풀이 전략이건 그냥 이분탐색만 알고 알고 있으면 간단히 해결될 것 같다. 3. 난관 봉착... 예제 입력을 넣었을 때 출력이 제대로 안 나옴근데 왜 첫 번째 예제 입력시 출력으로 15가 나와야 하는데 13이 나오는걸까? 두 번째 예제도 마찬가지. 36이 나와야 하는데 27이 나온다. 내가 작성한 로직은 아래와 같다.int result = 0;int left = 0;int right = 1000000000;while (left = M) { result = mid; left = mid + 1; ..

1. 오늘의 문제 - 알고리즘 수업 - 너비 우선 탐색 1 - 백준 : 24444번https://www.acmicpc.net/problem/24444  이름부터가 BFS로 풀라고 떠먹여준다.BFS는 참 좋다.공식만 알고 있으면 되니까.문제에서 친절하게 공식도 알려준다.2. 문제 풀이 전략2 - 1. 인접리스트로 접근정점수가 100,000 개이므로, 인접행렬로 그래프를 표현하면 메모리초과가 발생할 것이다.인접리스트로 그래프를 표현하자.// static int[][] adjMatrix; // 인접 행렬 안됩니다!static List> adjList; 2 - 2. 정렬예시의 입력을 살펴보면, 1번 정점과 4번 정점이 연결 되고, 1번 정점과 2번 정점이 연결 된다.결과적으로, 1번 정점과 연결된 정점들은 [..

1. 오늘의 문제 - 알고리즘 수업 - 깊이 우선 탐색 1 - 백준 24479번https://www.acmicpc.net/problem/24479 1년 전에 풀었던 문제가 나왔네?다시 한 번 풀어보자.다시 풀어봤는데, 첫 번째, 두 번째 제출은 틀렸고, 세 번째 만에 맞췄다.2. 문제 풀이 전략2 - 1. 인접리스트로 접근일단 정점수가 100,000이다.인접행렬로 풀 경우, 100,000 * 100,000 이니까 공간 복잡도가 어마어마해진다.정점수가 적을 때는 인접행렬로 풀어도 되지만, 이런 경우 인접리스트로 풀어야 시간초과가 안 난다.static List> adjList;2 - 2. 정렬예시의 입력을 살펴보면, 1과 4가 연결, 1과 2가 연결순으로 제시된다.1번과 연결된 놈들이  [4, 2] 가 되는..

1. 오늘의 문제 - 입국심사https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 입국심사를 받을 사람 n명이 주어지고, 각 입국 심사관의 심사 시간이 배열로 주어진다.가령, n = 6, times = [7, 10] 으로 주어진다면입국심사를 받을 사람은 6명이고, 입국 심사관은 2명이고, 각각 7분, 10분이 걸린다는 의미다.자세한 제한사항은 링크를 통해서 확인하도록 하고... 2. 문제풀이 전략2 - 1. times 배열 정렬입국 심사관의 심사 시간 배열은 정렬되어 주어지지 않는다. 일단 정렬한..