나의개발일지

https://www.acmicpc.net/problem/1022 사용 알고리즘구현 아이디어1. 주어진 입력 값의 시작점을 0, 0으로 옮기고, 이 크기의 배열 arr을 생성한다.2. 이를 기준으로 했을 때 0, 0 지점 (-r1, -c1)부터 1을 소용돌이 모양으로 채운다.3. dx, dy 배열로 우/상/좌/하 방향으로 이동할 수 있도록 한다.4. 이때, 같은 방향으로 1, 2, 3, ... 씩 증가하며 움직이는 게 2번씩 반복된다.(즉, 우 -> 상 -> 좌 -> 좌 -> 하 -> 하 -> 우 -> 우 -> 우 -> 상 -> 상 -> 상 -> ... 식으로 늘어나는 규칙의 코드를 반복문으로 짜야 함)5. 이동할 때 주어진 arr 배열 범위 밖이면 무시, 범위 안이면 배열에 값을 저장한다.6. 이를 길..

https://www.acmicpc.net/problem/9663 사용 알고리즘DFS, 백트래킹 아이디어1. 행을 DFS로 하나씩 올려가면서2. 열과 대각선 확인3. 마지막 행까지 왔을 때 + 1한 개수를 최종 출력 유의점1. 서로 공격할 수 있는 경우는 같은 행 / 같은 열 / 같은 대각선에 위치할 때이다. 제출코드package BOJ.Graph.DFS;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class BOJ_9663_NQueen { static int n; static int ans; static int[] visited; public static..

https://www.acmicpc.net/problem/1865 사용 알고리즘벨만-포드 아이디어1. 웜홀은 음의 간선치2. 간선 수(N-1) 만큼 거리의 최솟값 구하기3. N번째 최솟값에 변동이 생기면 음의 사이클 -> 시간이 되돌아감 유의점1. 모든 지점이 연결되어 있지 않을 수 있음. 가상의 지점 0에서 각 지점으로 모두 가중치 0으로 연결시키기 제출코드package BOJ.Graph.BellmanFord;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;imp..

https://www.acmicpc.net/problem/1504 사용 알고리즘다익스트라 아이디어1. 각 회선별 최단거리 계산 (다익스트라)2. v1, v2를 지나야 하므로 1 -> v1 -> v2 -> n 또는 1 -> v2 -> v1 -> n 인 경우 최단거리를 구한다. 유의점1. v1, v2 지나는 지 확인해서 마지막 노드에 저장하려 했으나, 무조건 최단 경로의 값을 저장해 이동하려는 문제가 발생했다.   -> 이 경우에는 경로를 쪼개서 1 -> a -> b -> n 각각의 경우의 최단거리를 계산하자!2. dist[]의 초기값이 Integer.MAX_VALUE;로 되어 있다보니, 거리를 합하면서 오버플로우가 발생했다. -> (long) 형변환 제출코드package BOJ.Graph.Dijkstra;..

https://www.acmicpc.net/problem/2470 사용 알고리즘투 포인터 아이디어1. 배열 정렬2. 두 용액의 합이 음수일 때는 s++;, 양수일 때는 e--;로 범위 좁히기3. 음수일 때, sum의 절댓값이 0에 가까워지는 수로 갱신하고, 양수일 때 sum이 0에 가까워지는 수로 갱신 유의점1. 절댓값 처리를 잘못해서 디버깅하다가 헷갈림; 주석으로 한번 잘 장리해두고 적자.. 제출코드package BOJ.BinarySearch;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;..

https://www.acmicpc.net/problem/1253 사용 알고리즘투 포인터 아이디어1. 배열 정렬2. 모든 각각의 수에 대해 투포인터 탐색3. s, e가 현재 탐색하는 수인 경우 제외하고4. 좋다를 만족하는 수면 cnt++5. s, e의 합이 탐색하는 수보다 작으면 s++;, 크면 e--; 유의점1. s, e가 현재 탐색하는 수인 경우 제외 조건을 걸지 않아서 틀렸었음,, (s == i 면 s++;, e == i 면 e--;) 제출코드package BOJ.BinarySearch;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import..

https://www.acmicpc.net/problem/2211 사용 알고리즘다익스트라 아이디어1. 각 회선별 최단거리 계산 (다익스트라)2. 최단거리로 갱신될 때 각 현재 컴퓨터로 들어오는 컴퓨터의 번화 저장 유의점- 처음에 우선순위 큐에 방문할 노드를 넣고 방문처리를 해서,, 더 짧은 거리를 가지는 회선 탐색을 못함,,  -> 모든 인접 노드를 탐색한 후 해당 노드를 시작으로 하는 노드일 때 방문처리 제출코드package BOJ.Graph.Dijkstra;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ_2211_네트워크복구 ..

https://www.acmicpc.net/problem/11657 사용 알고리즘벨만-포드 아이디어1. 노드가 n개 일때 간선은 n-1개2. n-1번 돌면서 최단거리 계산3. n번째에서 최단거리가 변경되면 음의 싸이클 -> return true; 유의점거리를 계산하는 dist[] 배열 : int 값 범위 넘음 (언더플로우) -> long 형 제출코드package BOJ.Graph.BellmanFord;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ_11657_타임머신 { static class Point{ int..

https://www.acmicpc.net/problem/1932 아래층으로 내려갈 땐 지금 당장 값이 작아도 끝까지 도착했을 때의 값이 더 클 수 있다.그럼 반대로 생각해보면 된다!위층으로 올라갈 때 직전 값 중 큰 값을 누적해가면 dp[0][0]이 최댓값이 된다.for(int i=n-1; i>=0; i--){ for(int j=0; j package BOJ.DP;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_1932_정수삼각형 { public static void main(S..

https://www.acmicpc.net/problem/2170 처음엔 pq를 사용했는데 시간초과가 떠서 방법을 변경했다.정렬 후에는 이후 값이 무조건 직전값에 영향을 받을 수 밖에 없기에 그때그때 확장하는 방법이 가능해진다. 1. x값 오름차순 정렬 x값이 같다면, y값 오름차순 정렬2. 만약 다음 값이 이전 값에 걸친다면 끝 좌표만 확장2. 만약 걸치지 않는다면 이전 선의 길이를 계산해 저장한 후, 현재 x, y를 새로운 시작과 끝 값으로 정의3. 마지막 선 길이까지 더한 후 결과 출력 package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..