코딩테스트/백준_Java
-
Q. 4963 자바 : 섬의 개수코딩테스트/백준_Java 2023. 4. 1. 09:51
Q. 4963 자바 : 섬의 개수 문제 : boj.kr/4963 실버 2 난이도의 문제이다. 격자 그래프가 주어졌을 때 이를 DFS, BFS로 순회하고 결과를 출력하는 문제이다. 주의해야 할 점은 순회 방향이 상 하 좌 우 + 대각선을 포함한다 그래서 탐색을 위한 dy, dx의 크기를 8로 늘리고 대각선 4방향을 추가해줬다. 그래프의 크기 W, H가 중지므로 시간복잡도는 아래와 같다. 1. DFS or BFS 순회 - O(W * H) 이 때 W, H의 최대값은 50이므로 시간초과는 걱정하지 않아도 된다. 그래프의 자료형은 boolean 2차원 배열로 해결했다. 풀이는 아래와 같다. import java.io.*; import java.lang.reflect.Array; import java.util.*;..
-
Q. 11724 자바 : 연결 요소의 개수코딩테스트/백준_Java 2023. 3. 31. 23:03
Q. 11724 자바 : 연결 요소의 개수 문제 : boj.kr/11724 실버 2 난이도의 문제이다. 정점의 수와 간선이 주어졌을 때 연결 요소의 수를 계산하는 문제이다. 풀려고 보니 연결 요소가 뭔지 모르겠어서 찾아봤더니, 서로 연결된 정점의 집합을 연결 요소로 이해하면 될 것 같다. 주의해야 할 점은 격자형 그래프 + 양방향 그래프이므로 간선(x, y)을 입력받는다면, 그래프에서는 graph[x][y], graph[y][x] 둘 다 표시를 해야한다. 사실 문제를 풀 때 고민했던 내용이 두가지 있었다. 첫번째는 정점의 수 N이 주어진다고는 써있지만, 이후 조건이 1
-
Q. 1012 자바 : 유기농 배추코딩테스트/백준_Java 2023. 3. 30. 22:49
Q. 1012 자바 : 유기농 배추 문제 : boj.kr/1012실버 2 난이도의 문제이다. 이전 글에서 푼 문제인 단지번호 붙이기와 거의 비슷한 문제이다.배추를 재배하는 땅들의 좌표가 주어진다.배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 될 때,총 몇 마리의 지렁이가 필요한지 계산하는 문제이다. 지도의 크기 M, N이 주어지는데, 격자형 그래프 순회 문제의 경우 모든 점을 순회해야 하므로 시간 복잡도는 O(NM)이고,문제에서N, M의 최대값은 각각 50이므로시간초과는 걱정하지 않아도 된다.또한 입력을 받을 때 자료형은 0과 1로만 구분되므로 boolean을 사용했다. 문제를 푼 방식은1. 탐색이 가능한 경우(arr[y][x] = true) 방문하고, 이후에 탐색을 진행하며 방문 횟수를 저장..
-
Q. 2667 자바 : 단지번호붙이기코딩테스트/백준_Java 2023. 3. 29. 13:35
Q. 2667 자바 : 단지번호붙이기 문제 : boj.kr/2667 실버 1 난이도의 문제이다. 0과 1로 구성된 격자형 그래프가 주어지고, 1(=집을 의미)이 모여 있는 곳을 단지로 정의했을 때, 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제이다. 지도의 크기 N이 주어지는데, 격자형 그래프 순회 문제의 경우 모든 점을 순회해야 하므로 시간 복잡도는 O(N^2)이고,문제에서N의 최대값은 25이므로 시간초과는 걱정하지 않아도 된다. 또한 입력을 받을 때 자료형은 0과 1로만 구분되므로 boolean을 사용했다. 문제를 푼 방식은 1. 탐색이 가능한 경우(arr[y][x] = true) 방문하고, 이후에 탐색을 진행하며 방문 횟수를 저장한다. (이 때 방문한 경우 방문..
-
Q. 1260 자바 : DFS와 BFS코딩테스트/백준_Java 2023. 3. 28. 12:02
Q. 1260 자바 : DFS와 BFS 문제 :boj.kr/1260 실버 2 난이도의 문제이다. 그래프가 주어졌을 때 이를 DFS, BFS로 순회하고 결과를 출력하는 문제이다. 주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 한다는 내용 때문에 그래프를 입력 받은 뒤 정렬이 한번 필요하다. 정점이 N, 간선이 M으로 주어지므로 시간복잡도는 아래와 같다. 1. 모든 정점에 대한 정렬 - O(N * M log M) 2. DFS, BFS 순회 - O(2 * N * M) (ArrayList를 이용한 그래프 탐색의 경우 정점 * 간선 만큼의 시간복잡도를 가짐) 따라서 두 식을 더하면 약 O(N * M) 정도의 시간복잡도를 가진다고 예상할 수 있다. 이 문제의 경우 정..
-
Q. 20366 자바 : 같이 눈사람 만들래?코딩테스트/백준_Java 2023. 3. 27. 22:27
문제 :boj.kr/20366 골드 3 난이도의 문제이다. 투 포인터 강의를 듣고나서, 투 포인터 유형의 다른 문제들을 찾아보다가 발견한 문제이다. 처음에 문제를 봤을 때는 어떻게 접근해야 할 지 감이 안잡혔었는데, 감이 안잡혀서 검색을 했더니, 세 용액 문제와 비슷한, 네 용액 문제로 풀면 된다는 내용이 있길래 그 내용만 보고 추측해서 풀었더니 다행히 풀렸다.(다른 블로그 코드 참고x) 문제를 보면 하나의 눈사람은 두 개의 눈덩이로 구성되고 눈덩이가 주어지면, 두 눈사람의 키 차이가 가장 작은 값을 구하라는 문제이다. 1. 투 포인터 알고리즘을 이용해 값을 조정하려면, 눈덩이들이 정렬된 상태여야 하므로 먼저 정렬을 해준다. - O(N log N) 2. 네 개의 값을 뽑아야 하므로 먼저 두 개의 값을 선..
-
Q.11559 자바 : Puyo Puyo(G4)코딩테스트/백준_Java 2023. 1. 10. 23:30
문제 : https://www.acmicpc.net/problem/11559 일하면서 풀어서 2일정도 걸려서 풀게 된 문제이다. 이 문제를 풀고 있을 때 코딩테스트를 모르는 친구가 코딩테스트가 뭐냐? 라고 물어본적이 있는데 이 문제 설명을 읽게 하니까 이해를 했다고 하면서 왜 이런걸 푸냐고 하긴 했다. 개인적으로 푸는 과정 자체는 상당히 고통스럽기도 하고 한 2~3일정도(일하면서) 박치기를 하다 보면 찾아보고 싶은 욕구를 참기가 꽤나 힘들다. 하지만 풀었을 때의 그 성취감이 상당하기 때문에 그리고 코딩테스트를 보는 기업이 많으므로 준비하고 있다. 문제 더보기 뿌요뿌요의 룰은 다음과 같다. 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 ..
-
Q.16973 자바 : 직사각형 탈출(G4)코딩테스트/백준_Java 2023. 1. 4. 14:30
문제 : https://www.acmicpc.net/problem/16973 더보기 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자. 격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다. 직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다. 직사각형의 크기와 좌표를 주고, 장애물을 피해 원하는 좌표..