본문 바로가기

전체 글109

[코딩테스트] 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.
[코딩테스트] Codility - Distinct (서로 다른 숫자의 개수) [코딩테스트] Codility - Distinct (서로 다른 숫자의 개수)1. 문제 소개이번에 풀어본 문제는 Codility의 Distinct 문제이다.정수 배열 A가 주어졌을 때, 배열에 존재하는 서로 다른 숫자의 개수를 반환해야 한다.예를 들어 다음과 같은 배열이 있다.int[] A = {2, 1, 1, 2, 3, 1};배열에는 1, 2, 3이라는 세 종류의 숫자가 존재한다.따라서 결과는 다음과 같다.결과: 3같은 숫자가 여러 번 등장하더라도 한 번만 계산한다는 것이 핵심이다.2. 내가 작성한 코드이번 문제는 Java의 HashSet을 활용하여 해결했다.import java.util.HashSet;public int solution(int[] A) { HashSet hs = new HashSe.. 2026. 10. 11.
[코딩테스트] Codility - TapeEquilibrium 문제 풀이 - 누적 합으로 최소 차이 구하기 (Java) [코딩테스트] Codility - TapeEquilibrium 문제 풀이 - 누적 합으로 최소 차이 구하기 (Java)1. 문제 소개Codility의 TapeEquilibrium 문제는 배열을 두 개의 비어 있지 않은 부분으로 나누었을 때, 두 부분의 합의 차이를 최소화하는 문제다.배열 A가 주어지면 분할 위치 P는 다음 조건을 만족해야 한다.0 분할 위치를 기준으로 왼쪽과 오른쪽 배열의 합을 구하고, 두 합의 차이의 절댓값을 계산한다.차이 = |왼쪽 합 - 오른쪽 합|모든 가능한 분할 위치 중에서 차이가 가장 작은 값을 반환해야 한다.예제int[] A = {3, 1, 2, 4, 3};배열을 나눌 수 있는 위치는 P = 1, 2, 3, 4다.P왼쪽 합오른쪽 합합의 차이131072495367141037최소.. 2026. 10. 10.
[코딩테스트] Codility - PermMissingElem - 배열에서 누락된 숫자 찾기 (Java) [코딩테스트] Codility - PermMissingElem - 배열에서 누락된 숫자 찾기 (Java)1. 문제 소개Codility의 PermMissingElem 문제는 배열에 있어야 할 숫자 중 누락된 하나의 숫자를 찾는 문제다.배열 A에는 1부터 N + 1까지의 정수가 들어가야 한다. 단, 숫자 하나가 빠져 있으며 나머지 숫자는 모두 서로 다른 값이다.문제 조건배열의 길이 N은 0 이상 100,000 이하이다.배열의 모든 원소는 서로 다른 정수다.원소의 범위는 1부터 N + 1까지다.배열에서 누락된 숫자 하나를 반환해야 한다.예제int[] A = {2, 3, 1, 5};배열의 길이는 4이므로 전체 숫자의 범위는 1부터 5까지다.전체 숫자: 1, 2, 3, 4, 5배열에 존재하는 숫자: 1, 2, 3.. 2026. 10. 10.
[코딩테스트] Codility - FrogJmp 문제 풀이 - Java 시간 복잡도 O(1)로 개선하기 [코딩테스트] Codility - FrogJmp 문제 풀이 - Java 시간 복잡도 O(1)로 개선하기1. 문제 소개Codility의 FrogJmp 문제는 개구리가 목표 위치에 도달하기 위해 필요한 최소 점프 횟수를 구하는 문제다.개구리는 현재 위치 X에 있으며, 한 번 점프할 때마다 일정한 거리 D만큼 이동한다. 목표 위치는 Y이며, 목표 위치를 지나쳐도 도달한 것으로 인정한다.문제 조건X: 개구리의 현재 위치Y: 목표 위치D: 한 번 점프하는 거리X ≤ Y모든 입력값은 1 이상 1,000,000,000 이하의 정수다음 조건에서 최소 점프 횟수를 구해야 한다.X = 10;Y = 85;D = 30;개구리의 이동 경로는 다음과 같다.점프 횟수도착 위치0101402703100세 번째 점프에서 85 이상인 1.. 2026. 10. 10.
반응형

티스토리툴바