백준 2357_최솟값과 최댓값 시간제한 2초, 메모리 제한 192MB # 조건 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다. 입력 첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의..

프로그래머스 - 점 찍기 # 조건 좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다. 원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다. 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다. 예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다. 정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는..

프로그래머스 - 택배 배달과 수거하기 # 조건 ![[Algorithm/programmers/assets/Pasted image 20230522135228.png]] 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다. 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n) 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배..

백준 1189_컴백홈 시간제한 1초, 메모리 제한 128MB # 조건 한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6 위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 ..

백준 2042 - 구간 합 구하기 시간 제한 2초, 메모리 제한 256MB # 조건 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 ..

목차 Segment Tree? 구현 query 응답하기 업데이트 1. Segment Tree? 어떤 데이터가 존재할 때, 특정 구간의 결과값을 구하는데 사용하는 자료구조이다. 단순한 구간합 뿐만 아니라주어진 쿼리에 대해 빠르게 응답하기 위한 자료구조!! 여기서는 이해하기 쉽게 구간합을 예시로 세그먼트 트리를 알아볼 예정 아래와 같은 배열이 존재할 때, 구간합을 구해보자. 배열을 돌면서 원하는 구간의 합을 더해주면 된다! 배열의 크기가 커진다면, 시간이 더 많이 걸릴 것이다. 따라서, 구간별 합을 구해 저장해둔다면 빠르게 찾을 수 있을 것이다!! 세그먼트 트리는 Binary Tree(이진 트리) 구조를 가지고 있다. 배열의 크기 Full Binary Tree 일 경우 높이는 logN 노드의 개수 2 * (..

백준 1019_책 페이지 시간 제한 2초, 메모리 제한 128MB # 조건 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. # 접근 방법 10억이므로 우선 브루트포스로는 시간초과가 발생하므로 풀 수 없다. 따라서 규칙을 찾아야 되는데 시간이 상당히 오래 걸렸다.. 찾은 규칙 설명 0~9까지는 앞자리가 변경되도 1개씩 나온다. 이걸 이용해서, 전체 숫자에서 일..

백준 14939 - 불 끄기 시간 제한 1초, 메모리 제한 256MB # 조건 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라 # 접근 방법 브루트 포스와 그리디를 활용하여 비트마스킹으로 풀어줘야 하는 문제였다.. 비트마스킹으로 첫 줄의 모든 경우의 수를 구하는 아이디어가 잘 생각이 나지 않아 다른 블로그를 참고하였다. https://bio-info.tistory.com/234 핵심은 첫 행의 전구 10개에 대해 켜고 끄는 모든 경우의 수 2 ^ 10 = 1024개에 대하여, 두 번째 행부터는 윗..

백준 9527 - 1의 개수 세기 시간 제한 1초, 메모리 제한 128MB # 조건 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. 입력 첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 출력 1의 개수를 세어 출력한다. # 접근 방법 처음에 어떻게 풀어야 될지 감이 잘 오지 않았던 문제이다. 1000조까지의 범위가 주어지므로 무식하게 풀 수 없었기에 규칙을 찾는데 집중하였다. 2가지 규칙을 찾을 수 있었는데 우선, 1부터 해당 숫자들을 2진수로 변경 시, 2^n -1 까지의..