티스토리

Better Programming

검색하기

블로그 홈

Better Programming

ar-tec.tistory.com/m

Yejii 님의 블로그입니다.

구독자: 8

방명록 방문하기

주요 글 목록

[Java] 백준 1003 피보나치 함수 문제 0이상 40이하의 정수가 주어질 때, 해당 숫자를 가지고 피보나치 함수를 호출한다. 이 때 n이 0과 1에 다다르는 횟수를 출력하는 문제이다. 문제에서 요구하는 바를 재귀로 구현하게 되면 40 level의 트리가 만들어지게 되고 O(40!)이라는 시간 복잡도가 나오게된다. (0.25초 안에 당연히 통과 불가) 따라서 만들어질 수 있는 수들의 규칙을 찾아서 점화식을 만들어야 한다. N = 0 1 0 N = 1 0 1 N = 2 1 1 N = 3 2 1 위의 숫자를 토대로 0의 개수, 1의 개수를 각각 담는 DP 배열을 만들 수 있다. N 0 1 2 3 4 [0의 개수] 1 0 1 1 2 [1의 개수] 0 1 1 2 3 코드 import java.io.BufferedReader; import java... 공감수 0 댓글수 0 2021. 3. 24.
[Java] 백준 1931 회의실 배정 문제 회의의 시작시간, 종료시간이 주어질 때 사용할 수 있는 회의의 최대개수를 출력하는 문제. 풀이 - 처음엔 문제를 잘못 이해했다. - 시작시간이 2 종료시간이 2라고 할 때 시작과 동시에 끝나므로 해당 경우도 갯수에 더해줘야 한다. - 또한 (1 2) (2 2) 인 경우나 (2 2) (2 5) 인 경우 2 회의 모두 결과값에 포함될 수 있다. - 첫번째로 푼 풀이는 다이나믹 프로그래밍이었다. - 현재 인덱스에 대해서 이전의 인덱스를 모두 확인하여 최댓값을 구하게끔 했다. - 이 경우 O(n^2)이라는 시간 복잡도가 나와 N이 10만인 경우 100억의 연산이 필요하다는 문제가 있었다. 당연히 시간초과가 났다. - 두번째로 푼 풀이는 그리디였다. - 사실 회의를 최대한으로 하는 횟수는 매우 간단하게 구할.. 공감수 0 댓글수 0 2021. 3. 24.
[Java] 백준 12852 1로 만들기 2 문제 숫자 N이 주어지고, 가능한 연산은 3가지가 주어진다. 3으로 나누어 떨어진다면 3으로 나누기, 2로 나누어 떨어진다면 2로 나누기, 1을 빼기. 이 때 최소의 연산 횟수로 1을 만든다고 할 때 최소 연산 횟수와 해당 경우에 사용되는 숫자를 출력하는 문제. 풀이 기존의 '1로 만들기' 문제에서 사용되는 숫자를 출력하는 로직만 넣어주면된다고 생각했다. 처음엔 MAP 자료구조를 이용해서 DP의 인덱스 값을 KEY로 해당 인덱스를 만들어주기 위한 숫자들을 VALUE로(ArrayList)로 저장하게끔 했다. 통과는 했다. 하지만 다른 분들의 답안을 보고 int 배열을 둔 뒤 재귀 호출로 출력하는 방식이 있다는 것을 발견했다. 처음에 푼 풀이보다 시간이 10분의 1로 줄어들었다. 코드 import java... 공감수 0 댓글수 0 2021. 3. 24.
[Java] 백준 11726 2 x n 타일링 문제 2 x n 크기의 직사각형을 채우는 경우의 수를 출력한다 사용할 수 있는 타일의 크기 - 1 x 2 - 2 x 1 풀이 - dp[i]는 2가지 타일을 사용해서 2 x i 직사각형을 채울 수 있는 방법의 수이다. - 2 x i를 만들 수 있는 경우의 수는 다음의 두 경우를 더한 값이다. - 2 x (i - 1)까지 만든 타일 + [2x1타일] - 2 x (i - 2)까지 만든 타일 + [1x2타일+1x2타일] - 이것을 점화식으로 나타내면, dp[i] = dp[i-1] + dp[i-2] 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class b11726__2 { .. 공감수 0 댓글수 0 2021. 3. 19.
[Java] 백준 11399 ATM 문제 사람의 수와 각 사람이 돈을 인출하는 데 걸리는 시간이 주어진다. 이 때 모든 사람이 돈을 인출하기 위해 대기하는 총 시간의 최솟값을 출력하는 문제이다. 풀이 인출시간이 빠른 사람이 앞에 오도록해서 사람들의 대기시간을 최소로 만든 뒤에 대기시간의 합을 구하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class b11399 { public static void main(String[] args) throws IOException { BufferedR.. 공감수 0 댓글수 0 2021. 3. 19.
[Java] 백준 1149 RGB 거리 문제 집 N개가 있다. 각각의 집은 빨강, 초록, 파랑으로 칠할 수 있다. 각각의 집에 각각의 색깔을 칠하는 가격은 다르다. 또한 인접한 집의 색깔은 같아선 안된다. 위의 규칙을 모두 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해라 풀이 N번째 집을 칠해야 하는 상황이라고 생각해보자. 1) N번째 집을 빨간색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다. - N-1번째 집이 초록색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용 - N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용 2) N번째 집을 초록색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다. - N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 .. 공감수 0 댓글수 0 2021. 3. 16.
[Java] 백준 10610 30 문제 숫자 N이 주어진다. 해당 숫자를 이루고 있는 수들을 이용해서 만들 수 있는 가장 큰 30의 배수를 출력하는 문제이다. 풀이 처음에는 받아온 N이라는 숫자를 char[]로 쪼개어서, 만들 수 있는 모든 조합을 만들다가 가장 큰 30의 배수가 나오면 출력하게끔 짰다. 근데 NumberFormat Exception이 발생했다. 다시 문제를 자세히 살펴보니, 주어진 N이라는 수의 자릿수가 최대 10^5라는 조건이 있었다. 최댓값이 10^5(100_000)라는 것으로 착각했던것.. 이 조건을 생각하면 long타입으로도 조합을 만들 수가 없다. 다른 분들의 코드를 참고해서 풀었다. 풀이의 핵심은 다음과 같다. - 30의 배수는 10의 배수이므로 끝자리가 0이다. => N에 0이 포함되어 있지 않다면 30의 .. 공감수 0 댓글수 0 2021. 3. 15.
[Java] 백준 9095 1,2,3 더하기 문제 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구해라. 풀이 1) 1을 1,2,3의 합으로 나타내는 방법 [1 단독으로 사용가능] - 1가지 : (1) - 1 단독 2) 2을 1,2,3의 합으로 나타내는 방법 [2 단독으로 사용가능] - 2가지 : (1,1) / (2) - [1]을 만드는 경우에 1을 합한 경우 / 2 단독 3) 3을 1,2,3의 합으로 나타내는 방법 [3 단독으로 사용가능] - 4가지 : (1,2)/ (1,1,1) (2,1) / (3) - [1]을 만드는 경우에 2를 합한 경우 / [2]를 만드는 경우에 1을 합한 경우 / 3 단독 4) 4를 1,2,3의 합으로 나타내는 방법 [단독으로 사용가능한 숫자없음] - 7가지 : (1,3) / (1,1,2) (2,.. 공감수 0 댓글수 0 2021. 3. 13.
[Java] 백준 2875 대회 or 인턴 문제 대회에 나갈 수 있는 1 팀은 여자2 남자1로 구성되어 있다. 여자는 총 m명 남자는 총 n명이 있다고 할 때 m+n명중 k명은 반드시 인턴에 참여해야한다. 인턴에 참여한 인원은 대회에 참가할 수 없다고 할 때, 만들 수 있는 최대 팀수를 구하는 문제이다. 풀이 - 먼저 만들 수 있는 팀 수의 최댓값(teams)을 구한다. - 만들 수 있는 팀의 개수는 '총 여자 수/2(1팀에 최소로 들어가야하는 여자 수)'와 총 남자 수/1(1팀에 최소로 들어가야 하는 남자 수)' 중 더 작은 값이다. - int teams = Math.min(M/2, N/1) - 총 인원에서 팀에 속한 사람들 (teams * 3)을 뺀 나머지 인원을 구한다. - 이 인원이 K보다 크거나 같아야 K명 이상이 인턴에 참여가능한 것이.. 공감수 0 댓글수 0 2021. 3. 10.
[Java] 백준 11047 동전 0 문제 n 종류의 동전이 주어진다. 동전을 적절히 사용해서 가치의 합을 K로 만드는 문제이다. 풀이 K보다 작은 동전의 가치중 가장 큰 값으로 K를 나눠 동전의 개수를 구하고 나머지로 K를 초기화한다. K가 0이 되면 사용한 동전의 총 개수를 출력한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu.. 공감수 0 댓글수 0 2021. 3. 10.
[Java] 백준 2579 계단 오르기 문제 계단을 밟으면 해당 계단에 쓰인 점수를 얻을 수 있다고 할 때, 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 규칙 - 한 번에 1계단 or 2계단 - 연속 3계단 불가능 - 시작점은 계단 아님 - 도착점은 반드시 밟기 풀이 현재 위치가 n번째 계단이라고 할 때, n번째 계단에서 얻을 수 있는 점수의 최댓값을 생각해보자. 연속 3칸을 밟은 것은 불가능하기 때문에 고려해야할 경우는 2가지이다. 1) n-2번째 계단을 밟은 뒤 n번째 계단을 밟은 경우 - dp[n-2] + scores[n] 2) n-3번째 계단을 밟은 뒤 n-1번째 계단을 밟고 n번째 계단을 밟은 경우 - dp[n-3] + scores[n-1] + scores[n] 즉, 다음의 두 가지 경우 중 큰 값으로 dp[n]을 초기화 시키면 .. 공감수 0 댓글수 0 2021. 3. 10.
[Java] 백준 1463 1로 만들기 문제 정수 N이 주어졌을 때, 3 종류의 연산을 적절히 사용해 1을 만드려고 한다. 정수 N을 1로 만드는 연산횟수의 최솟값을 출력해라. - 1 공감수 0 댓글수 0 2021. 3. 9.
[Java] 백준 2447 별찍기 10 문제 크기 3의 패턴이 주어지고, 크기가 3이상일 때 가운데는 공백 나머지는 n/3 패턴으로 둘러싼 형태의 모양을 출력하는 문제이다. 풀이 공백이 되어야 하는 부분과 아닌 부분으로 분할해서 재귀하는 것이 풀이의 핵심이다. - n을 3으로 나누어 현재 영역을 9등분한다. - 이 때 가운데는 공백이라는 조건이 있으므로, 5번째 영역은 항상 공백이 되어야 한다. - n이 1이라면 별을 출력하고, 아니라면 나누어진 영역을 재탐색한다. 코드 import java.io.*; public class Main { static char[][] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea.. 공감수 0 댓글수 0 2021. 3. 9.
[Java] 백준 1992 쿼드트리 문제 주어진 영역 내의 숫자가 모두 같은 숫자면 해당 숫자를 출력하고, 아니라면 영역을 4등분하여 숫자가 같은지 다시 검사를 하는 문제이다. 풀이 1. 현재 영역의 숫자를 검사 2. 모두 일치하지 않는다면 현재 변의 길이(n)을 1/2하고, 현재 좌표를 기준으로 4영역으로 분할하여 함수를 재호출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[][] map; static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedRea.. 공감수 0 댓글수 0 2021. 3. 9.
[Java] 백준 11729 하노이 탑 이동 순서 문제 하노이의 탑에 있는 N개의 원판을 '1'에서 '3'으로 이동시킬 때, 탑의 이동 순서를 출력하는 문제이다. 하노이의 탑 풀이는 공식처럼 외워서 사용하는 편이 편한 것 같다. 핵심적인 논리는 N개의 원판을 '1'에서 '3'으로 이동시키기 위해 우선 N-1개를 '1'에서 '2'(도움닫이 공간)으로 이동시킨 후, 마지막 1개의 원판을 '3'으로 이동시키는 것이다. 이동시킨 후엔 '2'(도움닫이 공간)으로 이동시킨 원판을 다시 '3'으로 이동하는 방식으로 진행한다. 그림을 그려가며 이해하는 것이 좋다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main {.. 공감수 0 댓글수 0 2021. 3. 5.
[Java] 백준 1780 종이의 개수 문제 잘라진 종이가 한 숫자로만 이루어져 있는지를 검사하고 그렇다면 종이 개수를 추가하고, 아니라면 9등분으로 나눠 다시 종이 내의 숫자를 검사하는 문제이다. 9등분으로 나누는 부분을 재귀로 처리하였다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int[][] map; static int[] res; public static void main(String[] args) throws IOException { solution(); } static v.. 공감수 0 댓글수 0 2021. 3. 5.
[Java] 백준 11728 배열 합치기 문제 정렬되어 있는 배열 A와 B가 주어질 때, A와 B를 합친 새로운 배열을 정렬된 형태로 출력하는 문제이다. A와 B의 가장 작은 값을 비교하여 더 작은 값을 새로운 배열에 추가하고 인덱스를 하나 증가시키는 방식을 사용한다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader.. 공감수 0 댓글수 0 2021. 3. 5.
[Java] 프로그래머스 징검다리 문제 바위들의 위치가 담긴 배열이 있고, 제거할 바위 수 n가 있다. 바위 배열에서 n개를 제거한 이후 각 지점사이 거리 최솟값 중 가장 큰 값 리턴해라. - distance : 도착지점까지의 거리 1~10억 - rocks 요소 개수 : 1~5만 - n 제거할 바위 개수 : 1 ~5만 1) 조합 처음엔 단순하게 n개의 숫자 중 n개를 고르는 시행 만든 뒤 최댓값을 비교하는 방식이 떠올랐다. 하지만 input 값이 커진다면 조합의 경우의 수가 매우 커지기 때문에 효율적인 방식이 아니다. 2) 이진탐색 최소거리를 탐색기준으로 설정한 뒤 추정한 거리로 바위 개수를 세고, '추정한 바위 개수' >= '바위 총개수 - n' 가 남아있어야 최소거리 조건을 만족한다. 조건을 만족한 값들 중 최댓을 구해서 리턴하면 된.. 공감수 0 댓글수 0 2021. 3. 5.
[Java] 프로그래머스 입국심사 문제 입국심사를 기다리는 사람들과 심사를 맡은 심사관들이 있다. 심사를 기다리는 사람 수를 n, 각각의 심사관이 1명을 심사하는 데 걸리는 시간이 담긴 배열 times가 주어졋을 때 n명 모두 심사를 받기 위해서 걸리는 최소 시간을 리턴하는 문제이다. - 1 공감수 0 댓글수 0 2021. 3. 5.
[Java] 백준 10815 숫자 카드 문제 상근이가 가진 숫자카드 N개가 주어지고, 각각의 카드에는 -10,000,000 이상 10,000,000 이하의 정수가 적혀있다. 그 다음 M개의 정수가 주어질 때 상근이가 가지고 있는 숫자인지를 판별해서 출력하는 문제이다. 2가지 방식으로 풀이했다. 1) 배열로 방문체크 - 카드가 가질 수 있는 숫자의 범위만큼 boolean배열을 만든다. - 상근이가 가지고 있는 숫자라면 해당 인덱스의 값을 true로 초기화한다. - M개의 카드 인덱스를 받아와서 boolean배열의 값이 true인지 확인한다. 2) 이진탐색 - 상근이가 가진 카드 배열을 오름차순 정렬한다. - M개의 카드 값을 받아와서 상근이의 카드배열을 이진탐색한다. 코드 import java.io.BufferedReader; import ja.. 공감수 0 댓글수 0 2021. 3. 3.
[Java] 백준 2110 공유기 설치 문제 집 N개에 공유기 C개를 설치한다. 공유기가 설치된 거리가 가장 가까운 두 집을 골라 두 집의 거리 차를 구한 뒤에 거리의 차이가 최대가 되는 경우의 거리차를 출력하는 문제이다. 1) 브루트포스 방식 (X) 문제를 곧이곧대로 생각한다면 다음과 같이 풀이할 수 있다. - N개의 집 중 공유기를 설치할 C개를 고른다 => nCc (조합) - 모든 경우의 수에서 가장 인접한 집 2채의 거리차를 구하여 거리차의 최댓값을 리턴한다. 하지만 N과 C 범위의 최댓값(N:20만, C:20만)으로 입력이 주어진다면 시간 제한을 통과하지 못하게 된다. (20만 팩토리얼..) 따라서 해당 방식으로 문제를 풀 수 없다. 2) 이진탐색 방식 문제를 살짝 다르게 생각하면 이진탐색방식으로 논리를 설계할 수 있다. 문제에서 요.. 공감수 0 댓글수 0 2021. 3. 3.
[Java] 백준 2805 나무 자르기 문제 필요한 나무의 길이 M과 나무들의 높이가 주어진다. 절단기 높이 H를 지정하여 나무들을 자르고, 잘라진 부분이 M 이상이 되게 만드는 H의 최댓값을 구하는 문제이다. - 1 공감수 0 댓글수 0 2021. 3. 3.
[Java] 백준 1654 랜선 자르기 문제 이미 가지고 있는 랜선의 개수 K와 만들어야 하는 랜선의 개수 N이 주어진다. 가지고 있는 랜선(길이가 제각각)을 잘라 동일한 길이의 랜선 N개를 만든다고 할 때, N개를 만들 수 있는 랜선의 최대 길이를 출력하는 문제. - 1 공감수 0 댓글수 0 2021. 3. 3.
[알고리즘 이론] 이진 탐색 알고리즘 이진 검색 알고리즘이란? : 오름차순으로 정렬된 리스트에서 특정한 값(X)의 위치를 찾는 알고리즘 가장 쉬운 예시로 책 페이지를 찾는 경우를 생각할 수 있다. 선생님이 168페이지를 피라고 말씀하신다면, 우리는 우선 가지고 있는 책을 반으로 갈라 페이지를 확인할 것이다. 펼친 페이지가 168페이지보다 크다면 더 앞의 페이지를 확인할 것이고, 168페이지보다 적다면 더 뒤의 페이지를 확인할 것이다. 이런 방식으로 임의의 중간값을 설정하여 목표값보다 큰지 작은지 판별하며 범위를 줄여나가는 탐색방법을 이진 탐색이라고 한다. - 장점: 탐색할 때마다 범위가 1/2로 줄어들기 때문에 선형 탐색보다 훨씬 빠르다. (선형탐색 : O(N^2), 이진탐색: O(NlogN)) - 단점: 탐색할 리스트가 오름차순으로 정렬된.. 공감수 0 댓글수 0 2021. 3. 2.
[Java] 백준 2178 미로 탐색 문제 (1,1)에서 (N,M)으로 이동하는 최단경로를 구하는 문제이다. 풀이 BFS로 map을 탐색하며 이동거리로 map을 초기화 했다. map[n][m]이 1이 아니게 되면 가장 먼저 도착지점에 다다른 것이므로 break하고 이동거리를 출력하도록 했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] map; static int AVAILAB.. 공감수 0 댓글수 0 2021. 2. 25.
[Java] 백준 2146 다리만들기 문제 설명 섬과 바다가 있는 지도가 주어진다. 섬과 또 다른 섬을 잇는 다리를 만든다고 할 때, 가장 짧은 다리의 길이를 출력하라. 풀이 각 섬을 그룹화하여 번호를 붙이는 것은 어렵지 않았지만, 최단경로를 구하는 부분에서 어려움이 있었다. 최단경로를 구하는 메서드의 로직을 처음 푼 방식과 추후 수정한 방식 2가지로 정리해보았다. 1. (처음 푼 방식) 섬 1개를 기준으로 탐색하여 다른 섬을 발견하면 탐색을 멈추는 방식 - 최단경로를 구하기 위해서 이동거리를 담을 배열 visited를 Integer.MAX_VALUE로 초기화한다. int[][] visited = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { visite.. 공감수 0 댓글수 0 2021. 2. 25.
[Java] 백준 7576 토마토 문제 M x N 크기의 상자와 각 칸에 들어있는 토마토의 상태가 주어진다. (1: 익은 토마토, 0: 안익은 토마토, -1: 토마토 없음) 익은 토마토는 인접한 안익은 토마토를 익게만든다고 할 때, 토마토가 모두 익을 때까지 최소 날짜를 출력해라. 모두 익을 수 없는 경우엔 -1, 이미 모두 익어있는 경우엔 0을 출력한다. (2 = N || y = M) return false; return true; } static class Point { int x, y, days; public Point(int x, int y, int days) { this.x = x; this.y = y; this.days = days; } } } 채점결과 공감수 0 댓글수 0 2021. 2. 23.
[Java] 백준 4963 섬의 개수 문제 섬(1)과 바다(0)로 이루어진 지도가 주어진다. 이어져 있는 섬은 하나의 섬으로 간주할 때, 섬의 총 개수를 출력해라. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class b4963 { static int W, H; static int[][] map; static int SEA = 0, LAND = 1, VISITED = 2; public static void main(String[] args) thro.. 공감수 0 댓글수 0 2021. 2. 23.
[Java] 백준 2667 단지번호붙이기 문제 0과 1로 이루어진 지도가 주어진다. 0은 집이 없는 곳 1은 집이 있는 곳이라 하고 집이 상하좌우로 모여있는 곳을 하나의 단지로 설정한다. 단지의 총 개수와 단지에 속하는 집의 수를 오름차순으로 정렬해서 출력해라. (5 = N) return false; return true; } } 채점 결과 공감수 0 댓글수 0 2021. 2. 23.
[Java] 백준 9466 텀 프로젝트 문제 학생의 수 N과 1부터 N까지의 학생이 팀을 이루고 싶은 학생 번호가 주어진다. 어떤 팀에도 속하지 않는 학생의 수를 계산해라. - 학생 수 (2 0) total -= cnt; }// for sb.append(total).append("\n"); } System.out.println(sb); } } 2. DFS 풀이 - 각 학생이 선택한 학생번호를 담을 int배열 students, 방문 확인여부를 담을 boolean배열 visited, 덧셈 확인여부를 담을 boolean배열 checked를 둔다. - for문을 돌며 각 학생들이 팀을 이룰 수 있는지 확인한다. - dfs(학생번호)를 재귀적으로 호출한다. - 현재 학생이 아직 방문하지 않은 상태라면 visited[학생번호]를 true로 변경하고 다음.. 공감수 0 댓글수 0 2021. 2. 22.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.