본문 바로가기

Coding Test

 (40)
백준 휴먼 파이프라인(22981) 그리디 알고리즘 문제를 풀어보았다. https://www.acmicpc.net/problem/22981 22981번: 휴먼 파이프라인 모든 상자를 최대한 빠르게 옮기는 경우의 작업 시간을 분 단위로 출력한다. www.acmicpc.net 문제를 보면 A, B 두팀의 합산으로 이루어진 분당 처리량을 구하면 될거 같다. 한팀은의 분당 처리량은 주어진 처리량값중에 가장 작은 값이다. 그 다음 처리량 값을 구하면 해당 해 기준으로 인원수 처리를 하면 된다. 해서 구할수 있는 점화식이 있었다. 분당 처리량 = (최대인원 - 선택인덱스) * 선택인덱스 처리량 + (선택인덱스 * 최소 처리량) 이 되겠다. K는 long 타입으로 주의해야한다. 계속 numberFormatException이 나오길래 뭔가했었다. imp..
백준 체스(9204) 오늘은 BFS 문제를 풀어보았다. https://www.acmicpc.net/problem/9204 9204번: 체스 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 시작 위치 X와 도착 위치 Y가 주어진다. 각 위치는 두 글자가 공백으로 구분되어져 있다. 글자는 열, www.acmicpc.net BFS + 구현 문제라고 생각이 된다. 비숍이 움직일 수 있는 방향은 대각선이다 열을 숫자로 바꾸어 생각하면 배열로 손쉽게 풀수있다. 현재 위치에서 움직일수 있는 방향을 모두 담아서 움직이고 방문 기록을 기록하면된다. 최대 4번만 움직일 수 있으니 그부분을 주의하면서 움직였던 기록도 함께 저장하면서 움직여야한다 메모리 제한은 작기에 최대 4번만 움직이게만든 문제같다...
백준 스타트와 링크(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 해당 문제는 어떻게 푸는게 좋을지 생각을 해보자 1. A팀의 인원을 선별하게 되면 나머지는 자동적으로 B팀이라고 가정하면 된다. 2. A팀을 예시로 1 2 5로 뽑나, 5 2 1 로 뽑나 같은 경우의 수로 해당 중복 케이스는 진행하지 않는 방향으로 구성하면 된다. 하여 뽑힌 A팀의 인원의 능력치와 B팀의 능력치를 구하여 비교한 최소값을 해로 구하면 된다. import java.io...
백준 나이트의 이동(7562) bfs문제를 풀어봤다. https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 테스트케이스가 주어지며 현재 위치에서 타겟 위치까지 체스 이동시 가장 작은 비용을 구하는 문제이다 일단 움직일수 있는 방향을 배열로 정리한 후 테스트케이스별 bfs 함수 처리를 진행했다. 이 문제의 포인트는 방문기록이 있지만 비용이 낮게 들어온경우는 처리해주면서 가장낮은 비용을 구하는 계산이 될 거 같다. import java.io.BufferedReader; import j..
백준 점프왕 쩰리 (Large)(16174) 간단한 DFS문제 풀었습니다. https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 오른쪽, 아래로 이동하면서 마지막 칸에 도달할 수 있는지 여부만 체크하면된다. 가는길에 방문 여부만 관리하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Mai..
백준 보드점프(3372) 오늘은 DP문제를 풀었다 https://www.acmicpc.net/problem/3372 3372번: 보드 점프 N × N 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 www.acmicpc.net 문제는 크게 어렵지 않다 처음 시작점부터 점프가능한 부분의 영역을 DP해가면서 진행하면된다. 크기가 굉장히 큰편이기에 BigInteger를 사용했다. 처음에는 모두 0으로 초기화 안하고 NULL체크로 진행했는데 종착점을 0으로 초기화 하지않으면 통과하지 못하는 케이스가 있어 고전했다. 알고리즘은 쉽지만 조건이 약간 귀찮은 문제였다. import java.io.Buffered..
백준 블랙홀과 소행성(29755) 이분 탐색 문제를 풀어 보았다. https://www.acmicpc.net/problem/29755 29755번: 블랙홀과 소행성 첫 번째 줄에 블랙홀의 수 $N$과 소행성의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 200\,000)$ 두 번째 줄에 $N$개의 정수 $b_1$, $b_2$, $\cdots$, $b_N$이 공백으로 구분되어 주어진다. $(-1\,000\,000 www.acmicpc.net 문제의 공식의 최소값을 구하는 문제이다. 공식을 잘 살펴보 |b-a| 해당 부분이 작을수록 최소값을 가질수 있는 것으로 보인다. 해당 값이 결국 작으려면 블랙홀과 행성의 거리 차가 가장 짧은 것을 찾으면된다. 각 행성별로 거리 차이 * 무게가 가장 높은게 최소 P 값이라고 생..
백준 국기 색칠하기(30702) 오늘의 문제는 DFS문제로 풀어봤다. https://www.acmicpc.net/problem/30702 30702번: 국기 색칠하기 세계의 여러 나라들은 자신의 나라를 상징하는 깃발인 국기가 있는데, 그중에는 색만 다르고 모양이 비슷한 국기들이 있다. 국기는 $N$행 $M$열의 격자판(행렬)으로 구성되어 있다. 격자판의 각 www.acmicpc.net 문제는 A국기를 B국기를 만들 수 있냐는 질문이었다. 해당 문제 풀이에 대해서 고민을 해본 결과 하나의 해답을 정했다. 풀이 메모리 제한이 굉장히 너프한 것을 보면 힌트를 얻을 수 있을 수 도 있다. 하나의 색으로 이루어 진 부분을 part라고 지칭하겠다. 문제는 A의 part가 B에 국기에 대조했을때 B국기에 해당 part의 색이 모두 똑같으면 된다. ..
백준 삼각 그래프(4883) dp 문제를 풀었다. https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 처음 가운데 중앙에서 마지막 가운데 중앙까지 가는 최단경로를 찾는 문제이다. 처음 dp배열라인에 값을 설정하고 증가시키는 방법으로 진행하려고 생각했다. 각 왼 중 오 3개의 포인트에서 어떤 루트로 들어와야 가장 값이 낮을수있을까 생각을 해봐야한다. 현재라인 h높이라 할때 왼 : dp[h-1][0], dp[h-1][1] 중 : dp[h][0], dp[h-1][0..
백준 스타트링크(5014) 오늘은 bfs 문제를 풀었다. https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 어떻게 문제를 처리하는게 좋을까 생각했다 일단 저층부터 고층까지 위아래로 움직이면서 갈수 있는곳 이 있을것이고 도착한곳에 방문기록을 생성하면 나아가면되지않을까 생각했다. 방문한곳은 더이상 방문하지않으면서 움직이면 최소한의 이동거리로 방문가능하게 bfs방식으로 움직여줬다. 이상하게 81퍼에서 계속 실패를해서 도저히 모르겠다 싶어서 게시판을 봤는데... 0층은 없다.... 0층을 간..

티스토리툴바