Algorithm

모든 노드 쌍 사이의 최단 거리를 구하는 알고리즘음의 가중치가 있어도 동작하지만, 음의 사이클이 있으면 안 된다!한 정점에서 다른 모든 정점까지 -> 다익스트라, 벨만-포드모든 정점 쌍에 대해 -> 플로이드-와샬플로이드-와샬은 다이나믹 프로그래밍 기반으로,노드 i에서

\[12906번: A와 B]처음 문제를 보고 T의 끝 문자만 보면 되겠다 생각했다.A이면 그냥 제거하면 되고, B이면 제거 후 역전하면 된다.그래서 제거가 편하도록 Stack을 사용하면 되나? 싶었지만, 문자열을 뒤집을 마땅한 방법이 떠오르지 않았다.Stack이 아니

\[2170: 선 긋기]LinkedList를 사용해야 하나? 주어진 선 범위는 visited 체크를 해야하나? 가 처음에 든 생각이다. 하지만 잘 생각해보면 전체 범위에 해당하는 배열을 만들어 선분을 표시하는 방식은 비효율적이다.문제의 핵심은 겹치는 구간을 잘 처리해서

\[9205번: 맥주 마시면서 걸어가기]주어진 좌표 외의 공간은 고려하지 않아도 된다려하지 않아도 된다. 거리가 1000m 이내인 좌표를 양방향으로 연결하여 펜타포트까지 갈 수 있는지 확인하면 된다.ArrayList A에 주어진 좌표들을 저장한다.모든 좌표를 돌며 연결

📌 문제 정보 [2141번: 우체국] 💡 접근 방식 위치와 인구 수를 저장하는 TreeMap을 만들고, 전체 탐색을 하면서 해당 위치에서의 이동 인구수와 위치를 저장하는 TreeMap을 만들었다. 결과는 시간초과~! 찾아야 하는 것은 사람들이 가장 적게 걸어야

\[1956번: 운동]플로이드 와샬 알고리즘을 사용하면 된다.overflow 방지를 위해 비용이 INF인지 체크도 해주자.그리고, 사이클을 구해야 하니 답을 구할 땐 (i, j) + (j, i)를 해야한다.첨에 (i,i)로만 생각했다가 틀렸다 ㅋㅋ🔍 주요 코드 설명:

\[1149번: RPG거리]i번째 집을 칠하는 최소 비용은현재 색 비용 + (i-1)번째 집을 다른 두 색 중 최소 비용으로 칠한 값앞에서 계산 값들을 테이블에 저장하여 현재 값을 계산해나가면 된다.점화식만 잘 세우면 간단한 문제이다~이 문제도 전에 시도했다가 포기했었

\[1932번: 정수 삼각형]dp 배열을 만들어, Bottom-Up 방식으로 풀어나가면 된다.i층 j번 숫자는i+1층 j번(left)으로 내려가거나i+1층 j+1번(right)으로 내려갈 수 있다.따라서, i층 j번까지의 누적합을 기준으로 다음 층의 left와 righ

\[1717번: 집합의 표현]같은 집합에 속한다라는 의미를 정리해보겠다.유니온0 1 2 -> 1과 2는 같은 집합0 2 3 -> 1, 2, 3은 같은 집합0 4 5 -> 4, 5는 같은 집합 ( 1, 2, 3 집합과는 별개 )set0 1 2 -> 1과 2는 같은 집합0

\[Lv3. 등굣길]이 문제는 목적지까지의 최소 거리를 구하는 것이 아니다! (당연함)물 웅덩이를 제외한 매 칸까지 도달하는 경우의 수를 누적해서 계산해야 한다.boardn+1 배열을 생성한다. board1은 출발점이니 1로 설정하고, 물이 있는 곳은 -1로 둔다.이동

\[Lv3. 아이템줍기]좌표를 2배로 늘려서 생각한다.정수 좌표를 다룰 때, 코너링을 처리하기 위해서는 좌표를 2배로 늘려서 풀어야 한다!무슨 말이냐면,, ㄷ자로 된 길이 있다고 생각해보자. 우측 아래에서 출발한다고 가정하면좌 -> 상 -> 우가 당연한 루트로 보이겠지

\[1717번: 집합의 표현]퀸은 수평, 수직, 대각선으로 이동 가능하다.N x N 체스판에 퀸을 N개를 두려면 한 행에 하나씩은 들어가야 한다.한 행마다 하나의 퀸을 놓는 방식으로 진행하면 수평 체크는 따로 진행할 것 없이 수직과 대각선만 확인하면 된다.수직은 간단히

\[2660: 회장뽑기]예제 입력을 보고 표를 짜보면 이렇게 된다.최종적으로 1번의 점수는 3점이고, 2~4번의 점수는 2점, 5번의 점수는 3점이라회장 후보는 2, 3, 4이다.즉, 각 회원과의 최단 거리를 구한 후 최대 거리가 최소인 사람을 찾는 문제이다...회원들

\[1074: Z]일단 헷갈리니까 좌표를 1부터 시작하게 했다.좌표 범위를 4등분하면서, 찾고자 하는 위치가 어디에 있는지를 찾아야 한다.1번이면 카운트를 유지하고2번이면 1번 칸 수만큼 더한다.3번이면 1번 + 2번 칸 수만큼 더하고4번이면 1번 + 2번 + 3번 칸

\[Lv2. 두 큐 합 같게 만들기]두 큐를 연결해서 하나의 배열로 합친다.슬라이딩 윈도우처럼 합을 조절하면 된다.sum1의 범위를 조절해서 (sum1 + sum2) / 2를 맞춰간다.sum1 > half 이면 left++sum1 < half 이면

\[18870: 좌표 압축]단순히 나보다 작은 수가 몇 개 있는지 찾으면 되는 문제이다.처음엔 원본 배열과 정렬된 배열을 따로 만들어서 mputIfAbsent로 중복 처리 해서 map에 저장하도록 풀었다. 그런데 단순히 정렬만 하면 같은 값이 배열에 남아 있어서 좌표

\[Lv3. 봉인된 주문]찾고자 하는 위치(n)의 주문보다 앞에 있는 삭제된 주문의 수 만큼 n에 더해주면 된다.삭제된 주문 배열 정렬배열 돌면서 문자열을 숫자로 변환해당 숫자가 n보다 작거나 같다면 n++n보다 크다면 n을 다시 문자열로 변환배열을 모두 숫자로 바꾸고

\[2156: 포도주 시식]연속으로 3개를 마실 수 없다.이때 i번째 포도주를 마시는 경우의 수는 3가지 이다.i-1번 안 마시고, i번 마시기 -> dp\[i-2] + wine\[i]i-2번 안 마시고, i-1번, i번 마시기 -> dp\[i-3] + wine\[i-

\[5430: AC]배열 자체를 ‘R’ 연산이 주어질 때마다 뒤집으면 백퍼 시간초과가 날 것 같아서R 상태에 따른 D 횟수를 카운트 했다.1\. R이 짝수번 등장했으면 원본 배열 상태 → D 등장 시 front_del++2\. R이 홀수번 등장했으면 뒤집힌 상태 → D