본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 2750 수 정렬하기 출처: https://www.acmicpc.net/problem/2750 삽입 정렬을 이용해 구현 - 배열 index에 적절한 값을 찾아갑니다. array = { 1, x, 5, 7, 2 } 1 = end) return; int pivot = start, le.. 2021. 2. 23.
[BOJ] 백준 2178 미로 탐색 출처: https://www.acmicpc.net/problem/2178 Input 4 6 110110 110110 111111 111101 Output 9 * input data는 각각의 수들이 붙어서 입력되므로 주의. BFS 이용 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Vertex{ int x, y; int count; public Vertex(int x, int y, int count) { this.x = x; this.y = y; this.count = count; } } public class Main { public static void main(String[] args) { Sca.. 2021. 2. 23.
[BOJ] 백준 6064 카잉 달력 출처: https://www.acmicpc.net/problem/6064 Input 3 10 12 3 9 10 12 7 2 13 11 5 6 Output 33 -1 83 카잉 달력의 표기 방식은 다음과 같습니다. 첫 번째 해 , 두 번째 해를 로 표현 즉, 의 다음 해를 방식으로 표현합니다. 1 ≤ x ≤ M, 1 ≤ y ≤ N일 때, 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 달력의 마지막 해. [M = 10, N = 12인 경우] - 첫번째 해는 - 11번째 해는 - 13번째 해는 - 마지막 해는 으로 60번째 해 (x,y)가 있으면 (x+1, y+1) → (x+2, y+2) → ..... 2021. 2. 23.
[BOJ] 백준 2108 통계학 출처: https://www.acmicpc.net/problem/2108 계수 정렬(Counting Sort) 계수 정렬(Counting Sort) 계수 정렬(Counting Sort) → O(N) - 숫자가 등장한 횟수를 세서 그 기준으로 정렬하는 방법 - 정렬하는 숫자가 특정한 범위안에 있을 때 사용할 수 있습니다. + 메모리 낭비가 있을 수 있습니다. - 비 zoosso.tistory.com N개의 수들에 대한 기본 통계값을 구하는 문제입니다. (N은 홀수라고 가정.) ① 산술평균 : N개의 수들의 합을 N으로 나눈 값 ② 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 ③ 최빈값 : N개의 수들 중 가장 많이 나타나는 값 ④ 범위 : N개의 수들 중 최댓값과 최솟값의.. 2021. 2. 23.
[BOJ] 백준 3184 양 출처: https://www.acmicpc.net/problem/3184 Input 9 12 .###.#####.. #.oo#...#v#. #..o#.#.#.#. #..##o#...#. #.#v#o###.#. #..#v#....#. #...v#v####. .####.#vv.o# .......####. Output 3 5 ① 배열을 순회하면 울타리가 아닌 지역에서 BFS ② BFS를 하며 같은 영역 안에 있는 양과 늑대 수 확인 ③ 살아남은 쪽을 결과값에 저장 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int R, C; static int[] dx = {-1, .. 2021. 2. 23.
[BOJ] 백준 2606 바이러스 출처: https://www.acmicpc.net/problem/2606 Input 7 6 1 2 2 3 1 5 5 2 5 6 4 7 Output 4 『1』 컴퓨터를 시작 정점으로 연결되어 있는 모든 정점의 개수를 찾습니다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); int connect = Integer.parseInt(sc.next()); int[][] com = n.. 2021. 2. 23.
[BOJ] 백준 1449 수리공 항승 출처: https://www.acmicpc.net/problem/1449 Input 4 2 1 2 100 101 Output 2 * 문제에서는 좌우 간격을 0.5를 주어야 한다고 하였으며, 다시말해, 테이프로 해당 좌표를 덮어씌울 수 있으면 됩니다. 물이 새는 곳의 위치는 다음과 같으면 L = 2이기 때문에 2개의 테이프만 있으면 됩니다. 왼쪽에서부터 테이프를 차례대로 겹치지 않게 붙입니다. 구현 ① 새어나오는 곳의 위치를 오름차순 정렬 (※ 실제 Input Data에서 Random하게 주어짐) ② 테이프 길이 L을 최대한 활용하며 테이프를 붙입니다. + 적은 테이프로 많은 곳에 붙여야 합니다. 새어나오는 위치 두 『1』, 『3』 를 테이프 1개로 붙이고 『100』에 1개 더 붙여 총 2개가 필요. In.. 2021. 2. 23.
[BOJ] 백준 12851 숨바꼭질 2 출처: www.acmicpc.net/problem/12851 Input 5 17 Output 4 2 ※ 5 → 순간이동 → 10 → 걷기 → 9 → 순간이동 → 18 → 걷기 →17 ▶ 4초 ※ 5 → 걷기 → 4 → 순간이동 → 8 → 순간이동 → 16 → 걷기 →17 ▶ 4초 [BOJ] 1697 숨바꼭질에서 구현했던 BFS 와는 다르게 특정 위치를 중복 방문해줘야 합니다. [BOJ] 백준 1697 숨바꼭질 출처: https://www.acmicpc.net/problem/1697 Input 5 17 Output 4 ※ 5 → 순간이동 → 10 → 걷기 → 9 → 순간이동 → 18 → 걷기 →17 ▶ 4초 A 위치 > B 위치인 경우, A를 오직 『.. zoosso.tistory.com Input 1 4.. 2021. 2. 23.
[BOJ] 백준 1697 숨바꼭질 출처: https://www.acmicpc.net/problem/1697 Input 5 17 Output 4 ※ 5 → 순간이동 → 10 → 걷기 → 9 → 순간이동 → 18 → 걷기 →17 ▶ 4초 A 위치 > B 위치인 경우, A를 오직 『x - 1』 이동하여 B를 만날 수 있습니다. A 위치 < B 위치인 경우, A는 『x + 1』 하거나 『2 * x』 하여 B 와의 간격을 좁힐 수 있습니다. ▶ BFS를 활용하여 가능한 경로로 방문하여 최단 경로를 구합니다. ※ (확장 문제)가장 빠른 시간안에 도달하는 방법의 수도 물어보는 문제 ▶ [BOJ] 12851 숨바꼭질 2 [BOJ] 백준 12851 숨바꼭질 2 출처: www.acmicpc.net/problem/12851 Input 5 17 Output .. 2021. 2. 23.
[BOJ] 백준 10711 모래성 출처: https://www.acmicpc.net/problem/10711 Input 10 10 .......... .99999999. .9.323239. .91444449. .91444449. .91444449. .91444449. .91232329. .99999999. .......... Output 35 ① 처음 input으로 주어지는 파도의 위치(x, y)와 경과 시간(cost)를 큐에 저장합니다. ② Queue에 값을 한 개씩 꺼내어 인접한 모래성의 강도를 낮춥니다. 다른 파도가 존재하는 곳이거나 모래성의 강도가 9인 경우는 continue (파도가 8면에 존재할 수 있으므로 모래성의 강도 = 9 인 경우 무너지지 않습니다.) ③ 무너지는 모래성이 존재한다면 다음 차례에 파도가 되므로 Queue.. 2021. 2. 22.
반응형

티스토리툴바