본문 바로가기
반응형

분류 전체보기313

백준 14889 : 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [ 문제풀이 ] 간단한 문제이다. N명의 사람 중 N/2명의 사람을 뽑는 조합을 구현할 수 있다면 아주 쉽게 해결할 수 있는 문제이다. ​다만, 모든 조합을 구할 필요가 없다. 6명의 사람 중 3명을 뽑는 모든 조합을 한번 보자. 자세히 보면 1번 사람을 선택한 후 가능한 조합 이후로는 이미 앞에서 구한 조합들만 나오는 것을 확인할 수 있다. 따라서 우리는 모든 조합을 구할 필요 없이 1번 사람을 포함하는 조합만 구하.. 2021. 8. 2.
백준 14888 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net [ 문제풀이 ] 간단한 문제이다. 주어진 연산자로 만들 수 있는 모든 경우의 수를 다 탐색하여 최댓값과 최솟값을 구해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamRead.. 2021. 8. 2.
백준 14503 : 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [ 문제풀이 ] 간단한 시뮬레이션 문제이다. 주어진 조건 그대로 로봇을 움직이도록 구현하면 쉽게 해결할 수 있을 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri.. 2021. 8. 2.
백준 14502 : 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [ 문제풀이 ] 이번에도 간단한 시뮬레이션 문제이다. 0인 공간에 벽을 세우면서 3개를 세웠을 경우 바이러스를 퍼트려 안전 공간의 개수를 카운트해 주면 쉽게 해결할 수 있다. ​벽을 3개 세우는 경우의 수를 구하는 것은 백트래킹 기법을 통해 구하면 될 것이다. ​나는 처음에 Virus라는 클래스를 구현하여 바이러스들을 관리해줬는데 매번 새로운 바이러스 객체를 생성해주는 것은 메모리에 부담이 크다. 어차피 바이.. 2021. 8. 2.
백준 4195 : 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net [ 문제풀이 ] 두 친구가 같은 그래프에 속하는지를 판단해야 하기 때문에 Union-Find 알고리즘을 활용하면 해결할 수 있다. 다만, 매번 두 친구가 속한 그래프의 정점의 개수를 탐색한다면 시간 초과가 발생할 것이다. 이를 위해 rank 배열을 하나 선언하여 각 정점마다 자식의 수를 관리해주도록 한다. 두 친구를 union할때 자식의 수가 많은 친구를 부모로 두 친구를 합해준다. i.. 2021. 8. 2.
백준 15486 : 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net [ 문제풀이 ] 다이나믹 프로그래밍을 이용한 정해의 시간 복잡도가 O(N)이었기 때문에 다시 한번 풀어봤다. 퇴사 1을 해결한 나의 코드에서 어떤 부분을 줄일 수 있을지 생각해봤다. ​아래의 코드가 퇴사 1에서 O(N^2)의 시간 복잡도를 가지는 구간이다. for (int i = 2; i = 0) { dp[i] = Math.max(dp[i], dp[j] + P[i]).. 2021. 8. 1.
백준 14501 : 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [ 문제풀이 ] 정해는 다이나믹 프로그래밍이지만 N이 워낙 작기 때문에 완전 탐색을 기반으로 해결해도 되는 문제이다. 나는 다이나믹 프로그래밍을 이용해서 해결하였다. ​먼저 다음과 같은 dp 테이블을 정의하자. dp[i] : i번째 날 얻을 수 있는 최대 수익 위와 같은 정의를 통해 우리는 dp[i]는 최대 수익이 들어있다고 가정할 수 있다. 그렇다면 점화식은 어떻게 도출할 수 있을까? ​j번째 날과 j번째 상담을 하고 걸리는 기간(T[j])이 현재 i번째 날보다 작거나 같으면 j번째 날의 최대 비용에 i번째 날의 상담을 하는 비용을.. 2021. 8. 1.
백준 14500 : 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [ 문제풀이 ] 테트로미노로 만들 수 있는 모든 종류(회전, 대칭)를 만들어 종이에 놓을 수 있는 모든 경우의 수를 구하면 해결할 수 있는 문제이다. ​종이를 회전시키는 방법도 있고 여러 가지 방법이 있겠지만 나는 간단하게 테트로미노로 만들 수 있는 모든 종류를 미리 만들어서 해결하였다. ​대칭, 회전을 통한 만들 수 있는 모든 종류는 다음과 같다. 이를 3차원 배열로 표현하면 다음과 같다. st.. 2021. 8. 1.
백준 14499 : 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net [ 문제풀이 ] 단순한 시뮬레이션 문제이다. 각 방향으로 주사위를 굴리는 부분만 구현하면 쉽게 해결할 수 있는 문제이다. 나는 주사위를 굴렸을 때 6번 면이 항상 아래 면으로 오도록 구현하였다. 동쪽으로 주사위를 굴리는 경우 : (3, 6), (1, 3), (4, 1)을 swap 해주면 된다. 서쪽으로 주사위를 굴리는 경우 : (6.. 2021. 8. 1.
반응형

티스토리툴바