처음 문제를 접했을 땐, 조합을 떠올렸지만 50,000개 중 2개를 뽑는 경우의 수에는 20억번의 연산이 포함되므로, 효율성 측면에서 낮다고 판단하였다. 그렇다면 시간 효율성을 높일 수 있는 방안 중 어떤 것이 있을까 고민하던 중,하나씩 빼면서 탐색을 하는 것 자체가 모든 경우를 조사해야하는 경우를 포함하므로 거꾸로, 최대가 되는 거리를 미리 정해서 이진 탐색을 활용하여 해당 거리를 줄여나가는 방식으로 문제를 해결하였다. 제한 사항에 변수가 1억 이상으로 나와있다면, 시간 효율성을 고려한 알고리즘을 항상 고려해야한다.1억개 이상의 크기를 갖는 배열을 만들어 이를 숫자별로 만든다면 시간 효율성은 떨어질 수 밖에 없다. import java.util.*;class Solution { public in..
알고리즘/문제풀이
이 문제에서 사용된 알고리즘은 투 포인터(Two Pointers) 알고리즘입니다. 투 포인터 알고리즘은 배열 내에서 두 개의 포인터(인덱스)를 사용해 문제를 해결하는 방법으로, 주로 배열을 양쪽에서 비교하거나 합을 조정할 때 사용됩니다.투 포인터 알고리즘 개요투 포인터 알고리즘은 두 개의 포인터를 사용해 배열을 순차적으로 탐색하면서 조건에 맞는 값을 찾는 방법입니다.배열의 특정 구간을 탐색하거나 두 부분 간의 합이나 차이를 비교하는 문제에서 자주 쓰입니다.일반적으로 두 개의 포인터가 배열의 서로 다른 위치에 놓이고, 필요한 상황에 따라 한 포인터를 왼쪽 또는 오른쪽으로 이동시킵니다.이 문제에서의 투 포인터 알고리즘은 배열을 중간 기준으로 나눠, 왼쪽과 오른쪽에서 각각의 부분 합을 비교하면서 최적의 값을 ..
문제 설명"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.한 번에 한 명씩 신청한 순서대로 방을 배정합니다.고객은 투숙하기 원하는 방 번호를 제출합니다.고객이 원하는 방이 비어 있다면 즉시 배정합니다.고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다..
목차 문제 해석 사고 과정 코드 구현 회고록 문제 해석 폴리오미노 : 1X1 정사각형 이어 붙임 겹침 X, 도형 모두 연결, 변끼리만 연결 4개 이어 붙인-> 테트로미노 회전 or 대칭 가능 한 개의 테트로미노가 놓인 칸에 쓰혀 있는 수들의 합 최대 4 DFS 활용하기 **Point ㅁ, ㅏ, ㅜ, ㅓ, ㅗ의 경우 각 이동 횟수가 2일 때, 추가로 네 방향 탐색을 시행해야만 한다 코드 구현 DFS의 응용 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 테트로미노 { static int N, M, max; ..
목차 문제 해석 사고 과정 코드 구현 회고록 문제 해석 문제에서 의미하는 단어들을 명확히 하는 단계입니다 2048 게임은 4 X 4 크기의 보드에서 즐기는 게임 한 번의 이동은 보드 위 전체블록을 상하좌우 중 하나로 이동 같은 값 두 블록 충돌 -> 하나로 합쳐짐 단 한 번의 이동에서 합쳐진 블록은 다시 합쳐짐 X (블록 추가 X) 블록은 적어도 하나가 주어진다. 충돌의 의미? 같은 값을 갖는 두 블록 충돌 -> 합쳐진다. 세개 붙어있으면, 이동하려는 쪽으로 부터 가까운애들이 먼저 합쳐진다. 5번 이동해서 만들 수 있는 가장 큰 블록의 값? 사고 과정 5번 이동, 상하좌우 랜덤하게 모든 경우의 수 구해서 최댓값 갱신하는 형태 -> 5번 이동 후 최대값 조사 -> 재귀적 구현 + 이전 게임보드의 값을 저장..
목차 문제 해석 사고 과정 코드 구현 회고록 문제 해석 1. 양방향 간선, 지역구별 인구가 존재,최소의 선거구 차이, 못 나눌 경우 -1 2. 한 선거구는 반드시 하나로 연결되어 었어야 함 3. 모두 연결이라는 말은 없음, 둘 혹은 셋 이상의 연결 그룹이 나올 수 있다는 것 인지 사고 과정 1. 각 노드에 연결된 간선 저장 2. 숫자가 순서대로 연속되어 있으니 카운팅 배열 사용하여 인구수 저장 3. 어떻게 각 선거구를 나눌 것인가, (조건 각 선거구의 전체 합이 총 인구수가 되야 한다) 4. 완전탐색 활용하여, 모든 경우의 수에 대한 각 그룹별 노드의 연결성 유무 확인하기 - > 부분 집합 + BFS 코드 구현 핵심 알고리즘 개념 부분집합 + BFS (너비 우선 탐색) public class 강게리맨더링..
