[카테고리:] C# 코딩테스트 강좌

안녕하세요! 이번 포스트에서는 취업용 알고리즘 시험 문제 풀이 강좌의 두 번째 편으로, C#을 사용한 구간 합 구하기 문제를 다루어 보겠습니다. 이 문제는 연속된 수의 합을 구하는 간단한 문제처럼 보이지만, 효율적인 방법으로 접근해야 할 필요가 있습니다.

문제 정의

주어진 정수 배열 nums와 두 정수 left, right가 있습니다. 우리는 nums 내에서 인덱스 left에서 right까지의 구간 합을 계산하는 문제를 해결해야 합니다. 구간 sum을 다음의 수식으로 정의합니다:

sum = nums[left] + nums[left + 1] + ... + nums[right]

배열의 길이는 1 이상 10^5 이하이며, left와 right는 각각 0과 nums.Length - 1 사이의 값입니다.

예제

입력

nums = [1, 2, 3, 4, 5]
left = 1
right = 3

출력

sum = 9

여기서 구간 합은 2 + 3 + 4 = 9입니다.

문제 접근 방법

이 문제를 해결하기 위해서는 두 가지 접근 방법을 고려할 수 있습니다:

• 직접적인 반복문을 사용한 방법
• 더 효율적인 방법으로 접두사 배열을 사용하는 방법

1. 직접적인 반복문 사용

먼저, 가장 간단한 방법은 해당 구간을 반복문을 통해 순회하며 합을 구하는 것입니다. 하지만 이 방법은 구간의 크기가 클 경우 시간 복잡도가 O(n)이 되어 비효율적입니다.

2. 접두사 배열 사용

이 문제를 더 효율적으로 해결하기 위해 접두사 배열을 사용할 수 있습니다. 접두사 배열(Prefix Sum)은 주어진 배열의 각 인덱스에서의 누적 합을 저장하여 반복문을 줄여줍니다.

접두사 배열을 구성하는 과정은 다음과 같습니다:

prefix[0] = nums[0]
prefix[i] = prefix[i - 1] + nums[i] (1 ≤ i < nums.Length)

이렇게 구성된 접두사 배열을 활용하면, 구간 합을 O(1)의 시간 복잡도로 계산할 수 있습니다. 구간 합은 다음과 같이 계산됩니다:

sum = prefix[right] - prefix[left - 1] (left > 0)
sum = prefix[right] (left == 0)

C# 코드 구현

이제 위에서 설명한 방법으로 C# 코드를 작성해 보겠습니다. 아래의 코드는 입력으로 주어진 배열 및 구간을 바탕으로 구간 합을 계산합니다.

코드

using System;

class Program {
    static void Main(string[] args) {
        int[] nums = { 1, 2, 3, 4, 5 };
        int left = 1;
        int right = 3;

        int result = GetRangeSum(nums, left, right);
        Console.WriteLine(result);
    }

    static int GetRangeSum(int[] nums, int left, int right) {
        int n = nums.Length;
        int[] prefix = new int[n];
        prefix[0] = nums[0];

        // 접두사 배열 초기화
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        // 구간 합 계산
        if (left == 0) {
            return prefix[right];
        }
        return prefix[right] - prefix[left - 1];
    }
}

이 코드는 주어진 배열 nums와 구간 left와 right를 인자로 받아서 구간 합을 반환합니다. 접두사 배열을 사용하여 구간 합을 효율적으로 계산할 수 있습니다.

복잡도 분석

이제 우리가 작성한 코드의 시간 및 공간 복잡도를 분석해 보겠습니다.

시간 복잡도

접두사 배열을 초기화하는 과정은 O(n)의 시간 복잡도를 가지며, 구간 합을 계산하는 과정은 O(1)의 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도는 O(n)입니다.

공간 복잡도

접두사 배열을 저장하기 위해 O(n)의 추가 공간이 필요하므로, 공간 복잡도 또한 O(n)입니다.

결론

이번 포스트에서는 구간 합 구하기 문제를 다루었습니다. 접두사 배열을 활용한 효율적인 접근 방법을 통해 구간 합을 O(1)의 시간 복잡도로 계산할 수 있게 되었습니다. 이 기법은 다양한 알고리즘 문제에 유용하게 적용될 수 있으므로, 꼭 기억해 두시기 바랍니다.

다음 포스트에서는 또 다른 알고리즘 문제를 다루겠습니다. 감사합니다!

안녕하세요! 이번 포스트에서는 C#을 이용한 코딩 테스트 문제 중 ‘선분의 교차 여부 구하기’에 대해 다루어 보겠습니다.
이 문제는 기하학적인 문제로, 주어진 두 선분이 서로 교차하는지를 판단하는 것입니다. 여러 분야에서 활용되는 기초적인 문제이기 때문에,
알고리즘 문제 풀이 능력과 수학적 사고력을 향상시키는 데 유용합니다.

문제 설명

두 점 A(x1, y1)와 B(x2, y2)를 가지는 선분 1과 두 점 C(x3, y3)와 D(x4, y4)를 가지는 선분 2가 주어졌을 때,
두 선분이 교차하는지 여부를 판단하는 프로그램을 작성하세요.

입력

• 첫 번째 선분의 두 점 A, B의 좌표: (x1, y1), (x2, y2)
• 두 번째 선분의 두 점 C, D의 좌표: (x3, y3), (x4, y4)

출력

두 선분이 교차하면 true, 그렇지 않으면 false를 출력하세요.

문제 해결 접근 방식

이 문제를 해결하기 위해서는 선분의 위치 관계를 파악할 필요가 있습니다. 선분이 교차하기 위해서는 다음 두 가지 조건을 모두 만족해야 합니다:

1. 선분 AB의 끝점이 선분 CD의 서로 다른 방향에 위치해야 합니다.
2. 선분 CD의 끝점이 선분 AB의 서로 다른 방향에 위치해야 합니다.

수학적 배경

각 점이 주어졌을 때, 벡터의 외적을 이용하여 두 점이 서로 다른 쪽에 위치하는지를 판단할 수 있습니다.
두 벡터 v1 = B - A와 v2 = C - A의 외적의 부호가 다르다면 점 C가 선분 AB의 한쪽에,
점 D가 반대쪽에 위치한 것이 됩니다. 이와 같은 방법으로 선분의 교차 여부를 판단할 수 있습니다.

구현 방법

문제를 해결하기 위한 기본 로직은 다음과 같습니다:

1. 주어진 4개의 점 A, B, C, D를 사용하여 각 선분의 방향을 정의한다.
2. 외적 함수를 만들어 두 벡터의 외적을 계산한다.
3. 두 점의 경우에 따라 외적의 부호를 비교하고 교차 여부를 반환한다.

C# 코드 구현

using System;

class Program
{
    static void Main()
    {
        // 점 A, B, C, D의 좌표 입력
        int[] A = { 1, 1 }; // (x1, y1)
        int[] B = { 4, 4 }; // (x2, y2)
        int[] C = { 1, 4 }; // (x3, y3)
        int[] D = { 4, 1 }; // (x4, y4)

        // 교차 여부 확인
        bool isCross = DoSegmentsIntersect(A, B, C, D);
        Console.WriteLine(isCross ? "true" : "false");
    }

    static bool DoSegmentsIntersect(int[] A, int[] B, int[] C, int[] D)
    {
        // 외적을 이용한 선분 교차 확인
        int d1 = CrossProduct(A, B, C);
        int d2 = CrossProduct(A, B, D);
        int d3 = CrossProduct(C, D, A);
        int d4 = CrossProduct(C, D, B);

        // 서로 다른 방향에 위치해야 교차
        if (d1 * d2 < 0 && d3 * d4 < 0)
            return true;

        // 선분이 끝점에 겹치는 경우도 고려
        if (d1 == 0 && IsOnSegment(A, B, C)) return true;
        if (d2 == 0 && IsOnSegment(A, B, D)) return true;
        if (d3 == 0 && IsOnSegment(C, D, A)) return true;
        if (d4 == 0 && IsOnSegment(C, D, B)) return true;

        return false;
    }

    static int CrossProduct(int[] A, int[] B, int[] C)
    {
        // 벡터 외적 계산
        return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0]);
    }

    static bool IsOnSegment(int[] A, int[] B, int[] P)
    {
        // 점 P가 선분 AB 위에 있는지 확인
        return Math.Min(A[0], B[0]) <= P[0] && P[0] <= Math.Max(A[0], B[0]) &&
               Math.Min(A[1], B[1]) <= P[1] && P[1] <= Math.Max(A[1], B[1]);
    }
}

코드 설명

위의 코드를 통해 선분 교차 문제를 해결할 수 있습니다. 각 함수의 세부 설명은 다음과 같습니다.

• Main: 프로그램의 진입점으로, 각 선분의 점을 설정하고 교차 여부를 확인하는 역할을 합니다.
• DoSegmentsIntersect: 두 선분의 교차 여부를 판단하는 핵심 로직을 구현한 함수입니다.
• CrossProduct: 주어진 세 점을 이용하여 외적을 계산합니다. 외적의 결과를 통해 방향을 판단합니다.
• IsOnSegment: 특정 점이 선분 위에 위치하는지 판단하는 함수입니다.

테스트 케이스

주어진 코드를 테스트하기 위해 몇 가지 테스트 케이스를 고려할 수 있습니다.

테스트 번호	점 A	점 B	점 C	점 D	기대 결과
1	(1, 1)	(4, 4)	(1, 4)	(4, 1)	true
2	(1, 1)	(2, 2)	(2, 1)	(3, 1)	false
3	(0, 0)	(3, 3)	(0, 3)	(3, 0)	true
4	(0, 0)	(5, 5)	(1, 1)	(5, 5)	true

결론

이번 글에서는 C#을 사용하여 선분의 교차 여부를 판단하는 알고리즘을 구현해 보았습니다.
기하학적 문제는 이러한 문제 해결 방식을 이해하는 데 도움이 되며, 고급 알고리즘을 배우는 기초가 되기도 합니다.
앞으로도 다양한 알고리즘 문제를 함께 풀어보시기 바랍니다. 감사합니다!

안녕하세요! 오늘은 C# 코딩테스트를 준비하시는 여러분을 위해 ‘조약돌 꺼내기’라는 주제를 가지고 알고리즘 문제를 다뤄보겠습니다. 본 글은 다양한 구성 요소를 포함하여 신중하게 설계되었습니다. 문제에 대한 개요, 접근 방법, 구현, 예제와 해설 등을 통해 심도 깊은 이해를 도울 것입니다.

문제 설명

조약돌이 각각의 구역에 무작위로 배치되어 있는 게임을 생각해보세요. 조약돌은 엉망인 배치를 하고 있습니다. 사용자는 조약돌을 꺼내어 상자를 만들어야 하는데, 상자에 넣을 조약돌의 갯수에 대한 제약이 있습니다. 조약돌을 꺼낼 때는 항상 구역 별로 정해진 개수를 꺼내야 하며, 이 조건을 만족하는 조약돌을 꺼낼 수 있는 경우의 수를 계산하여 출력해야 합니다.

문제 정의

주어진 정수 배열 stones와 각 구역에서 꺼낼 조약돌의 개수를 정의하는 정수 배열 pick가 있습니다. 두 배열의 길이는 같으며, 각 구역의 조약돌을 꺼내는 경우의 수를 모두 계산하여 반환하는 함수 countWays(stones, pick)를 작성해야 합니다.

입력

• stones : 조약돌의 각 구역에 있는 조약돌의 개수를 나타내는 정수 배열
• pick : 각 구역에서 꺼낼 조약돌의 개수를 나타내는 정수 배열

출력

• 모든 구역의 조약돌을 꺼낼 수 있는 경우의 수를 정수로 반환합니다.

제약조건

• 1 ≤ stones.Length, pick.Length ≤ 50
• 0 ≤ stones[i] ≤ 100
• 0 ≤ pick[i] ≤ stones[i]

접근 방법

이 문제를 해결하기 위해서 우리는 조합(combination) 공식을 사용하여 각 구역에서 꺼낼 조약돌 수에 대한 조합을 계산해야 합니다. 구역이 여러 개인 경우, 각 구역의 조합 수를 곱하여 총 경우의 수를 구할 수 있습니다. 이는 수학적 개념을 토대로 하며, 각 조합의 수를 효율적으로 계산할 수 있도록 도와줍니다.

조합의 수 C(n, k)는 다음의 수식으로 정의됩니다:

C(n, k) = n! / (k! * (n - k)!)

여기서 n은 조약돌의 개수, k는 꺼내야 할 조약돌의 개수입니다. 이를 통해 각 구역의 조합을 계산한 후 모두 곱하여 최종 경우의 수를 도출합니다.

구현

이제 우리는 실제로 코드를 작성해보겠습니다. C# 언어를 사용하여 요구사항을 충족하는 함수를 구현해보도록 하겠습니다.

using System;

public class Solution {
    public int countWays(int[] stones, int[] pick) {
        int totalWays = 1;  // 모든 경우의 수를 곱할 초기값

        for (int i = 0; i < stones.Length; i++) {
            totalWays *= Combinations(stones[i], pick[i]);
        }

        return totalWays;
    }

    // 조합 계산 시 사용할 헬퍼 메서드
    private int Combinations(int n, int k) {
        if (k > n) return 0;
        if (k == 0 || k == n) return 1;

        int numerator = Factorial(n);
        int denominator = Factorial(k) * Factorial(n - k);
        return numerator / denominator;
    }
  
    // 팩토리얼 계산 메서드
    private int Factorial(int num) {
        if (num == 0) return 1;
        int result = 1;
        for (int i = 1; i <= num; i++) {
            result *= i;
        }
        return result;
    }
}

예제

우리가 작성한 코드가 제대로 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 살펴보도록 하겠습니다.

예제 1

입력:

stones = [5, 3, 8]
pick = [2, 1, 3]

출력: 840

설명: 구역 0에서 2개를 꺼내는 경우의 수: C(5, 2) = 10, 구역 1에서 1개 꺼내는 경우의 수: C(3, 1) = 3, 구역 2에서 3개 꺼내는 경우의 수: C(8, 3) = 56. 총 경우의 수 = 10 * 3 * 56 = 1680.

예제 2

입력:

stones = [2, 2, 2]
pick = [1, 1, 1]

출력: 8

설명: 각각 1개씩 꺼내는 경우의 수: C(2, 1) = 2. 세 구역 모두 2의 경우의 수를 곱하면 2 * 2 * 2 = 8.

마무리

오늘은 C# 코딩 테스트를 준비하는 여러분을 위한 ‘조약돌 꺼내기’ 문제를 풀어보았습니다. 알고리즘 문제를 해결할 때는 각 문제의 본질을 이해하고, 그에 맞는 적절한 접근 방법을 택하는 것이 중요합니다. 앞으로도 다양한 문제를 많이 풀어보며 실력을 키워나가기를 바랍니다.

코딩 테스트는 연습이 필요하며, 다양한 유형의 문제를 접해 볼수록 더 많은 경험을 쌓을 수 있습니다. 그럼 행복한 코딩 되시길 바랍니다!

안녕하세요! C# 코딩 테스팅을 준비하는 모든 분들께 인사드립니다. 오늘은 코딩 테스트에서 자주 다뤄지는 주제 중 하나, 즉 시간 복잡도에 대해 알아보고 그 개념을 적용한 알고리즘 문제를 풀어보도록 하겠습니다. 시간 복잡도는 알고리즘의 효율성을 평가하는 중요한 지표이며, 코딩 테스트에서는 특히 중요한 요소입니다.

1. 시간 복잡도란?

시간 복잡도는 입력의 크기(n)가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가를 수학적으로 표현한 것입니다. 이를 통해 알고리즘이 얼마나 효율적으로 작동하는지를 살펴볼 수 있습니다. 시간 복잡도를 분석하면 최악의 경우, 최선의 경우 및 평균의 경우를 살펴볼 수 있습니다.

2. 시간 복잡도의 표기법

시간 복잡도를 나타내는 표기법에는 여러 가지가 있지만, 가장 일반적으로 사용되는 표기법은 다음과 같습니다:

• 빅 O 표기법 (O-notation): 가장 많이 사용되는 표기법으로, 함수의 상한을 나타냅니다.
• 빅 Θ 표기법 (Θ-notation): 함수의 하한과 상한을 동시에 나타냅니다.
• 빅 Ω 표기법 (Ω-notation): 함수의 하한을 나타냅니다.

코딩 테스트에서는 주로 빅 O 표기법을 사용하여 시간 복잡도를 표현합니다.

3. 문제 설명

이제 구체적인 알고리즘 문제를 풀어보겠습니다. 문제는 다음과 같습니다:

문제: 두 수의 합

정수 배열 nums와 정수 target이 주어졌을 때, 배열에서 두 수를 찾아 그 합이 target이 되는 두 수의 인덱스를 반환하는 문제입니다. 단, 같은 요소는 두 번 사용할 수 없습니다. 결과는 인덱스를 배열로 반환해야 합니다.

예를 들어, nums = [2, 7, 11, 15]이고 target = 9일 경우, [0, 1]을 반환해야 합니다.

4. 문제 해결 과정

이 문제를 해결하기 위한 여러 가지 접근 방법이 있지만, 여기서는 가장 효율적인 두 가지 방법을 설명하겠습니다: 브루트포스 방법과 해시맵을 활용한 방법입니다.

4.1. 브루트포스 방법

브루트포스 방법은 배열의 모든 쌍을 비교하여 그 합이 target과 같은지 확인하는 방식입니다. 이 방법은 간단하지만, 시간 복잡도가 O(n^2)로 비효율적입니다. 아래는 C# 구현 예시입니다:

public int[] TwoSum(int[] nums, int target) {
    for (int i = 0; i < nums.Length; i++) {
        for (int j = i + 1; j < nums.Length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    return new int[] { -1, -1 }; // 찾지 못한 경우
}

위의 코드는 배열의 모든 쌍을 반복하며 그 합이 target과 같은지 확인합니다. 결과적으로 주어진 입력에 대해 올바른 인덱스를 반환하게 됩니다.

4.2. 해시맵을 활용한 방법

해시맵을 활용하는 방법은 시간 복잡도를 O(n)으로 줄일 수 있는 효율적인 접근 방식입니다. 이 방법은 배열을 한 번 순회하면서 각 숫자와 그 인덱스를 해시맵에 저장합니다. 그런 다음 다시 배열을 순회하면서 target - nums[i]가 해시맵에 존재하는지 확인합니다. 아래는 구현 예시입니다:

using System.Collections.Generic;

public int[] TwoSum(int[] nums, int target) {
    Dictionary numDict = new Dictionary();
    for (int i = 0; i < nums.Length; i++) {
        int complement = target - nums[i];
        if (numDict.ContainsKey(complement)) {
            return new int[] { numDict[complement], i };
        }
        numDict[nums[i]] = i; // 현재 숫자와 인덱스를 저장
    }
    return new int[] { -1, -1 }; // 찾지 못한 경우
}

위의 코드는 각 숫자를 해시맵에 저장하면서 두 수의 합이 target이 되는 경우를 찾아냅니다. 이렇게 하면 불필요한 반복을 줄이고, 알고리즘의 성능을 크게 향상시킬 수 있습니다.

5. 시간 복잡도 분석

브루트포스 방법의 경우 시간 복잡도는 O(n^2)입니다. 이는 배열의 모든 쌍을 검사하는 데 드는 시간이기 때문입니다. 반면 해시맵을 활용한 방법은 O(n)입니다. 배열을 한 번 순회하고 각 숫자를 해시맵에 추가하는데, 해시맵의 평균 조회 시간은 O(1)입니다.

이와 같이 두 방법의 시간 복잡도를 비교해보면, 해시맵을 사용하는 방법이 훨씬 효율적인 것을 알 수 있습니다. 코딩 테스트 준비 시 알고리즘의 효율성을 고려하는 것이 매우 중요합니다.

결론

이번 강좌에서는 C# 코딩 테스트에 자주 나오는 문제를 통해 시간 복잡도에 대해 알아보고, 두 가지 다른 방법으로 문제를 해결해 보았습니다. 알고리즘을 설계할 때는 효율성을 반드시 고려해야 하며, 성능이 우수한 방법을 선택하는 것이 중요합니다.

다음 강좌에서도 더 많은 알고리즘과 코딩 테스트의 기술을 다뤄보도록 하겠습니다. 여러분 모두가 멋진 취업_success를 이루시길 바랍니다!

감사합니다!

안녕하세요! 오늘은 C#을 이용한 알고리즘 문제풀이 강좌를 진행하겠습니다. 주제로는 ‘타임머신으로 빨리 가기’입니다. 해당 문제는 코딩테스트에서 자주 접할 수 있는 DFS(Depth First Search)와 BFS(Breadth First Search)의 혼합 문제로, 최단 경로를 찾는 것이 주된 목표입니다.

문제 설명

당신은 시간 여행을 할 수 있는 기능이 있는 타임머신을 가지고 있습니다. 당신의 목표는 현재 시간에서 미래의 특정 시간으로 이동하는 것입니다. 그러나 타임머신은 다음과 같은 규칙이 있습니다:

• 현재 시간이 X일 때, X – 1 초로 이동하면 1초 후로 이동합니다.
• 현재 시간이 X일 때, X + 1 초로 이동하면 1초 후로 이동합니다.
• 현재 시간이 X일 때, X * 2 초로 순간 이동할 수 있습니다.

당신은 현재 시간 0초에 있으며, N초 후에 도착해야 합니다. 타임머신을 이용하여 N초를 가장 빠르게 도달하는 방법을 계산하세요.

입력 형식

입력은 한 줄로 구성되어 있으며, 목표 시간 N이 주어집니다. (0 ≤ N ≤ 100,000)

출력 형식

가장 빠르게 도달하는 방법으로 걸리는 시간을 출력합니다.

문제 예제

    입력:
    5

    출력:
    5
    

문제 풀이 접근법

이 문제는 BFS를 통해 해결할 수 있습니다. BFS는 최단 경로를 찾는 데 매우 효과적이며, 모든 가능한 경로를 탐색하면서 최적의 해를 찾을 수 있습니다. BFS를 사용할 때는 Queue를 사용하여 현재 상태를 저장하고, 다음 상태를 큐에 추가하는 방식으로 진행합니다.

1단계: BFS 구조 이해하기

BFS는 다음과 같은 구조로 진행됩니다:

1. 현재 위치를 큐에 추가합니다.
2. 큐에서 위치를 꺼내고, 그 위치에 도달하기 위해 필요한 시간을 저장합니다.
3. 현재 위치에서 가능한 모든 이동을 계산합니다.
4. 이동한 새로운 위치가 목표 위치(N)와 같으면 종료합니다.
5. 아니면 이동한 위치를 체크하고 큐에 추가합니다.

2단계: C# 코드 구현

코드를 구현하여 BFS를 통해 이를 해결해보겠습니다:

    using System;
    using System.Collections.Generic;

    public class TimeMachine
    {
        public static void Main(string[] args)
        {
            int targetTime = int.Parse(Console.ReadLine());
            Console.WriteLine(FindMinimumTime(targetTime));
        }

        public static int FindMinimumTime(int target)
        {
            Queue queue = new Queue();
            bool[] visited = new bool[100001];
            queue.Enqueue(0); // 시작 시간
            visited[0] = true;

            int[] timeArray = new int[100001]; // 각 인덱스에 도달하는 데 걸리는 시간을 저장

            while (queue.Count > 0)
            {
                int currentTime = queue.Dequeue();

                if (currentTime == target)
                {
                    return timeArray[currentTime];
                }

                // 이동: X - 1
                if (currentTime - 1 >= 0 && !visited[currentTime - 1])
                {
                    queue.Enqueue(currentTime - 1);
                    visited[currentTime - 1] = true;
                    timeArray[currentTime - 1] = timeArray[currentTime] + 1; // 이동 시간 추가
                }

                // 이동: X + 1
                if (currentTime + 1 <= 100000 && !visited[currentTime + 1])
                {
                    queue.Enqueue(currentTime + 1);
                    visited[currentTime + 1] = true;
                    timeArray[currentTime + 1] = timeArray[currentTime] + 1; // 이동 시간 추가
                }

                // 이동: X * 2
                if (currentTime * 2 <= 100000 && !visited[currentTime * 2])
                {
                    queue.Enqueue(currentTime * 2);
                    visited[currentTime * 2] = true;
                    timeArray[currentTime * 2] = timeArray[currentTime] + 1; // 이동 시간 추가
                }
            }

            return -1; // 도달할 수 없는 경우
        }
    }
    

3단계: 코드 설명

각 부분에 대해 자세히 설명하겠습니다:

Queue와 배열

Queue는 BFS의 핵심 데이터 구조로, 현재 위치를 유지하는 데 사용됩니다. visited 배열은 이미 확인한 시간을 기록하여 무한 루프에 나가지 않도록 방지하고, timeArray는 각 시간에 도달하기 위한 최소시간을 저장합니다.

이동 로직

이동 로직은 현재 시간에서 X-1, X+1, X*2 로 각각 이동 가능한지 검사합니다. 이때 만약 이 위치가 이미 방문했다면 큐에 추가하지 않습니다.

최종 목표 확인

현재 시간과 목표 시간이 동일하다면 BFS를 종료하고, 그때까지 소요된 시간을 반환합니다. 이를 통해 우리는 최단시간에 목표 시간에 도착할 수 있습니다.

결론

이 문제는 BFS를 활용하여 그래프 탐색을 수행하는 대표적인 예제입니다. 코딩테스트에서 자주 출제되므로 이해하고 활용하는 것이 중요합니다. 구현 과정을 통해 BFS에 대한 실력을 다지셨길 바랍니다. 다음 시간에도 더 흥미로운 알고리즘 문제로 찾아뵙겠습니다!

감사합니다!