반응형 알고리즘 PS113 온라인 코딩 테스트의 사전준비 1. 연습장과 필기 도구 재귀 구조를 구현할 때 머릿속으로만 구조를 그려내면 실수하기가 쉽다. 처음부터 연습장에 값의 변화나 최종 결과를 기록하고 머릿속에 떠올린 구조와 비교하면서 풀이해나가자. 2. 자신만의 코드 스니펫 준비 코딩테스트 시 자주 쓰이는 동작들에 대해 코드 스니펫을 미리 만들어 두면 도움이 된다. 예를 들어 연결리스트를 뒤집거나 삭제하는 등의 작업들은 갑자기 구현하려면 헷갈리기도 하고 시간이 걸리는데, 이런 작업에 대한 코드를 미리 만들어두면 좋다. 3. 모든 테스트 케이스를 통과하도록 풀어야 코딩 테스트 시에는 충분히 생각하고 문제가 없는지 코드를 다시 한번 더 꼼꼼히 확인 후에 제출하는 편이 유리하다. 실무에서처럼 일단 돌아가는 코드를 제출하고 테스트를 지속적으로 돌려보면서 오류를 수.. 2022. 9. 17. [백준] 1753번 - 최단경로 (Java) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 다익스트라 알고리즘을 사용 2. 정점은 인접행렬로 구성하고, 방향이 있는 그래프이니 s -> e만 배열에 저장할 것. import java.util.*; /* [백준] 1753번 - 최단경로 (Java) */ public class Main { static int V, E, K; static int[][] map; static int[] visited; .. 2022. 9. 14. [백준] 2839번 - 설탕 배달 (Java) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 재귀나 반복문으로 푸는 문제가 아니다. 따라서 수들을 늘어서놓고 법칙을 찾아야 한다. N 3 4 5 6 7 8 9 10 11 12 봉지수 1 2 N / 5 1 2 N % 5 3 4 0 1 2 3 4 0 1 2 N 13 14 15 16 17 18 19 봉지수 3 N / 5 2 3 N % 5 3 4 0 1 2 3 4 1. 법칙성을 찾기 위해 N/5와 N%5의 값들을 구해본다. N 3 4 5 6 7 8 9 10 .. 2022. 9. 14. [백준] 1707번 - 이분 그래프 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 먼저 이분그래프에 대해 알아보자. 2. 인접한 정점은 다른 색상으로 저장하자. (1 or 2) 3. 방문하려는데 동일한 색상이 이미 칠해져 있으면 이분그래프가 아니다. 4. DFS(정점번호, 색상)을 넘겨주자. import java.util.*; /* [백준] 1707번 - 이분 그래프 (Java) */ public class Main { static int K, V, E; static in.. 2022. 9. 13. [백준] 7562번 - 나이트의 이동 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. BFS 탐색으로 최소이동거리를 구하는 문제이다. 2. TC가 여러개이므로 매번 맵을 초기화 해야 한다. 3. 누적거리는 map[][]에 탐색하면서 업데이트 한다. 4. 8방향으로 탐색이 가능하다. import java.util.*; /* [백준] 7562번 - 나이트의 이동 (Java) */ public class Main { static int N, M; static int map[][];.. 2022. 9. 13. [백준] 14502번 - 연구소 (Java)(△) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다. 2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다. 2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자. 3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수) 3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가.. 2022. 9. 12. [백준] 1697번 - 숨바꼭질 (Java) https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 1차원 그래프이다. 2. N의 위치에서 할 수 있는 액션은 3개이다. 2-1. nx = 2 * x 2-2. nx = x+1 2-3. nx = x - 1 3. BFS로 위 3개 액션을 for(1 to 3)문으로 돌려서 탐색한다. 4. 방문거리는 visited 배열에다가 이전거리+1을 해서 기록하고, 방문한 노드는 스킵한다. 5. N과 K가 같을 때 BFS 수행 전에 .. 2022. 9. 8. [백준] 1520번 - 내리막 길 (Java) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. map에는 높이 정보가 주어지고, 탐색은 상하좌우로만 가능하다. 2. 경로를 찾는데 높이가 지금보다 낮은 쪽으로만 이동 가능한 경로를 찾는다. 3. 가능한 경로의 개수를 찾는다. 4. dfs 파라메터로 좌표 정보를 넘겨준다. import java.util.*; /* [백준] 1520번 - 내리막 길 (Java) */ public class Main { int N, M; int A[][]; bool.. 2022. 9. 7. [백준] 7576번 - 토마토 (Java) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 익은 토마토는 1, 안익은 토마토는 0, 빈칸은 -1로 주어진다. 2. 익은 토마토의 상하좌우로 영향을 줘서 안익은 토마토가 하루가 지나면 익게 된다. 3. bfs 탐색으로 상하좌우로 탐색할 때 0이면 1로 바꾸고 탐색을 계속한다. 3-1. 상하좌우 검색 후에 누적거리+1 을 하자. 4. 출발점이 없으니 메인함수에서 for문을 돌려서 1이 나오면 bfs를 호출하자. 5. 0이.. 2022. 9. 7. 이전 1 ··· 8 9 10 11 12 13 다음 반응형
