'알고리즘 풀이/백준' 카테고리의 글 목록
본문 바로가기
728x90

알고리즘 풀이/백준28

[백준] 7662 이중 우선순위 큐 자바(Java) 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 TreeMap 자료 구조를 사용한다. TreeMap은 키값을 기준으로 즉시 정렬되는 자료 구조입니다. key = 정수, value = 입력된 횟수 최댓값(최솟값)의 입력 횟수가 2번 이상일 때는 입력 횟수 -1, 입력된 횟수가 1번이면 삭제한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str.. 2023. 6. 19.
[백준] 6198 옥상 정원 꾸미기 자바(Java) 풀이 기존에 지나온 빌딩 중 새로운 빌당보다 낮은 빌딩만 저장 마지막 서있는 곳보다 새로운 빌딩의 높이가 낮으면 같이 지나갈 수 있기 때문 스택에 가장 마지막 빌딩 높이(마지막 서있는 곳) 2023. 4. 13.
[백준] 2493 탑 자바(Java) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 stack에 탑의 위치, 높이를 저장 이전 탑의 길이) 현재 탑의 길이 이전 탑의 위치 표기 수신할 수 있는 탑이 없으면 0 표기 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.Str.. 2023. 4. 10.
[백준] 1874 스택 수열 자바(Java) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 스택 활용 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; public class Main { public static void main(String[] ar) throws Exception { .. 2023. 4. 9.
[백준] 20165 인내의 도미노 장인 호석 자바(Java) https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 알고리즘은 다음과 같이 작동합니다. 각 도미노의 양쪽에 일정한 수의 점이 있는 도미노 게임을 시뮬레이트하는 Java 프로그램입니다. 직사각형의 도미노 보드를 가져옵니다. 여기서 각 셀은 각 면에 특정 수의 점이 있는 도미노를 나타냅니다. 프로그램은 또한 일련의 동작을 취하며 각 동작은 공격과 방어로 구성됩니다. attack은 시작 셀, 방향 및 크기로 표시됩니다. 지정된 셀에서 시작.. 2023. 3. 4.
[백준] 16924 십자가 찾기 자바(Java) https://www.acmicpc.net/problem/16924 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net 문제 이 알고리즘의 목적은 주어진 문자 격자에서 모든 별 모양의 패턴을 찾고 각 패턴의 크기와 위치를 출력하는 것이다. 입력은 표준 입력 스트림에서 읽히고 첫 번째 줄에 두 개의 정수 N과 M으로 구성되며, 각각 문자 그리드를 나타내는 길이 M의 N 줄로 구성된다. 문자 '*'는 별 모양의 패턴의 일부를 나타냅니다. 출력은 표준 출력 스트림으로 인쇄되며, 발견된 별 모양 패턴의 수를 나타.. 2023. 2. 28.
[백준] 10816 숫자 카드 2 자바(Java) https://www.acmicpc.net/problem/10816 중복된 값을 가지고 있는 배열에서 입력된 값이 몇 개 있는지 출력하는 문제 HashMap을 사용해서 풀 수 있지만 카테고리가 이분 탐색이라 이분탐색으로 문제 접근 처음 입력받은 배열을 정렬 입력 값 이분 탐색 동일 값 처음 인덱스 마지막 인덱스 구하기 마지막 인덱스 - 처음 인덱스 동일 값 처음 인덱스 private static int lower(int[] arr, int key) { int si = 0; int li = arr.length; while (si < li) { int mid = (si + li) / 2; // 입력 값과 같거나 큰 값 if (key 2023. 2. 22.
[백준] 11004 K번째 수 자바(Java) https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 11004번 문제에서 2가지 정렬 방식으로 문제를 접근했습니다. Arrays.sort(), Collections.sort() Java8에서는 Arrays.sort()는 시간 초과가 나오고 Collections.sort()는 문제를 맞혔습니다. Java11에서는 Arrays.sort()도 맞았다고 나옵니다. 시간 복잡도에서 최악의 경우 Arrays.sort()는 O(n^2) 값이 나와 시간 초과가 나옵니다. Java11에서는 왜 맞았다고 나오는지 이유.. 2023. 1. 29.
[백준] 2579 계단 오르기 자바(Java) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 백준 2156 포도주 시식 문제와 비슷한 문제다. 다른 점은 "마지막 도착 계단은 반드시 밟아야 한다."이다. 계단 오르기의 경우의 수는 2가지이다. 마지막 도착 계단 밟은 상태에서 n -1 위치의 계단을 밟지 않는 상태 vs n -1 위치의 계단을 밟은 상태 위 그림과 같이 2가지 형태로 나올 수 있다. 앞에 n - 2, n - 3 위치의 체크표시가 빨간 이유는 다음과 같다. n -1 위치의 계단을 밟지 않.. 2023. 1. 6.
[백준] 2156 포도주 시식 자바(Java) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 가장 많이 마실 수 있는 상황의 값을 저장한 dp 테이블 int[] dp = new int[n + 1]; 와인의 용량이 저장된 테이블 int[] values = new int[n + 1]; 와인을 마실 수 있는 경우의 수 아래 그림 3가지 중 가장 큰 값이 dp[i] 에 저장이 된다. 현재 i위치에 있는 와인을 마시는 경우 그림에서 위에 2줄 연속으로 3잔을 모두 고를 수 없다는 것을 고려한다. 1.. 2023. 1. 6.
[백준] 9465 스티커 자바(Java) https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제에서 이동하는 방법은 현재 위치에서 대각선으로만 갈 수 있다. 하지만 아래 그림과 같이 그 다음칸의 대각선으로도 이동이 가능하다. 1번 값과, 2번 값중 큰 값을 선택하면 된다. 그럼 점화식나온다. dp[0][n] = Max(dp[1][n - 1], dp[1][n - 2]) + dp[0][n] dp[1][n] = Max(dp[0][n - 1], dp[0][n - 2]) + dp[1].. 2023. 1. 6.
[백준] 2193 이친수 자바(Java) https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 점화식 풀이 1. 현재 위치에서 값이 0이면 이전 값은 1과 0이 올 수 있다. dp[digit][0] = dp[digit - 1][1] + dp[digit - 1][0]; 현재 위치에서 값이 1이면 이전 값은 0만 올 수 있다. dp[digit][1] = dp[digit - 1][0]; 풀이 2. d[i] = d[i-2]+d[i-1] 이런 식으로 푸는 방식이 있는데, 직접 나열하면서 .. 2023. 1. 5.
[백준] 11057 오르막 수 자바(Java) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net dp테이블 자릿수, 자릿값을 가지고 있어야 한다. -> dp[자릿수][자릿값] 접근 static int L(int n, int i) { if (dp[n][i] != 0) { return dp[n][i]; } if (i == 0) { dp[n][i] = L(n - 1, i); } else { for (int j = i; j >= 0; j--) { dp[n][i] .. 2023. 1. 4.
[백준] 10844 쉬운 계단 수 자바(Java) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1의 자릿수일 때 1 ~ 9까지 가능 -> 9가지 2의 자릿수일 때 1의 자릿수 1 ~ 9, 2의 자릿수 1의 자릿수의 값이 1, 9가 아니면 1의 자릿값 + 1과 1의 자릿값 - 1 2가지가 가능하게 된다. dp테이블 자릿수, 자릿값을 가지고 있어야 한다. -> dp[자릿수][자릿값] 초기화 dp[1][1~9] = 1; -> 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없다 점화식 탑다운 자바 코드 package main.iyk2h; import java.io.BufferedReader.. 2023. 1. 2.
[백준] 9095 1, 2, 3 더하기 자바(Java) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 : n을 1, 2, 3의 합으로 나타내는 방법의 수 접근. countSum( 1 ) = 1 countSum( 2 ) = 2 countSum( 3 ) = 4 countSum( 4 ) = 7 countSum( 5 ) = 13 ... n = 5까지 단순하게 숫자를 세본 결과 규칙을 찾을 수 있었다. countSum( n ) = countSum( n - 1) + countSum( n - 2) + countSum( n - 3) 증명. n = 4일 때 맨 마지막 더하기 값에는 3가지 값이 들어갈 수 .. 2023. 1. 1.
[백준] 11727 2xn 타일링 2 자바(Java) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726 문제를 이해하고 풀었다면 쉽게 풀리는 문제이다. 아래 블로그 참고 https://iyk2h.tistory.com/306 기존 문제에서 2 * 2 정사각형 타일이 추가되었다. 위 그림과 같이 직사각형을 채워나갈 수 있게 된다. n의 값이 3, 4일 때부터 규칙이 보이기 시작한다. n = 3 일 때 색으로 구별해 두었는데, 빨간색은 박스는 n = 2 일 때 타일을 채우는 방법에 2 * 1 세로 타일을 추가했고, 오른쪽 .. 2023. 1. 1.
[백준] 11726 2xn 타일링 자바(Java) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제를 풀어보고 오면 좋겠습니다. 문제는 2*n 크기의 직사각형을 2 * 1 타일로 채우는 방법의 수를 구하는 문제이다. 위 그림과 같이 직사각형을 채워나갈 수 있게 된다. n의 값이 3, 4일 때부터 규칙이 보이기 시작한다. n = 3 일 때 두 개의 박스로 크게 묶어두었다. 묶은 이유는 왼쪽 박스는 n = 2 일 때 타일을 채우는 방법에 2 * 1 세로 타일을 추가했고, 오른쪽 박스는 n = 1 일 때 직사각형을 .. 2023. 1. 1.
[백준] 1463 1로 만들기 자바(Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근 방법 단순하게 접근하면 3으로 나누고, 2로 나누고, 나눌 수 없으면 -1을 하면서 값을 작게 만들면 되지 않나 생각할 수 있다. 단순 접근 : 10 -> 5 -> 4-> 2-> 1 : 4번 정답 : 10 -> 9 -> 3-> 1 : 3번 쉽게 단순 접근은 틀린 걸 알 수 있다. 이유는 10을 1로 만드는 경우에 2가지 경우의 수가 생기게 된다. 1. 9를 1로 만드는 최솟값 + 1 2. 5를 1로 만드는 최솟값 + 1 두 값 중 더 작은 값이 최솟값이 된다. 그럼 문제에서 나온 3가지 경우를 보면 최솟값.. 2022. 12. 30.
Java - [백준] 1929 소수 구하기 이번 소수 구하기에서 1978 소수 찾기, 2581 소수, 11653 소인수분해 문제와 다른 점은 시간제한이 있다. n 값을 줬을 때 소수를 구하는 방법에는 크게 3가지 방법이 있다. 첫 번째로 모든 자연수, 즉 1~n까지 n 값을 나누어 값이 1, n을 제외한 다른 자연수로 나눠지면 소수가 아니게 된다. for (int i = 2; i < n; i++) { // i의 값 범위를 2 2022. 9. 30.
Java - [백준] 2292 벌집 벌집 모양을 보면 6, 12, 18, 24 ... 6*n씩 증가하는 수열이다. 그리고, 값의 범위도, 직전의 값 + 1 ~ 진전의 값 + (6*n) 이다. 값의 범위안에 있으면, 최단거리는 같은 n값을 가진다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ​ public class Main { ​ public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); ​ int input = Integer.parseIn.. 2022. 9. 27.
Java - [백준] 1316 그룹 단어 체커 간단하게 설명하면, 입력된 단어를 스펠링단위로 값을 받아 입력된 값을 check[] 에 따로 표시하면서. 다음 스펠링이 check[] 에 표시가 되었다면, 전에 스펠링과 같은 스펠링이면 패스, 다른 스펠링이면 break or return false 로 카운트 하지 않는 방법으로 접근해서 풀었다. 일반 2중 반복문 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; ​ public class Main { public static void main(String[] args) throws IOExceptio.. 2022. 9. 23.
Java - [백준] 1157번 단어공부 입력받을때 영어의 대문자 소문자를 구분하는데 2가지 방법이 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.Set; ​ public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); ​ int[] arr = new int[26]; ​ String s = bf.. 2022. 9. 20.
Java - [백준] 3052번 나머지 서로 다른 값이 몇개 있는지 출력 = 중복 없는 값 출력 => set 자료형 이용해서 사이즈 구하면 되는 문제 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; ​ public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int a = 0; Set s = new HashSet(); int a.. 2022. 9. 9.
Java - [백준] 11021 A+B -7 이 문제에서 IDE를 사용하면 헷갈리는 부분이 생긴다. 예제 입력 1 5 1 1 2 3 3 4 9 8 5 2 예제 입력을 한번에 하고 예제 출력 1 Case #1: 2 Case #2: 5 Case #3: 7 Case #4: 17 Case #5: 7 예제 출력을 한번에 해야하나? 라는 의문이 생긴다. 정답은 아니다. 사람이 예제 입력을 입력하다보면 입력 속도보다 출력속도가 빨라 출력이 보이게 된다. 테스트 코드를 작성해 한번에 입력 값을 넣는 경우 입력 후 출력이 된다. 사실상 속도의 차이일 뿐 그래서 IDE에서 작성하는 경우 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j.. 2022. 9. 2.
Java - [백준] 8393번 합 문제 n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오. 이 문제는 2가지 방법으로 풀 수 있다. 반복문을 이용하거나, 수학 공식을 이용하거나 반복문 Scanner sc = new Scanner(System.in); ​ int n2 = sc.nextInt(); int sum = 0; while (n2 > 0) { sum += n2; n2--; } System.out.println(sum); 공식 Scanner sc = new Scanner(System.in); ​ int n = sc.nextInt(); int result = n*(n+1)/2; System.out.println(result); 공식을 사용하면 간단하게 문제가 해결된다. 또한 반복문은 O(n)의 시간 복잡도를 가지고 수학.. 2022. 8. 26.
728x90

티스토리툴바