백준84 [11659] 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 누적합과 관련된 문제이다. 누적합 알고리즘 없이 for문으로 풀게 된다면 시간초과가 발생할 것이다. 누적합: 배열 index가 증가함에 따라, 입력 받은 수를 누적해서 더한 값을 넣고, 구간을 지정하면 그에 맞는 값을 출력함 누적합을 저장해줄 배열 X의 입력 최대 범위를 생각해보았다. 1,000이하의 수가 입력된다고 하였으므로 누적합의 최대 범위는 1,000*100,000 .. 2022. 10. 10. [3190] 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀 게임할 땐 재밌었는데 코드 구현은 좀 힘들다 ㅎㅎ^^;; 전체적인 while문을 구성해보자면 (1) 뱀이 어디로 움직일지 좌표 (i,j)을 설정한다. (2) 가려는 좌표 (i, j)가 적합한지 따져본다. (2)-1 적합하다면 사과가 있는지 없는지 따져본다 (2)-2 적합하지 않다면 while문 종료 문제에 종료 조건이 주어져있다. 1. 벽에 부딪히거나 2. 자기자신의 몸과 부딪히면 게임이 끝난다. 그.. 2022. 10. 5. [11664] 선분과 점 https://www.acmicpc.net/problem/11664 11664번: 선분과 점 첫째 줄에 선분과 점의 좌표 Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz가 주어진다. 좌표는 0보다 크거나 같고, 10,000보다 작거나 같은 정수이다. www.acmicpc.net 선분 AB와 점 C 사이의 거리의 최솟값을 구하는 문제이다. 처음에는 선분 AB를 지름으로 하는 원을 만들어서 최소 거리를 구해볼까 생각했는데, 3차원이라서 쉽지 않았다. 그래서 사용한 것이 삼분 탐색이다. 선분 AB 위에 놓여있는 점 x,y,z를 삼분탐색으로 계속 바꿔준다. 그렇게 갱신한 점이 점 C와 최소 거리를 갖는다! 하면 값을 바꿔주는 것이다. 근데 제일 애 먹었던게 탐색을 어떤 조건을 이용해 종료할 것인지.. 2022. 10. 2. [1654] 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 요즘 문제 이해하는 시간도 오래 걸린다 .. K = 4, N = 11, 갖고 있는 랜선의 길이가 차례로 802 743 457 539 라면! 이미 있는 4개의 랜선을 동일한 크기로 다 쪼개면 랜선의 개수가 N개 이상이 되어야 함. // 802 : 200 200 200 200 2 // 743 : 200 200 200 143 // 457 : 200 200 57 // 539 .. 2022. 10. 1. [2805] 나무 자르기 이게 왜 실버 2에 있지? 싶을 정도로 쉬운 문제였다. 내 자존감 지키미. 고마웡. 절단기 설정 높이를 KEY라고 지정해놓았다면, 나무가 X미터일 때 KEY 이상으로는 다 잘라서 가져간다는 뜻이다. 나무가 KEY보다 작으면 뭐 어쩔 수 없지 못가져가는 것이다. 그럼 이제 절단기 설정 높이의 범위를 알아야 하는데, 문제에 써있다.(0이상 1,000,000,000미만) 하지만 탐색 시간을 줄이기 위해 입력된 나무의 최대 높이를 최댓값으로 잡아주었다. 탐색시간을 줄이려면 이분 탐색이 짱이다. 사실 알고리즘 분류에도 이분 탐색이라고 쓰여있다. 완성된 코드는 아래와 같다. 주석을 자세히 적어놓았다. #include using namespace std; int N, M; int A[1000000]; int maxi.. 2022. 9. 30. [2343] 기타 레슨 2512번 문제와 유사하게 이분탐색으로 푸는 문제이다. https://kmyobin.tistory.com/69 [2512] 예산 알고리즘 분류가 이분 탐색으로 되어있다. 일단 상한액의 범위는 (1 ~ INPUT의 최댓값)이다. 이를 이분 탐색 해나가며 상한액을 최댓값으로 갱신한다. 상한액이 만약 key라면, key를 기준으로 전체 kmyobin.tistory.com 거의 똑같다. 이 때는 최댓값 구하는 게 목표였던 것 빼고는? 이번에는 최소 블루레이 크기를 구하는 것이 목표이다. 그럼 일단 블루레이 크기가 될 수 있는 범위를 생각해본다. 배열 X에 강의 시간이 N개 입력된다고 했을 때, 블루레이 크기는 최소 1부터.. 최대 N개의 강의 영상 시간을 다 더한 sum(X)까지다 1 ~ sum(X) 1부터 반.. 2022. 9. 28. [2512] 예산 알고리즘 분류가 이분 탐색으로 되어있다. 일단 상한액의 범위는 (1 ~ INPUT의 최댓값)이다. 이를 이분 탐색 해나가며 상한액을 최댓값으로 갱신한다. 상한액이 만약 key라면, key를 기준으로 전체 예산을 구해본다. 이 총 예산액이 M보다 크다면 key를 너무 크게 잡은 것이므로 더 작게 잡고 이분탐색을 진행한다. 총 예산액이 M보다 작거나 같다면 이 key가 최댓값인지 따져보고, 더 큰 상한액을 위해 이분탐색을 진행한다. 자세한 설명은 코드에 적어놓았다. #include #include using namespace std; int N; int INPUT[10000]; int M; int maximum = -1; void BinarySearch(int start, int end, int key) {.. 2022. 9. 27. [1094] 막대기 문제 설명이 너무 이상해서 검색을 해보았다. 64cm의 막대기를 계속 절반으로 쪼개면서 Xcm의 막대기로 만드는 것이다. 예를 들면 23cm의 막대기를 만들고 싶으면 23cm = 16cm + 4cm + 2cm + 1cm : 총 4개의 막대기 필요 48cm의 막대기를 만들고 싶으면 48cm = 32cm + 16cm : 총 2개의 막대기 필요 64cm부터 시작해서 계속 절반으로 쪼갰을 때, Xcm보다 작아진다면 X로부터 만들어진 막대기의 길이를 빼주기(X=X-cur)를 반복하다가 X가 0이 되면 종료하고 막대기의 개수를 출력한다. 전체 코드는 아래와 같다. #include using namespace std; int X; // 64 32 16 8 4 2 1 // 23 = 16 + 4 + 2 + 1 => 4개.. 2022. 9. 27. [1064] 평행사변형 규칙은 그리 어렵지 않다. 주어진 3개의 점이 만약 일직선상에 놓여있다면 ? 이는 사각형이 만들어질 수 없는 조건이므로 -1.0을 출력한다. 사각형의 둘레를 구하는 것은 좀 더 생각을 해봐야 한다. 나는 모든 경우의 수를 생각하고 일치하는 조건들을 찾는 타입이다. 결국 찾았다. 저 보라색으로 쓰여있는 것이 우리가 따져볼 수 있는 둘레의 경우의 수이다. 저기서 최댓값, 최솟값을 구해 차이를 출력하면 되는 문제였다. 두 점 사이의 거리를 구할 때는 피타고라스의 정리가 이용된다. 이는 중학교 때 배운 것이니 코드로 직접 보일 것이다. 소수점의 자리수도 생각해줘야 한다. 기본은 6자리까지밖에 안나오기 때문에 %.16f를 사용하든 cout xy[i].x >> xy[i].y; } sort(xy, xy + 3, cm.. 2022. 9. 26. [1904] 01타일 처음에는 00타일과 1타일로 만들 수 있는 경우의 수를 백트래킹을 이용하여 풀어보았다. #include #include using namespace std; int N; string m[1000001]; int cnt; void dp(int count, string before, bool is_done) { if (count == N) { cnt++; return; } if (before == "0" && is_done == false) { // 0이 하나만 쓰였을 때 m[count] = "0"; is_done = true; dp(count + 1, m[count], is_done); } else { // 0이 다 쓰여져있거나 그 전 값이 1이었던 경우 if (count == N - 1) { // 맨 마.. 2022. 9. 25. 이전 1 2 3 4 5 6 7 8 9 다음
