알고리즘
-
[프로그래머스] 부족한 금액 계산하기 - 자바(JAVA)알고리즘/프로그래머스 2022. 7. 10. 00:01
https://programmers.co.kr/learn/courses/30/lessons/82612 코딩테스트 연습 - 부족한 금액 계산하기 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 문제 해석 새로 생긴 놀이기구는 인기가 너무 많아 줄이 끊이지 않습니다. 원래 이용료는 price인데 놀이기구를 N번째로 이용한다면 원래 이용료의 N배를 받습니다. 처음 이용료가 100이라면 2번째는 200, 3번째는 300으로 요금이 인상됩니다. 놀이기구를 count번 타게 되면 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 r..
-
[백준] 2536번 : 버스 갈아타기 - 자바(JAVA)알고리즘/백준 2022. 7. 8. 00:01
https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net 문제 해석 2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있습니다. 아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예시입니다. 가로 7 세로 6 이 도로망을 운행하는 버스들이 k개 존재하며 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 수직선 상의 두 교차점 사이 선분을 왕복 운행합니다. 즉, 가..
-
[백준] 1981번 : 배열에서 이동 - 자바(JAVA)알고리즘/백준 2022. 7. 6. 00:01
https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 해석 n x n 배열이 존재하고 배열의 (1,1)에서 (n, n)까지 이동하려고 합니다. 이동할 때는 상하좌우로 1칸씩 이동할 수 있습니다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하세요 문제 풀이 전 설계 n의 범위는 최대 100 x 100으로 10,000입니다. 세 가지 풀이가 떠올랐습니다. 1. 파라메트릭 서치 배열의 각 ..
-
[백준] 7453번 : 합이 0인 네 정수 - 자바(JAVA)알고리즘/백준 2022. 7. 5. 00:01
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 해석 정수로 이루어진 크기가 같은 배열 4개가 존재합니다. A[a], B[b], C[c], D[d] 의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하세요 배열의 크기 최대(4000) 배열에 들어있는 정수의 최대는 2^28입니다. 문제 풀이 전 설계 시간 제한이 12초인 점이 가장 먼저 눈에 들어왔습니다. 또한 정수의 절댓값은 2^28인데 4개의 배열..
-
[백준] 13397번 : 구간 나누기2 -자바(JAVA)알고리즘/백준 2022. 7. 3. 00:01
https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 문제 해석 N개의 수로 이루어진 1차원 배열이 있다. 배열을 M개 이하의 구간으로 나누어 구간의 점수를 최댓값을 최소로 하려고 합니다. 1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다. 2. 배열의 각 수는 모두 하나의 구간에 포함되어야 한다. 이때 구간의 점수는 구간에 속한 수의 최댓값과 최솟값의 차이입니다. 예를 들어 배열이 1 5 4 6 2 ..
-
[백준] 2110번 : 공유기 설치 - 자바(JAVA)알고리즘/백준 2022. 7. 2. 00:01
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 해석 집 N개가 수직선 위에 존재하고 집 여러 개가 같은 좌표를 가지는 일은 없다. 공유기 C개를 설치하려고 하는데 한 집에는 공유기를 하나만 설치할 수 있다. 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. 집의 개수와 공유기의 개수가 주어질 때 두 공유기 사이의 최대 거리를 출력하라. 문제 풀이 전 설계 집의 개..
-
[백준] 16566번 : 카드 게임 - 자바(JAVA)알고리즘/백준 2022. 6. 28. 00:01
https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 해석 철수와 민수는 카드 게임을 즐겨한다. 1. N개의 빨간색 카드가 있으며 1부터 N까지 번호가 매겨져 있다. 2. N개의 파란색 카드가 있으며 1부터 N까지 번호가 매겨져 있다. 3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다. 4. 철수와 민수는 고른 카드 중 1장을 뒤집어진 상태로 낸다. 5. 카드 번호가 큰 사람이 ..
-
[백준] 1799번 : 비숍 - 자바(JAVA)알고리즘/백준 2022. 6. 27. 00:01
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제 해석 서양 장기인 체스에 대각선 방향으로 움직일 수 있는 비숍이 있습니다. 비숍의 위치라 B라고 했을 때 다음 그림처럼 움직일 수 있습니다. 이때 색칠된 부분에는 비숍을 놓을 수 없지만 지나갈 수는 있다고 하겠습니다. 이와 같은 체스판에 서로가 서로가 잡을 수 없는 비숍을 놓는다면 최대 7개의 비숍을 넣을 수 있습니다. 비숍의 최대 개수를 구하는 프로그램을 작성하세요. 체스판의 크기는 10 이하의 자..