백준 14499번 : 주사위 굴리기 [Java]

문제 탐색하기간단한 시뮬레이션 문제이다. 문제에서 요구하는건 주사위를 지도위에 따라서 굴리고 지도 바깥으로 벗어나지 않을 때만 해당 주사위의 top을 출력하면 된다. 시간 복잡도는 O(M)으로 계산해볼 수 있다. 실제 연산에 드는 시간이 크지 않고 들어오는 M의 값에 따라서만 달라지면 된다. 주사위를 하나의 클래스로 생성하고 top, bottom, right, left, front, rear 이런 식으로 이름을 붙여서 돌리는 연산을 수행하였다. 이전에 문제를 풀었을 때는 위와 같이 하지 않고 주사위 자체도 2차원 배열로 설정하여 풀었었는데, 주사위에게 좌표 값을 입력해주지 않아도 되는 걸 생각해보면 위와 같은 방식이 구현할 때 어렵지 않고 효율적일 듯 하다. 이 때 연산의 종류와 상관없이 지도 바깥으로 ..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 11.
• textsms

백준 1561번 : 놀이 공원 [Java]

https://www.acmicpc.net/problem/1561 문제 탐색하기 꽤나 애를 많이 먹은 문제였다. 처음에는 여러 자료 구조를 이용해서 시간복잡도 안에 해결할 수 있을 듯하였다. 이에 따라서 M개의 놀이기구를 각각 HashMap (Python의 Dictionary)에 시간 별로 나누어 저장하고 매 시간 마다 계산 하도록 하였다...  처음 생각했던 위 풀이는 공간 복잡도 (메모리 초과)로 통과할 수 없었는데 이는 매번 리스트를 생성 하고 저장하는 것과 HashMap에 리스트를 저장해야하는 것에서 비효율적이지 않나 생각된다. 하지만 위 풀이대로 한다해도 매번 1분씩 시간을 더했기 때문에 주어진 시간안에 연산할 수 없을 것이 분명했고 다른 방법을 생각했다. N은 최대 20억, M은 1만이다. 1..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 10.
• textsms

백준 12015번 : 가장 긴 증가하는 부분 수열 2 [Java]

https://www.acmicpc.net/submit/12015 문제 탐색하기주어진 N 길이의 수열에서 제일 긴 증가하는 수열을 찾아내는 문제이다. 입력의 개수가 훨씬 더 작았다면 O(N^2)시간에도 찾을 수 있지만 N의 최대가 100만 인 만큼 O(N^2) 시간안에 풀 수 없다. 따라서 다른 방법을 통해 정답을 찾아야 한다.  완전 탐색을 하지 않더라도 여전히 N만큼의 탐색시간을 거쳐야 한다. 어떤 방법으로 이걸 찾을 수 있을까? 리스트를 하나 두고 해당 연결리스트에 값을 추가하거나 새로 수정하여 구하는 방법을 통해서 O(Nlog(N)) 시간 안에 답을 찾을 수 있다. 다음은 문제에서 나온 예제이다. 이를 통해서 어떤 방식으로 O(Nlog(N)) 시간 안에 답을 찾을 수 있는지 알아보자.610 20 ..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 9.
• textsms

백준 2473번 : 세 용액 [Java]

https://www.acmicpc.net/problem/2473 문제 탐색하기- 10억 ~ 10억 사이의 용액의 특성 값이 주어질 때 세 용액의 합이 0에 제일 가까울 경우를 출력하도록 하는 문제이다. N의 최소는 3 ~ 5000 사이의 수 일 때 위 세 용액을 어떻게 섞어야 할까? 시간 복잡도와 풀이를 생각해보기 전에 먼저 다양한 입력을 고려해봤다.용액이 단 3개만 주어질 때알칼리 용액만 주어질 때 (입력에 음수만 존재할 때)산성 용액만 주어질 때 (입력에 양수만 존재할 때)알칼리, 산성 용액이 모두 주어질 때1번의 경우 정렬 후 출력만 하면 된다. 2, 3번의 경우도 마찬가지로 정렬 후 절댓값이 0과 가까운 세 수를 출력하면 된다. 여기서 해결해야 할 문제는 4번의 경우이다. 여러 예제를 통해 아래..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 8.
• textsms

백준 1477번 : 휴게소 세우기 [Java]

https://www.acmicpc.net/submit/1477?solve=true문제 탐색하기문제는 휴게소 사이의 간격의 최대 값이 최소가 되게 하는 길이를 구해야 한다.  처음에 문제가 잘 이해가 되지 않아서 풀어서 써야했다. 1번 예제를 중심으로 문제를 생각해보면// 아래는 예제에 있는 수에 시작(0)과 끝(800)을 더해서 오름차순으로 정렬한 형태이다.[0, 82, 201, 411, 555, 622, 755, 800] 먼저 두 지점 사이의 간격을 구하려면 위 배열을 i + 1번째 수에서 i번째 수를 빼서 다시 배열로 만들면 각 지점 사이의 거리가 보인다.[82, 119, 210, 144, 67, 133, 45] 이렇게 바꾸니 뭔가 좀 보이는 듯 하다. 예제 1번의 답이 70인걸로 미루어보아서 이 ..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 7.
• textsms

백준 8895번 : 막대 배치 [Java]

https://www.acmicpc.net/problem/8895문제 탐색하기문제는 높이가 1, 2, 3 ... n인 막대 n개를 양쪽에서 봤을 때 각각 l, r에 해당하는 수만큼 막대가 보이는 경우의 수를 구하면 된다. 일단 예제부터 범상치않다. 막대 20개일 때 왼쪽에서 2개, 오른쪽에서 1개가 보이는 경우의 수는 아래와 같다.6402373705728000 // 64경 2373조 7057억 2800만 몇 가지를 고려해보며 어떻게 이런 큰 수가 나올 수 있는 지 생각해보면 된다. 1. 가장 큰 막대(n)를 맨 앞에 두는 경우n이 맨 앞에 있을 때, 왼쪽에서는 무조건 제일 긴 막대인 n만 보인다. 이 때 n을 제거하면 남은 n - 1개의 막대에서 (l - 1, r)을 만족하는 경우의 수를 구하는 문제와 ..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 6.
• textsms