본문 바로가기

전체 글113

[코딩테스트] programmers - 전력망을 둘로 나누기 - DFS와 재귀 호출 이해하기 [코딩테스트] programmers - 전력망을 둘로 나누기 - DFS와 재귀 호출 이해하기1. 문제 소개문제: 프로그래머스 - 전력망을 둘로 나누기알고리즘: 그래프(Graph), 깊이 우선 탐색(DFS)이 문제는 여러 송전탑이 전선으로 연결된 전력망에서 전선 하나를 끊어 두 개의 네트워크로 나누고, 두 네트워크에 속한 송전탑 개수의 차이가 최소가 되는 경우를 찾는 문제다.전선은 방향이 없는 연결이므로 모든 송전탑은 양방향으로 이동할 수 있다.예를 들어 다음과 같이 5개의 송전탑이 연결되어 있다고 가정하자.1 ─ 2 ─ 3 ─ 4 │ 5여기서 2번과 3번 송전탑 사이의 전선을 끊으면 다음과 같이 두 개의 네트워크로 나뉜다.1 ─ 2 3 ─ 4 │ .. 2026. 10. 16.
[코딩테스트] programmers - 피로도 - DFS와 백트래킹, visited 복구 이해하기 [코딩테스트] programmers - 피로도 - DFS와 백트래킹, visited 복구 이해하기1. 문제 개요프로그래머스의 피로도(Lv.2) 문제는 DFS와 백트래킹을 이용해 해결할 수 있는 완전 탐색 문제입니다.현재 피로도와 각 던전의 최소 필요 피로도, 소모 피로도가 주어집니다. 던전은 한 번씩만 방문할 수 있으며, 탐험할 수 있는 던전의 최대 개수를 구해야 합니다.이 문제에서 가장 중요한 부분은 다음 코드입니다.visited[i] = true;dfs( fatigue - dungeons[i][1], count + 1, dungeons);visited[i] = false;현재 던전을 방문 처리한 후 DFS를 호출하고, 재귀 호출이 끝나면 방문 상태를 복구합니다.이번 글에서는 이 코드가.. 2026. 10. 15.
[코딩테스트] programmers - 호텔 대실 - Java 풀이 및 코드 비교 [코딩테스트] programmers - 호텔 대실 - Java 풀이 및 코드 비교1. 문제 정보문제: 호텔 대실플랫폼: 프로그래머스난이도: Level 2언어: Java알고리즘: 그리디(Greedy), 정렬, 큐(Queue), 우선순위 큐(PriorityQueue)문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1556512. 문제 설명호텔 예약 정보가 담긴 2차원 배열 book_time이 주어집니다.각 예약은 입실 시각과 퇴실 시각으로 구성되어 있으며, 객실을 사용한 후에는 다음 손님을 받기 위해 퇴실 시각부터 10분간 청소해야 합니다.모든 예약을 처리하기 위해 필요한 최소 객실 수를 구해야 합니다.예를 들어 다음과 같은 예약이 있다고 .. 2026. 10. 14.
[코딩테스트] programmers - 택배상자 (Lv.2) - Stack [코딩테스트] programmers - 택배상자 (Lv.2) - Stack1. 문제 정보문제 이름: 택배상자출처: 프로그래머스난이도: Level 2사용 언어: Java핵심 알고리즘: Stack (스택)문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1317042. 문제 설명1번부터 N번까지의 택배 상자가 컨테이너 벨트를 통해 순서대로 전달된다.택배 기사님이 원하는 상자의 적재 순서는 order 배열에 주어진다.컨테이너 벨트에서는 상자를 순서대로 꺼낼 수 있다. 원하는 순서와 다른 상자는 보조 컨테이너에 보관할 수 있지만, 보조 컨테이너는 입구가 하나뿐이므로 마지막에 넣은 상자를 가장 먼저 꺼내야 한다.이러한 구조를 LIFO(Last In.. 2026. 10. 14.
[코딩테스트] programmers - 네트워크 - DFS로 연결된 컴퓨터 그룹 찾기 [코딩테스트] programmers - 네트워크 - DFS로 연결된 컴퓨터 그룹 찾기1. 문제 설명네트워크 문제는 컴퓨터 간의 연결 정보가 주어졌을 때, 네트워크가 몇 개 존재하는지 구하는 문제이다.네트워크란 컴퓨터들이 서로 연결되어 정보를 교환할 수 있는 집합을 의미한다.컴퓨터 A와 컴퓨터 B가 연결되어 있고, 컴퓨터 B와 컴퓨터 C가 연결되어 있다면 컴퓨터 A와 C가 직접 연결되어 있지 않더라도 같은 네트워크에 속한다.이 문제에서는 컴퓨터의 개수 n과 컴퓨터 간의 연결 정보를 나타내는 2차원 배열 computers가 주어진다. 연결되어 있는 컴퓨터들을 하나의 네트워크로 묶고, 전체 네트워크의 개수를 반환하면 된다.입출력 예제 n computers return 3[[1,1,0],[1,1,0],[0,.. 2026. 10. 13.
[코딩테스트] programmers - 게임 맵 최단거리 - BFS(너비 우선 탐색) Java 풀이 [코딩테스트] programmers - 게임 맵 최단거리 - BFS(너비 우선 탐색) Java 풀이1. 문제 소개게임 맵 최단거리 문제는 시작점에서 도착점까지 이동할 때 지나야 하는 칸의 최솟값을 구하는 문제다.맵은 2차원 배열로 주어지며, 각 칸은 다음과 같은 의미를 가진다.1: 이동할 수 있는 칸0: 벽이므로 이동할 수 없는 칸상하좌우로만 이동할 수 있으며, 시작점은 좌측 상단 (0, 0), 도착점은 우측 하단 (N - 1, M - 1)이다.도착점에 도달할 수 없다면 -1을 반환한다.문제 해결의 핵심이 문제는 BFS(Breadth-First Search, 너비 우선 탐색)를 사용하면 효율적으로 해결할 수 있다.BFS는 시작점에서 가까운 위치부터 차례대로 탐색하는 알고리즘이다. 모든 이동 비용이 1로 .. 2026. 10. 12.
[코딩테스트] Geometry - 사각형 둘레로 최대 좌표 개수 구하기 [코딩테스트] Geometry - 사각형 둘레로 최대 좌표 개수 구하기1. 문제 소개2차원 좌표와 사각형의 둘레가 주어졌을 때, 사각형 안에 포함할 수 있는 좌표의 최대 개수를 구하는 문제입니다.함수 시그니처는 다음과 같습니다.public int maxPointsWithPerimeter(Map2D[] map, int perimeter)입력 데이터는 다음과 같은 Map2D 클래스로 표현합니다.class Map2D { int X; int Y; Map2D(int x, int y) { this.X = x; this.Y = y; }}문제 조건좌표는 제1사분면부터 제4사분면까지 모두 사용할 수 있습니다.perimeter는 사각형의 한 변의 길이가 아니라 둘레입니다.사각.. 2026. 10. 11.
[코딩테스트] Stack - Word Machine 문제 풀이 (Java) [코딩테스트] Stack - Word Machine 문제 풀이 (Java)1. 문제 소개Word Machine은 문자열에 포함된 숫자와 명령어를 순서대로 읽고, 스택(Stack)을 이용해 연산을 수행하는 문제입니다.이 문제의 핵심은 문자열을 파싱(Parsing)하고, 각 명령어에 맞는 스택 연산을 실행한 뒤 최종 결과를 반환하는 것입니다.함수 시그니처는 다음과 같습니다.int solution(String S)입력값: 숫자와 명령어로 구성된 문자열 S반환값: 모든 명령어를 실행한 후 스택의 최상단에 남아 있는 값연산 오류가 발생하거나 최종 스택이 비어 있다면 -1 반환이 문제는 Stack, String Parsing, Simulation 유형으로 분류할 수 있습니다.2. 명령어 정의Word Machine은.. 2026. 10. 11.
[코딩테스트] Tree - 밸런스 노드 개수 구하기 [코딩테스트] Tree - 밸런스 노드 개수 구하기1. 문제 설명트리(Tree)가 주어졌을 때, 트리에 존재하는 밸런스 노드(Balanced Node)의 개수를 반환하는 문제입니다.함수 시그니처는 다음과 같습니다.int solution(Node tree)tree: 트리의 루트 노드반환값: 밸런스 노드의 개수이 문제에서는 트리 전체가 균형 잡혀 있는지 판단하는 것이 아니라, 각 노드가 밸런스 조건을 만족하는지 확인하고 그 개수를 반환해야 합니다.밸런스 노드의 조건이 문제에서는 다음 조건을 기준으로 밸런스 노드를 판단합니다.자식이 없는 노드(리프 노드)는 밸런스 노드입니다.자식이 하나인 노드도 밸런스 노드입니다.자식이 두 개 이상인 노드는 모든 자식의 직계 자식 개수가 같아야 밸런스 노드입니다.여기서 비교하.. 2026. 10. 11.
[코딩테스트] Codility - FrogRiverOne - 개구리 강 건너기 [코딩테스트] Codility - FrogRiverOne - 개구리 강 건너기1. 문제 소개문제 설명개구리는 강의 시작 위치인 0에서 반대편 위치인 X + 1로 이동하려고 한다.강을 건너려면 위치 1부터 X까지 모든 위치에 나뭇잎이 떨어져 있어야 한다.정수 배열 A에서 A[K]는 시간 K초에 나뭇잎이 떨어진 위치를 의미한다.모든 위치에 나뭇잎이 놓이는 가장 빠른 시간을 반환하는 함수를 작성한다.모든 위치가 채워지면 가장 빠른 시간 반환모든 위치가 채워지지 않으면 -1 반환예제X = 5;A = [1, 3, 1, 4, 2, 3, 5, 4];시간에 따른 나뭇잎의 위치는 다음과 같다. 초 위치 새 위치 개수 0111133221중복23443422453중복46555시간 6에 위치 1, 2, 3, 4, 5가 모.. 2026. 10. 11.
[코딩테스트] Codility - MaxCounters (카운터 최댓값 갱신) [코딩테스트] Codility - MaxCounters (카운터 최댓값 갱신)1. 문제 소개이번에 풀어본 문제는 Codility의 MaxCounters이다.정수 N과 배열 A가 주어질 때, N개의 카운터를 다음 두 가지 연산으로 처리하고 최종 카운터 값을 반환하는 문제이다.모든 카운터는 처음에 0으로 초기화된다.연산 종류1. 개별 카운터 증가A[K]가 1부터 N 사이의 값이라면 해당 카운터를 1 증가시킨다.A[K] = Xcounter[X - 1]++카운터 배열의 인덱스는 0부터 시작하기 때문에 X - 1을 사용한다.2. 모든 카운터를 현재 최댓값으로 갱신A[K]가 N + 1이라면 모든 카운터를 현재 카운터의 최댓값으로 설정한다.counter[i] = 현재 최댓값이 연산이 반복해서 등장할 수 있다는 점이 .. 2026. 10. 11.
[코딩테스트] Codility - PassingCars (차량 쌍 계산하기) [코딩테스트] Codility - PassingCars (차량 쌍 계산하기)1. 문제 소개이번에 풀어본 문제는 Codility의 PassingCars이다.정수 배열 A가 주어졌을 때, 동쪽으로 이동하는 차량과 서쪽으로 이동하는 차량이 서로 교차하는 쌍의 개수를 구하는 문제이다.배열의 각 원소는 다음과 같은 의미를 가진다.0: 동쪽으로 이동하는 차량1: 서쪽으로 이동하는 차량인덱스 P와 Q가 P 를 만족하고, A[P] = 0, A[Q] = 1이라면 두 차량은 하나의 교차 쌍을 형성한다.예제int[] A = {0, 1, 0, 1, 1};배열에서 발생하는 차량 쌍을 살펴보면 다음과 같다.첫 번째 0은 오른쪽에 있는 세 개의 1과 쌍을 이룬다.두 번째 0은 오른쪽에 있는 두 개의 1과 쌍을 이룬다.따라서 전체 .. 2026. 10. 11.
반응형

티스토리툴바