백준 검색 결과

해당 글 27건

백준 3020번 개똥벌레 (JAVA)

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 처음에는 2차원 배열로 만들어서 체크하는 방식으로 접근했는데, 생각보다 N과 M이 커서 메모리가 터졌습니다. 그래서 입력받으면서 구간합 느낌으로 더해줬습니다. 종유석을 top에 넣고, 석순을 bot에 넣어서 높이별로 수를 합산하여 가장 적게 걸리는 경우를 계산하여 출력했습니다. public class BOJ_3020_개똥벌레 { static Function stoi = Integer::parseInt..
카테고리 없음 2021. 7. 12. 19:27

백준 2533번 사회망서비스SNS (JAVA)

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net DP문제 * 스티커 모으기(2)랑 어쩌면 비슷했던 개념의 문제. * 처음에는 트리를 구현해서 풀 수 있을거라고 생각했는데, * 어떤 노드라도 루트가 될 수 있다는 점을 망각하여 결국 로직을 다시 구성해야했습니다. * dp로 접근하여, 루트노드를 1로 잡고 루트가 얼리어답터인 경우 vs 아닌 경우로 나누어 탑다운 dp로 풀이 public class BOJ_2533_..
알고리즘/백준 2021. 7. 12. 19:16

백준 4195번 친구 네트워크 (JAVA)

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 전형적인 유니온 파인드 문제이다. 엔테크 서비스 코딩테스트에 나왔던 유니온 파인드 문제를 제대로 풀지 못한게 아쉬워서 한번 더 풀어보았다. public class BOJ_4195_친구네트워크 { static Function stoi = Integer::parseInt; static int T, F; static int[] parent; static int[] rank; public st..
알고리즘/백준 2021. 7. 12. 18:59

백준 21610번 마법사 상어와 비바라기 (JAVA)

굉장히 놀랍게도 어른 상어 이후의 상어 시리즈가 있었다! 마법사 상어와 파이어볼의 연장선 같은 느낌이 나는 문제였는데, 맵을 넘어가는 구름이 이동 시 모듈러 연산을 하는 부분이 그러했다. 지난번과 같이 수학적으로 한줄로 풀어낼까 하다가, mod 함수를 따로 빼서 두는 것이 가독성이 좋을 것 같아 이번엔 그러한 방식으로 구현해보았다. 구현 방식은 문제에 주어진 것을 그대로 구현하면 된다. 1. 모든 구름이 di 방향으로 si칸 이동한다. private static void moveCloud() { Direc d = direcs.poll(); List tmp = new ArrayList(); for (Node n : clouds) { tmp.add(new Node(mod(n.x + dir[d.d][0] * ..
알고리즘/백준 2021. 6. 27. 22:59

백준 15684번 사다리조작 (JAVA)

역시나 삼성 기출문제답게 시뮬레이션 + 완탐이지만, 생각보다 첫 발상이 까다로워서 꽤 오랜 시간 푼 문제이다. 왼쪽으로 가는 사다리를 1, 오른쪽으로 가는 사다리를 2로 놓고 모든 경우의 수에 사다리를 놓아 완탐을 돌면 답을 구할 수 있다. 1. 사다리를 놓을 위치를 완전탐색으로 정한다. private static void buildLadder(int x, int cnt) { if (flag) { return; } if (cnt == result) { // 기저조건 if (check()) { flag = true; } return; } for (int i = x; i
알고리즘/백준 2021. 6. 27. 22:55