알고리즘

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.첫째 줄과 둘째 줄에 두 문자

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로

문제 https://www.acmicpc.net/problem/1786 문자열 T에 문자열 P가 몇 번 나오는지 출력 문자열 P가 문자열 T의 몇 번째 인덱스에 나오는지 나열 간단하게 말해서 이 두 가지를 구하는 문제이다. 접근 이 문제를 브루트 포스하게 풀게 되

https://www.acmicpc.net/problem/2206N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데,

https://www.acmicpc.net/problem/2042어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부

수식이 주어졌을 때, +, -, \* 의 우선순위를 재정의하고 그 우선순위를 통해 계산했을 때 결과값의 절대값이 가장 큰 값을 구하는 문제이다.(단, +, - > \* 와 같이 두 부호의 우선순위가 같을 수는 없다.)100-200\*300-500+2060420우선, 이

두 개의 단어 begin, target과 단어의 집합 words가 있을 때 begin = "hit"target = "cog"words = \["hot","dot","dog","lot","log","cog"]"hit" -> "hot" -> "dot" -> "dog" ->

https://www.acmicpc.net/problem/9205송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한

https://programmers.co.kr/learn/courses/30/lessons/129851번~8번 참가자가 있다고 가정해보자. (N=8)1번 참가자 vs 2번 참가자3번 참가자 vs 4번 참가자5번 참가자 vs 6번 참가자7번 참가자 vs 8번 참

https://programmers.co.kr/learn/courses/30/lessons/42577솔직히 단순하게 전부 돌려가면서 비교하는 방법이 먼저 생각났는데, O(n^2)의 시간복잡도록 시간초과가 날 것 같아 다른 방법을 생각하게 되었다.문자열 첫 글자

https://www.acmicpc.net/problem/1697처음에는 DFS를 먼저 떠올렸지만 풀다보니 어디서 멈춰야 할지? 과연 이 길을 통해 최적의 경로를 찾을 수 있을지 애매하다고 느껴 결국 BFS로 접근하여 풀게 되었다. 문제 자체는 어렵지는 않지만

https://www.acmicpc.net/problem/16198처음에는 곱한 에너지의 크기가 큰 순으로 정렬하는 우선순위 큐를 하나 만드는 쪽으로 접근을 하였다. 처음에 짠 코드는 다음과 같다.예제는 다 정답을 출력하였지만 제출하자마자 틀렸다고 떴다. 곰곰

https://www.acmicpc.net/problem/1965처음에는 단순히 모든 값을 탐색하면 해결될 줄 알아서 단순히 재귀로 해결하려고 했다.결과는... 시간초과다.재귀로 풀었는데 시간초과라면 십중팔구 dp문제다. (적어도 본인 경험으로는)생각해보니 앞

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 같습니다.▲ - 다음 알파벳▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)◀ -

문제 https://programmers.co.kr/learn/courses/30/lessons/72413 접근 1. 다익스트라 (오답) 처음에는 문제를 보자마자 다익스트라가 먼저 떠올랐다. 시작점도 주어졌고, 최소 비용을 구하는 문제였기 때문이다. 과정은 다음과 같

문제 자체가 어려운 것은 아니었지만 자잘한 실수가 많아 기록하게 되었다.https://www.acmicpc.net/problem/15686순열 조합 및 BFS로 접근하게 되었다.순열 조합 : 폐업시킬 치킨집의 경우의 수BFS : 각 집에서 치킨집까지의 최단 거

https://programmers.co.kr/learn/courses/30/lessons/17683단순히 문자열을 다루는 문제라서 그런지 어렵지는 않았다. 다만, 생각해야 하는 테스트케이스가 좀 있었다.

https://www.acmicpc.net/problem/2800처음에는 단순히 왼쪽 괄호가 몇 개 나오는지를 재귀함수의 파라미터로 두는 방향으로 접근했지만 생각대로 잘 풀리지 않았다. 결국 힌트를 살짝 얻었는데, 본인이 생각했던 방향과 가장 큰 차이점은 아래

https://programmers.co.kr/learn/courses/30/lessons/62050제약사항 중 입력 최대 크기가 300 \* 300 = 90000이다. DFS로는 재귀의 깊이가 너무 깊어질 것으로 예상되어 BFS로 풀게 되었다.처음에는 단순히

https://programmers.co.kr/learn/courses/30/lessons/68645?language=java규칙이 있을 것이라고 생각하고 문제를 접근하게 되었다. 약간 큰 정삼각형을 그렸을 때 그 규칙을 찾아낼 수 있었다.ex) n = 8 (

https://programmers.co.kr/learn/courses/30/lessons/42627일단 최대한 비는 시간을 만들면 안되며 소요 시간이 가장 짧은 작업을 먼저 수행해야 한다고 생각했다. 요청 시간과 소요 시간 둘 다 정렬 기준이 될 수 있을 것

문제 https://programmers.co.kr/learn/courses/30/lessons/12979 접근 처음에 기지국의 영향을 받는 시작점과 끝점을 담은 Node에 대한 배열을 만들고 이를 오름차순으로 정렬하였다. 그리고 그 배열을 처음부터 탐색해서 기지국의

문제 https://programmers.co.kr/learn/courses/30/lessons/17678?language=java 풀이 먼저 셔틀버스 시간표를 만들어준다. 09시부터 t분 간격으로 n회 배치하면 된다. t분씩 더해주다가 분(minute)단위가 60이

https://www.acmicpc.net/problem/12100보드의 크기 N은 1 ≤ N ≤ 20이며 최대 5번 이동이라는 제약으로 인해 dfs로 풀어도 시간초과가 나지 않겠다는 생각을 하였다. 정해진 방향으로 숫자가 모두 밀렸을 때를 리스트에 대한 배열

https://programmers.co.kr/learn/courses/30/lessons/12936단순히 완전 탐색을 이용하였으나, 시간초과가 났다.거의 비슷하게 접근했었는데, 한 가지 간과한 점이 있었다. 반례를 찾으면서도 앞뒤가 안맞는다고 생각되는 요인

https://level.goorm.io/exam/51356/ab%EB%A5%BC-bba%EB%A1%9C/quiz/1처음에는 스택 두 개를 두고 푸는 방법을 생각했다. 특정 위치의 문자가 'b'일 경우 그 전의 문자가 무엇이었는지 스택의 top을 통해 알아내는

https://programmers.co.kr/learn/courses/30/lessons/81303?language=java인덱스만 좀 조심해서 구현하면 되는 문제같다. 처음에 단순히 ArrayList를 사용하여 풀어서 정확성 측면에서는 통과했지만, 효율성

https://programmers.co.kr/learn/courses/30/lessons/86052우선, 회전에 이용할 dx, dy 배열을 만들어줘야 한다. 단, 시계 방향으로 정해줘야 나중에 구현하기 편해진다. 본인은 다음과 같이 정의하였다.본인은 다음과

문제 https://www.acmicpc.net/problem/6091 접근 한참 고민하다가 정점 A에서 정점 B로 가는 비용이 작다는 것은 인접해있을 확률이 높다고 생각하고 비용 순서대로 우선순위 큐를 정의하였다. 그리고 우선순위 큐에서 하나씩 간선에 대한 정보를

https://programmers.co.kr/learn/courses/30/lessons/12905처음에 특정 지점에서 모두 1로 구성된 정사각형 영역을 계속 구하자니, 반복적으로 탐색해야 한다는 점을 눈치채고 dp 문제라고 생각하였다.방법은 간단하다.현재

https://leetcode.com/problems/jump-game-iv/처음에는 재귀함수를 사용하는 방법을 생각하고 이렇게 코드를 짰었다.다음과 같은 테스트케이스가 들어온다면?\[7, 7, 7, ... 7] <- arr.length = 3000재귀함