알고리즘/문제 풀이

heights 를 이중순회하면서 height[j] 문제각 칸의 넓이가 동일한 히스토그램의 높이 값이 주어진다. 이 히스토그램에서 가장 넓은 사각형을 만들었을 때 그 넓이를 출력하라시간 제한: 0.7초데이터 크기:  1  출처: https://www.acmicpc.net/problem/1725 접근히스토그램의 높이값 배열을 heights 라고 하자기본적인 아이디어는 heights 를 하나의 방향으로 순회할때  height[i] 보다  height[i+1] 이 작으면 더이상 height[i] 높이의 사각형을 만들 수 없다는 것이다.부르트포스따라서 부루트포스 접근으로 heights 를 이중순회하면서 height[j] 하지만 이 접근의 시간 복잡도는 O((n * n)) 이다. 1초에 2억번 연산을 한다고 생각하..

문제n 개중에 k 개를 고르는 이항계수(Binomial Coefficient) 를 구하는 문제이다. 결과값을 1,000,000,007 로 나눈 나머지를 출력한다.제약사항: 1  출처: https://www.acmicpc.net/problem/11401접근OutOfMemoryError: Java heap space일단 숫자가 심상치 않게 크다는 것을 알 수 있다. 이항 계수 2에서 사용했던 이항 계수의 정의를 이용한 풀이를 하려면  4,000,000 * 4,000,000 의 long 타입 heap 메모리 공간( 256,000 GB )을 확보해야한다.이정도의 heap 메모리 공간을 일반적인 컴퓨터에게 기대할 수 없는 수준이므로 4,000,000 * 16byte = 0.064GB  의 메모리 공간을 요구하는 ..

문제n 개중에 k 개를 고르는 이항계수(Binomial Coefficient) 를 구하는 문제이다. 결과값을 10007 로 나눈 나머지를 출력한다.제약사항: 1  출처: https://www.acmicpc.net/problem/11051접근이항 계수1 풀이와 마찬가지로 조합의 정의를 이용한 접근, 그리고  이항계수의 정의를 이용한 접근 모두 사용해볼 수 있겠다.하지만 조합의 정의를 이용했을 경우에는 모듈러 연산이 복잡해지므로 이 단계에서는 간단한 모듈러 정의만 이용하기 위해 이항계수의 정의를 이용한 풀이만 소개한다.모듈러 연산의 특징 을 고려해서 코드를 약간 변형해줘야한다.모듈러 연산의 특징덧셈에 대한 모듈러: (a+b) %  m =((a % m) + (b %  m)) %  m곱셈에 대한 모듈러: (a*..

문제n 개중에 k 개를 고르는 이항계수(Binomial Coefficient) 를 구하는 문제이다.n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 다음과 같이 정의한다. = 'nCk = n!/(n-k)!k!'제약사항: 1 접근n!/(n-k)!k! 를 구현해내면 된다.조합의 정의를 이용팩토리얼은 그 계산이 단순하여 DP 로 구현이 가능하고, n! 과 (n-k)!k! 의 값을 DP 로 풀어내면 될 것이다.N 의 크기가 최대 10으로 제한되어 있으므로 Heap Memoy OOM 걱정은 없고, n!, (n-k)!, k! 를 계산할때 이미 계산했던 데이터를 이용하므로 속도상 이점이 있을 것이다.시간복잡도팩토리얼 계산을 해야하므로 O((N)) 의 시간복잡도를 가질 것이다. 이항계수의 정의를 이용조합의 정의를..

문제N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 이 있는데, 하나의 숫자로만 이루어진 정사가형의 개수를 세어서 -1, 0, 1 순서로 출력하라 출처 : https://www.acmicpc.net/problem/1780접근이전에 풀었던 백준 2630 색종이 만들기의 조금 다른 버전의 문제이다.기본적으로 동일한데 종이를 4등분이 아닌 9등분을 한다는 사실과 -1, 0, 1 순서로 출력한다는 사실이 다르다.따라서 백준 2630 색종이 만들기 문제를 조금더 확장성 있게 바꿔서 풀면 된다. 역시 시간 복잡도는 O(N^2) 이다.풀이public class Main { private static int[][] BOARD; private static final int NEXT..

문제N×N(N=2k, k는 1 이상 7 이하의 자연수) 크기의 배열이 주어지고, 0 아니면 1로 채워져있다. 0을 흰색, 1을 파란색으로 인식할때 배열이 하나의 색상으로만 이뤄질때까지 4등분씩 잘라내고 최종적으로 모든 정사각형이 하나의 색상으로만 이루어졌을때 흰색 정사각형개수, 파란색 정사각형 개수를 출력하라접근로직(1) 판단: 주어진 배열 BOARD 가 BOARD[x][y] ~ BOARD[x+size][y+size] 안에 모든 숫자가 동일한지 판단한다.(2) 병합: 주어진 배열 BOARD 이 일정 범위 (x,y ~ + size) 안에서 동일한 숫자만 있다면 그에 맞는 색상{흰색, 파란색} 의 개수를 늘린다.(3) 분할: 주어진 배열 BOARD 이 일정 범위 (x,y ~ + size) 안에서 동일한 숫자..

문제이런류의 문제는 설명이 장황해서 실제 코딩테스트에서 마주치면 당황할 수 있지만, 잘 읽어보면 쉬운 문제이다. N 개의 도시를 직선 방향으로 이동할껀데, 기름이 0인 차를 타고 시작한다.각 도시간 거리와 각 도시의 리터랑 가격이 주어진다.1리터랑 거리 1씩 이동할 수 있다.이때 지불하는 최소한의 금액을 구하여라 문제 출처 : https://www.acmicpc.net/problem/13305접근첫번째 도시에서는 다음 도시까지 가기위해서는 어쩔수 없이 distance[0] * oilPrice[0] 만큼 값일 치뤄야한다.만약 oilPrice[0] 위와 같이 다음 도시의 기름값이 지금 도시의 기름값보다 비싸다면, 지금 도시에서 해당 거리만큼을 채워넣는다. 이러한 접근방법을 일반화하면되고, 순회횟수는 각도시간..

문제+, -, 숫자로 이루어진 계산식이 주어지면 가장 계산 결과가 작아지게 괄호를 놓았을 때 그 결과를 출력하라각 숫자는 5자리를 넘지 않으며, 0으로 시작할 수 있다.식의 처음과 끝은 무조건 숫자이다. 출처 : 백준 1541번 문제접근- 를 만났을때 하나의 그 이후를 모두 -로 묶을 수 있다. 풀이오랜만에 string to int 를 직접 구현해야해서 번거로웠다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static String formula; static int index, number; public static void main(S..