개발 쥬스

🔗 문제 링크: https://www.acmicpc.net/problem/17470 🔍 해결 과정배열 돌리기 3 문제와 내용은 같으나 연산의 수 R의 최댓값이 200만이라는 점에서 차이가 있습니다.직접 배열의 내용 자체를 가지고 연산을 활용하기에는 시간복잡도 O(NMR)을 가지기 때문에 최악의 경우 200만 x 10000 = 200억의 연산이 진행이 되기에 일반적인 풀이로는 시간초과가 발생합니다. 그래서 처음에는 배열의 내용들을 바탕으로 연산하기보다는 배열의 영역을 매핑하여 압축시키고 이를 바탕으로 연산을 진행해야겠다는 생각을 했습니다. 즉 그림으로 표현하자면 다음과 같습니다.  위 네 가지의 영역을 바탕으로 2 x 2 압축된 배열을 만들고 R번 연산을 진행을 하게 된다면 최대 2 X 2 X 200만..

🔗 문제 링크: https://www.acmicpc.net/problem/13460  🔍 해결 과정bfs 시뮬레이션 문제로  빨간 구슬과 파란 구슬이 동시에 움직여 위치를 겹치지 않게 처리하는 과정에서 시간이 걸렸던 문제였습니다. 전체적인 과정을 요약하자면 다음과 같습니다.1️⃣ 빨간 구슬과 파란 구슬의 위치정보, 그리고 이동 횟수를 저장하는 Pair 클래스를 하나 만든다.2️⃣ 빨간 구슬과 파란 구슬의 위치의 조합이 방문되었는지 확인하기 위해서 4차원 boolean 배열의 형태를 가진 visited 배열을 만든다.3️⃣ bfs를 통해서 빨간 구슬과 파란 구슬의 이동 정보를 큐에 담을텐데 먼저 보드판을 상하좌우 흔들며 빨간 구슬과 파란 구슬을 이동처리를 한다.4️⃣ 여기서 빨간 구슬과 파란 구슬이 가..

🔗 문제 링크: https://www.acmicpc.net/problem/9202 🔍 해결 과정이 문제를 간단히 요약하자면 최대 30만 값을 가진 w개의 단어 사전들이 존재하는데 최대 29번의 boggle을 진행해서 각 경우마다 단어사전에 해당하는 단어들을 찾은 다음 문제의 요구에 맞게 정답을 출력하면 되는 문제입니다. w의 최댓값이 30만이라는 점에서 시간복잡도를 최적화해야겠다는 생각이 들었지만, boggle 보드판의 크기는 4x4이고, 단어의 길이도 최대 8이라는 점을 감안했을 때 dfs와 가지치기(pruning)를 활용하여 백트래킹 기법을 사용해 시간 안에 문제를 해결할 수 있습니다. (참고로 문제에서 요구하는 최대 시간은 10초입니다.) 또한 단어 사전에 들어있는 단어의 개수가 최대 30만개이..

🔗 문제 링크: https://www.acmicpc.net/problem/14942 🔍 해결 과정처음에 이 문제를 접하고 들었던 생각은 dfs를 통해서 각 개미 노드 번호의 부모 노드 번호 정보를 저장한 다음 저장한 부모 노드 정보를 활용하여 개미의 에너지를 사용했을 때 최대로 거슬러 올라갈 수 있는 부모 노드의 번호를 저장하는 방식으로 구현했습니다. 과정을 요약하자면 다음과 같습니다.1️⃣ 개미의 방 구조를 나타내는 이중 연결 리스트 graph를 통해서 방의 구조 형태를 그린다. 이 때 양방향으로 연결한다.2️⃣ 개미의 에너지 정보 배열 energies, 개미의 부모 정보 배열 parent, 개미의 에너지를 활용하여 가장 가까운 방 번호 저장용 배열 result를 만들어준다. 각각의 배열은 일차원 ..

🔗 문제 링크: https://www.acmicpc.net/problem/21609🔍 해결 과정이 문제는 시뮬레이션 문제로 시간 초과 걱정할 필요 없이 조건에 맞춰 문제를 해결하면 됩니다. 개인적으로 코드를 작성하는 과정에 있어서 디버깅 등의 시간도 할애하느라 시간을 많이 썼던 문제였습니다. 처음에 문제를 보고 핵심 조건에 맞춰서 그에 맞는 메서드를 분류했습니다. 핵심 기능들은 다음과 같습니다.1️⃣ 크기가 가장 큰 블록 그룹을 찾는 기능2️⃣ 기준 블록이 속한 블록 그룹에 있는 블록들을 제거하는 기능 (제거하면서 점수를 반환한다.)3️⃣ 중력 작용 기능4️⃣ 90도 반시계 방향 회전 기능 메인 함수에서는 위와 같이 4개의 핵심 기능들을 정의하였고, 조건에 맞춰서 핵심 기능들을 구현하는 방향으로 문제..

🔗 문제 링크: https://www.acmicpc.net/problem/2470🔍 해결 과정서로 합했을 때 그 절댓값이 0에 제일 가까운 두 용액을 찾아내는 것이 문제의 핵심이므로 투 포인터 방식을 활용(시간 복잡도: O(N), N: 용액의 개수)하였습니다.두 용액의 절댓값에 대한 처리와 두 용액을 서로 저장하는 과정에 있어서 고민을 좀 했었던 문제입니다.✏️ 코드import java.io.*;import java.util.Arrays;public class Main { private static final String SPACE = " "; public static void main(String[] args) throws IOException { BufferedReader ..