백준 JAVA 풀이

문제 > 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최

크기가 N인 배열 A가 있다.배열에 있는 모든 수는 서로 다르다.이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다.그리고, 교환은 많아봐야 S번 할 수 있다.이 때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.첫째 줄에 N이 주어진다.N은 50보다

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다.그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다.그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다.이 오븐은 깊은 관처럼 생겼는데, 관의 지름이 깊이에 따라 들쭉날쭉하게 변한다

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다.방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다.숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다.문방구에서는 같은 숫자를

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의

창영이는 메모장에 '.', '\\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1\*1크기의 단위 정사각형을 나타낸다.'.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이 연결된 선분을, '\\'은 왼쪽 위 꼭짓점과 오른쪽

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.업로드중..이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.동물원 조련사의

다익스트라 문제는 처음 풀어보았다.다익스트라의 로직을 이해한 후 직접 구현해보았다. N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.다음 날부터 종수는

출발점과 도착점이 주어지지 않고,갈 수 있는대로 최대한 도달한 후,도달한 정점의 수와 가장 먼 정점의 거리를 출력하는 문제이다.일단 평범한 다익스트라 알고리즘을 작성하였다.우리가 필요한 정보는 도달한 정점들의 수와 최대 비용이다.해당하는 결과를 반환한다.

과거에 해당 문제를 시도한 적이 있지만 결국 해결하지 못하였다.당시는 다익스트라 알고리즘을 몰랐고, 단순히 2차원 배열을 이용한 BFS를 구현하였다.해당 문제는 2차원 배열을 이용한 BFS로는 시간초과가 발생하게 된다.시간을 단축하기 위해 배열을 그래프로 변환해야 한다

문제에 쓰여있는 연산은 아래와 같다.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.화면에 있는 이모티콘 중 하나를 삭제한다.해당 연산을 해석하면 이러하다.클립보드 = 화면화면 = 화면 + 클립보드화면 =

해당 문제를 풀기 위해선 조합을 필요로 한다.기본적인 백트래킹을 필요로 한다는 것이다.만들 수 있는 모든 문자열을 만든다.부등호에 알맞은 문자열인지 모두 검사한다.처음과 마지막 문자열을 출력한다. (백트래킹을 통해 조합을 했으므로 정렬되어 있을 것이다.)가장 확실하고

스도쿠 문제를 풀기 위해선 각 행, 열, 박스 마다 사용된 숫자들을 파악하는 것이 중요하다.그것을 파악하기 위해 우선 각 행, 열, 박스 별로 boolean배열을 만들었다.풀다 보니 객체지향적으로 구현하게 되었다.물론 철저히 객체지향 규칙을 지키지는 않았다구조를 박스

해당 문제가 요구하는 것은 문자열의 내용이 아닌 문자열의 길이이다.그렇기에 문자열을 길이로 다루면 편리하게 문제를 풀 수 있을 것이다.K(Q)는 Q라는 문자열을 K번 반복한다.Q를 숫자로 저장한다면, K(Q)는 K\*Q가 될 것이고 이 또한 숫자가 된다.해당 문제에서

우선 정렬이 필요해보인다.그렇다면 어떻게 정렬을 해야할까?내림차순으로 정렬이런 경우 어떠한 경우에 4에 4를 올려도 되는지 판단하기가 어려워진다.오름차순으로 정렬주어진 조건과 반대의 순서로 쌓는다고 생각한다.현재까지 쌓은 수보다 같거나 높은 수를 쌓을 수 있다.이러면

해당 문제는 하나의 회의실에서 할 수 있는 가장 많은 회의의 수를 찾는 것이다.회의가 끝나는 시각이 이른 회의부터 채워나가면 가장 많은 회의를 할 수 있다.회의가 끝나는 시각을 기준으로 정렬한다.회의가 시작하는 시각이 현재 시각보다 이르거나 같다면,회의가 끝나는 시각을

해당 문제는 평소에 풀던 다른 문제들에 비해 난이도가 있는만큼 문제를 풀기 전, 푸는 과정의 생각들을 모두 정리하며 문제를 풀었다.✍️ 풀이 과정에서는 틀린 추측과 과정이 포함되어 있다.옳은 말만 보고 싶다면 아래의 ✍️ 풀이를 보자.N개 중에 K개를 중복해서 뽑되,

어떻게 풀지 먼저 생각해보았다.A + B \* (C + D) 👉 A + B \* CD+현재 값이 닫는 괄호가 나온다면 여는 괄호가 나올 때까지 뺀다.해당 문자열들을 후위 표기식으로 바꾼 후 하나의 문자열로 다시 스택에 집어넣는다.덱을 활용해 원래 순서로 넣는다.덱

그냥 문제를 보자마자 생각난 방법이다.그냥 모든 정점에서 모든 정점으로 가는 최단거리를 구하는 것이다.플로이드 워셜 알고리즘을 알고 있다면 가장 쉽고 간단한 풀이이다.하지만 해당 문제에서 요구하는 것은한 정점을 왕복하는 거리들을 구하는 것이다.플로이드 워셜은 불필요한

오름차순으로 정렬되는 우선순위 큐와내림차순으로 정렬되는 우선순위 큐총 2개의 우선순위 큐를 활용하여 구현하였다.단순히 해당 구조로만 구현한다면하나의 큐에서 요소를 삭제해도 다른 큐에는 해당 요소가 남아있게 된다.이것을 해결하기 위해 숫자를 wrapping하는 클래스를

높이가 3이었기에 풀기에 조금 원활했던 문제였다.우선 2\*1 타일로 만들 수 있는 직사각형들을 구상했다.그 결과 위와 같이, 너비가 2인 직사각형 1개와, 너비가 2씩 증가하는 직사각형들의 집합 2개가 있음을 알아내었다.이제 2\*1 타일은 갖다 버리고 위 조각들로

단순한 미로찾기 BFS와 비슷한 문제이다.다른 점이라곤 최단시간을 찾는 대신 벽을 부수는 최소횟수를 구하는 것이다.벽을 피해 최단시간을 구하는 기존의 미로찾기는 그냥 큐를 사용하면 된다.무조건 짧은 시간이 앞으로 오기 때문이다.하지만 최단횟수를 구해야 하는 해당 문제에

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면,이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.사실 요구하는 구현은 어렵지 않다.나머지

기본적인 이분탐색 문제다.그래서 구현했다.근데 엄청 많이 틀렸다.원인은 실수에 있었다.값을 반환하는 조건에 좌우의 차이가 0.000000001보다 작다면이라는 조건을 걸었다.이러한 조건을 걸었던 이유는 절대/상대 오차는 10^-9까지 허용한다.라는 내용 때문이었다.최대

기본적인 다이나믹 프로그래밍 문제이다.이전 회차 i 들의 값들 중같은 무기 j 를 사용한 값들 중 최솟값에현재 회차의 무기 소모 시간을 더해 dp배열에 집어넣는다.이를 반복한 후, 마지막 회차에서의 최솟값을 출력하면 끝이다.해당 메소드는 다른 인덱스들의 값들을 선형으로

👨‍💻 [문제] (https://www.acmicpc.net/problem/15989) ✍️ 풀이 🏹 점화식 해당 문제는 (1, 2)와 (2, 1)을 같은 조합으로 생각한다. 그렇기에 단순히 위와 같은 점화식을 작성하게 되면, |i|0|1|2|3| |--

양방향 그래프가 입력된다.1번 노드가 루트 노드일 때의각 노드들의 부모 노드를 출력해야 한다.1번 노드부터 방문하지 않은 연결된 노드들을 탐색하며,해당 연결된 노드들의 부모 노드를 현재 노드로 기록한다.리프 노드가 나올 때까지 연결된 노드들의 방문하지 않은 연결된 노드

낮은 비용부터 N개 마셔본다. 같은 비용이라면 높은 가치 우선가치가 부족하다면 다음 낮은 비용을 마신다.N개를 넘었으니 하나를 빼야 한다. -> 가치가 가장 낮은 걸 뺀다. 같은 가치라면 높은 비용 우선낮은 비용 순으로 정렬된 맥주들, 입력된 맥주들낮은 가치 순으로 정

물병은 같은 양의 물을 가진 물병 2개만을 합칠 수 있다.1, 2, 4, 8, 16, ... 과 같은 2^n형태의 용량을 가질 수 있게 된다.이는 2진수로 1, 10, 100, ...과 같은 형태이다.즉 목표 물병의 수가 1개라면,10000... 1로 시작하고 0개 이

2차원 배열에서 (a,b)부터 (c,d)까지의 총합은 누적합을 활용하면 빠르게 구할 수 있다.누적합은 (0,0)에서부터 (x,y)까지의 총합을 빠르게 구해낼 수 있다.(3,3)에서부터 (4,4)까지의 총합을 구하고 싶다면,위 그림과 같이 파란 구역에서 필요없는 부분인

여러 개의 숫자들 중에 합의 절댓값이 가장 작은 2개의 숫자를 찾는 문제이다.투포인터를 사용할 수도 있고 이분탐색을 사용할 수도 있다.뭘 사용하던 일단 정렬을 해야 한다.단순히 오름차순으로 정렬한다.left와 right는 양 끝으로 초기화하고,둘이 만날 때까지 간격을

단순히 보면 BFS로 풀어도 좋은 문제이지만,X를 통해 떨어지는 경우, 떨어져서 도달하는 위치를 확인하는 연산을 반복하게 될 수 있기 때문에,각 칸에서 갈 수 있는 칸들을 모두 지정해놓고,다익스트라를 통해 문제를 해결해야 한다.2차원 배열을 그래프로 변환해야 한다.2차

BFS/DFS를 통해 구역을 나누는 문제이다.처음에는 양의 수와 늑대의 수를 저장한 Section이라는 클래스를 만들어ArrayList<Section>에 저장한 후,마지막에 결과를 집계하려 했으나, 굳이 클래스를 만들 필요는 없었다.마당의 구조에 대한 입력은 ch

각 자리가 등차수열을 이룬다면 한수라고 한다.자연수 N (N < 1018) 이 주어졌을 때, N보다 작은 모든 한수의 수를 구하면 된다.가장 쉽게 떠올릴 수 있는 방법이다.1018개의 모든 숫자를 한수인지 확인하면 너무 오래 걸릴 것이다.아마 시간초과 판정을 받을

여는 괄호와 닫는 괄호로 이루어진 문자열을 올바르게 수정하는 문제이다.이미 올바르게 열리고 닫히는 괄호들은 생략한다.스택을 사용하여 작업을 수행한다.아래 코드에서는 덱을 사용하였지만 스택을 사용하여도 무방하다.이 작업을 통해 }}{{와 같이 올바르지 못한 표현만 남게