문제 https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net 풀이 예상 백준 1749 점수따먹기풀이 와 같이 2차원 배열의 누적합을 활용해서 3차원으로 늘린 풀이 방법이다. 행렬의 원소의 범위가 1~10이였기 때문에 가능한 풀이이고 2차원과 방법은 똑같고 2차원 배열에 하나를 더 붙혀서 1~10숫자의 카운트를 각각해주면 된다. 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => O(N^2) import java.io.Buffere..
문제 https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 풀이 예상 2차원 배열 안에서 누적합을 이용한 풀이 풀이방법 (접근 방법 & 시간복잡도) 2차원 배열 안에서의 누적합은 아래와 같이 구할 수 있다. 주황색 칸을 구하기 위해서 왼쪽, 위쪽 칸을 더하고 왼쪽 위 대각선 칸을 빼주면 된다. 식으로 나타내면 sum[i][j] = num + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]; //본인자리숫자 + 왼쪽칸 + 위쪽칸 -..
문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 예상 석순과 종유석의 높이를 받을 때마다 해당 높이의 카운트를 늘려주는 것은 최대 20만x50만 번의 작업이 이루어 지기 떄문에 다른 방법을 찾아야 겠다고 생각했다. 그래서 높이에 따른 개수를 저장하고, 누적합을 통해서 구간에 포함되는 장애물의 수를 구한다. 풀이방법 (접근 방법 & 시간복잡도) 예제 입력 1번을 예시로 들면 입력 받았을 때, bottom[] 배열은 이렇게 되어있다. bot..
문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 예상 이 전에 바로 누적 합 문제를 풀었었기 때문에 바로 누적합이 떠올랐다. 풀이방법 (접근 방법 & 시간복잡도) 백준 2015(수들의 합4)풀이 풀이 방법 은 비슷하게 풀어서 상세하게는 설명하지 않고 달랐던 부분만 적어보겠다. A 배열에서 부 배열의 합을 Amap에 저장한다. (key: 합, value: ..
문제 https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 풀이 예상 N의 개수가 200,000 개 이기 때문에 부분 합 전체를 구해서 풀면 시간초과가 날 것 같았다. 문제에서 주어진 부분 합이란 배열 자리 수가 연속된 숫자이기 때문에 누적 합을 통해서 풀 수 있을 것 같다고 생각했다. 풀이방법 (접근 방법 & 시간복잡도) 누적합을 배열에 저장해 두고, 이 전에 나온 누적합과의 차이..
문제 https://www.acmicpc.net/problem/1407 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 풀이방법 범위가 (1≤A≤B≤10^15) 로, 엄청나기 때문에 숫자 하나 하나 나누면서 계산을 할 수 없다고 생각했다. 그래서 생각해낸 방법이 1~B 까지 더한값에 1~A-1 까지 더한 값을 빼면, 즉 f(B) - f(A-1) 으로 계산하는 방법을 생각했다. function 안에서는 일정한 규칙을 찾았고, 그 규칙에 따라 계산해 주면 된다. 규칙은주어진 숫자 n에 대해서..
https://school.programmers.co.kr/learn/courses/30/lessons/17677?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이방법 문자열을 받아서 char 배열로 만든다. 앞부터 두개씩 잘라서 보고 둘다 알파벳이라면 대문자로 바꿔서 각각의 map에 있는지 검사한다. map에 없으면 value값을 1로저장 map에 있다면 value값을 +1 값으로 저장 맵 값을 전부 순회하며 aNum, bNum, n 값을 채운다 (순서대로 str1의 총개수, str2의 총개수, 교집합개수) aNum 과 bNu..
https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이방법 해시맵과 Priority Queue를 사용. 현재 문자열을 받아와서 전부 대문자로 바꿔준다(toUpperCase() 사용) 맵에 들어있는 개수가 캐시 사이즈보다 작은경우 (pq와 맵에 값을 넣는다.) 이미 맵에 들어있는 값이면 +1 맵에 없는 값이면 +5 맵에 들어있는 개수가 캐시 사이즈와 같은 경우 (pq와 맵에 값을 넣는다.) 이미 맵에 들어있는 값이면 +1 ..
