Coding Test (40) 썸네일형 리스트형 백준 테트리스(3019) 구현에 가까운 문제를 풀었다. https://www.acmicpc.net/problem/3019 3019번: 테트리스 테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다. 블록을 떨어뜨리기 전에 www.acmicpc.net 위 문제는 선택된 블록이 바닥에 높이를 정해줬다. 시작부터 끝라인까지 순회하면 현재 높이로부터 블록을 쌓았는데 이후 높이들이 맞는지 확인한다. 총 블록이 7개가 존재하여 블록 별로 필요한 높이를 case별로 배열로 정리해두고 해당 검사 루프를 돌린 후 검사에 통과하였을 경우 개수를 증가시켜줬다. import java.io.BufferedReader; import java... 백준 RGB거리(1149) dp 문제를 풀었다.. https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 128 MB 112778 63223 46955 55.176% 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠.. 백준 계단(21600) DP 문제를 풀게되었다. https://www.acmicpc.net/problem/21600 21600번: 계단 자료의 분포를 아래의 그림과 같이 나타낸 그래프를 히스토그램이라고 합니다. 당신은 히스토그램 영역에서 가장 큰 계단을 찾으려고 합니다. 계단은 아래 조건을 만족하는 영역을 말합니다. www.acmicpc.net 왼쪽에서 오른쪽으로 가장 높은 계단을 만들 수 있는 경우를 구하는것이다. 해당 문제는 현재 차례의 자리가 만들 수 있는 가장 높은 높이를 저장하면서 구하면된다. 필자 같은 경우는 처음 높이는 1로 시작하면서 진행했고 이전 높이보다 현재 높이가 높으면 현재 자리는 이전높이 + 1를 해준다 그렇지 않는 경우는 현재 높이와 이전 높이중 작은 값을 설정해준다. 이후 최대 값을 찾으면 된다. i.. 백준 사격(31264) 이분 탐색 문제이다. https://www.acmicpc.net/problem/31264 31264번: 사격 초기 사격 실력이 $1$이라면 $1$점 표적, $2$점 표적, $4$점 표적을 차례로 쏴 총 $7$점을 얻어 진급에 실패한다. 초기 사격 실력이 $2$라면 $2$점 표적, $4$점 표적, $5$점 표적을 차례로 쏴 총 $11$점을 얻 www.acmicpc.net 해당 문제를 정확이 풀기 위해서는 이분탐색을 사용해야한다. 처음에는 중복으로 사격 가능한걸 놓쳐서 고생을 하다 중복가능성을 보고 문제를 풀었다.... 해당 문제는 현재 사격가능한 최대 점수 기준으로 최대 사격 점수를 가져와 나의 사격 가능 점수를 높이면서 M번 사격했을때 총합을 비교하면된다. 처음에는 위에 방법만 사용하니 50점을 맞았는데.. 백준 두 수의 합(9024) 이분 탐색 문제이다. https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 두 수의 합 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 2217 936 688 43.544% 문제 여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수 S = { -7, 9, 2, -4, 12.. 백준 입국심사(3079) 오늘은 이진탐색 문제를 하나 풀어보았다. https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 입국심사를 최소 시간을 돌 수 있는 케이스를 찾아보기 위해서 시간을 이분탐색하며 해당 시간에 모두 심사를 마칠수 있는지 체크하는 방식으로 진행했다. 알고리즘은 맞는거 같은데 틀리길래 확인해보니 나는 최대로 오래걸리는 입국심사위원 * 대상자가 최대 시간이라 생각했는데 이러면 overflow가 나오는거 같다 그리하여 최소입국 심사위원으로 변경하니.. 백준 개똥벌레 (3020) 이분탐색 문제 찾아 풀어봤다 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 개똥벌레 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 17682 7763 5710 45.014% 문제 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 아래 그림은 길이.. 백준 시간관리(1263) 그리디 문제 하나 풀었다. https://www.acmicpc.net/problem/1263 1263번: 시간 관리 진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다. 진영 www.acmicpc.net 시간 관리 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 3542 1483 1253 42.503% 문제 진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다. 진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해.. 백준 숌 사이 수열(1469) 백트래킹 문제를 풀어보았다 복잡해서 시간이 오래걸렸다. https://www.acmicpc.net/problem/1469 1469번: 숌 사이 수열 첫째 줄에 X의 크기 N이 주어진다. 둘째 줄에 X에 들어가는 수가 빈칸을 사이에 두고 주어진다. X의 크기는 8보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수 www.acmicpc.net 초기에는 가능한 종류를 만들어보려고 하였지만 시간초과 발생 할 것같아서 주어진 경우의 수에서 가능한 경우의 수를 찾는 방식으로 처리를 했다. 문제의 핵심은 현재 뽑은 원소의 값이 2개가 위치할 수있는가 예를들어 2라면 현재 위치 2 ? ? 2 해서 마지막 2가 놓일 수 있는가 핵심이다. 나의 로직에서는 depth + element .. 백준 로프(2217) 그리디 문제를 한개 더풀어봤다 생각보다 이 알고리즘이 재미가 있다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프의 개수가 늘어날수록 (로프 리스트 중 가장 낮은값 * 로프 개수가) 최대 무게가 된다 이러한 방식으로 정렬되어있는 로프를 순서대로 최적해를 찾아가면 된다. package greedy; import java.io.BufferedReader; import java.io.IOException; import java.io... 이전 1 2 3 4 다음
