백준

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. 오늘의 문제 - 나무 자르기 - 백준 : 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. 오늘의 문제 - 징검다리 : 백준 11561번https://www.acmicpc.net/problem/11561 2. 공부한 내용2 - 1. 규칙 찾기 시도징검다리가 1개일 때는 최대 징검다리수 는 몇 개 일까?2개일 때는? 10개 일때는? 규칙을 찾으려고 노력했다. 2 - 2. 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야1이상 점프해야 한다는 제약 조건은 무엇을 의미할까?최대한 많은 징검다리를 밟는 걸 찾는 문제다그러면 정확하게 1칸 뛰고 2칸 뛰고 3칸 뛰는 게 최대한 많은 징검 다리를 밟는 경우의 수일 것이다.1 이상 뛸 수 있다고해서 처음에 5칸 뛰고 그 다음 7칸 뛰고 그다음 13칸 뛰면 최댓값이 아닐 것이다. 아주 당연하다. 2 - 3. 등차수열의 합최선의 경우가 1, 2, 3,..