1) RPC의 종류

• 정기적이고 대역폭이 제한된 네트워크 업데이트 프로세스의 경우 Property Replication에 적용되고, 네트워크를 통해 즉시 전송하려는 우선순위가 높은 메시지의 경우 RPC를 사용하여 전송하게 된다.
• 모든 UFUNCTION은 Client, Server, Multicast 중 하나로 지정하여 RPC로 만들 수 있다.
• 서버에서 Client RPC를 호출하면 액터를 소유한 클라이언트에서 Implementation 함수가 실행된다.
• 액터를 소유한 클라이언트에서 Server RPC를 호출하면 Implementation 함수가 서버에서 실행된다.
• 서버에서 Multicast RPC를 호출하면 Implementation 함수가 서버 및 모든 클라이언트에서 실행된다.
  • Server 및 Client RPC와 달리 관련성은 Multicast RPC의 요소이다. 액터를 소유하지 않은 클라이언트는 액터에 대한 채널을 가지고 있지 않을 수도 있기 때문이다.
  • 위와 같은 경우 클라이언트는 단순히 RPC를 수신하지 않는다. 이는 지속적인 상태 변경을 클라이언트에 복제하기 위한 수단으로 Multicast RPC에 의존해서는 안 된다는 것을 의미한다.

2) Reliability (신뢰성)

• RPC는 Reliable(신뢰 가능) 또는 Unreliable(신뢰 불가능)로 설정할 수 있다.
  • 대역폭이 포화된 경우 Unreliable RPC가 삭제될 수 있다. 이 경우 도착이 보장되지 않으므로 순서대로 도착한다는 보장도 없다.
  • Reliable RPC는 도착하는 것이 보장되며, 단일 액터 내에서는 신뢰할 수 있는 RPC가 호출된 순서대로 도착하는 것이 보장된다.
• 함수 호출이 게임 플레이에 중요한 경우 이러한 안전성이 필요하지만, 과도하게 사용하면 대역폭 포화가 악화되고 패킷 손실 시 병목 현상이 발생할 수 있다.

3) Implementation

• C++에서는 함수의 실제 본문을 _Implementation 접미사로 정의해야 한다.
  • 이는 실제로 원격 프로세스에서 실행되는 함수인 반면, 로컬에서 호출하는 함수는 네트워크를 통해 적절한 메시지를 보내는 자동 생성된 Thunk이다.

4) WithValidation

• Server RPC는 WithValidation으로 선언될 수도 있다. 이 경우 기존 함수와 동일한 인수를 사용하고, 해당 값을 신뢰할 수 있는지 여부를 나타내는 부울 값을 반환하는 "_Validate" 함수를 구현해야 한다.
  • 이는 치트와 같이 서버가 게임 플레이에 영향을 미치는 방식으로 클라이언트에서 전송된 데이터를 사용하는 경우를 감지하기 위한 수단이다. 서버 RPC가 유효성 검사에 실패하면 해당 RPC를 보낸 클라이언트가 게임에서 추방된다.
• 따라서 RPC는 즉시 전송되고 신뢰할 수 있으므로, Property Replication이 제한될 수 있는 특정 경우에 유용하다.

Property Replication in Detail

• RPC는 "즉각적", Property Replication은 "결국"이 핵심 단어이다.
• 서버에서 복제된 속성을 변경하면 모든 클라이언트가 결국 서버와 동기화 될 것을 기대할 수 있다. 플레이어가 너무 멀리 떨어져 액터와의 관련성이 사라질 때, 서버에서 액터가 변경되면 변경 사항은 계속 유지 된다. 결국 액터가 다시 해당 클라이언트와 관련되면 업데이트된 속성 값을 받게 된다.
  • Property Replication은 어떤 경우에도 업데이트 빈도 및 대역폭 제한을 준수한다. 서버의 단일 프레임마다 복제된 속성을 변경할 수 있으며, 클라이언트는 업데이트 될 때마다 가장 최근 값을 가져온다. 즉, 서버는 모든 중간 지점의 값들을 하나씩 보내지 않아도 된다. (여기서는 업데이트 되는 값을 보간 해주었음.) (동영상 링크) 13:30 ~ 14:05
• Property Replication을 활성화하려면 해당 속성의 UPROPERTY에 Replicated 지정자를 추가하면 된다.
  • C++에서는 액터의 .cpp 파일에 GetLifetimeReplicatedProps() 함수를 정의해야 한다. (UnrealNetwork.h도 포함시키는 것이 좋다.) 이 함수에서는 복제해야 하는 속성과 조건을 지정한다. 가장 간단한 경우에는 속성이 항상 모든 클라이언트에 복제되며, 이 때는 DOREPLIFETIME 매크로에서 속성의 이름을 지정하여 이를 수행한다.
  • 그러나 복제 조건을 지정할 수도 있는데, 아래와 같은 경우가 있다. (이외에도 존재)
    • 1) 소유 클라이언트에 속성을 복제하기만 하면 되는 경우
      • 2) 업데이트를 받기 위해 비소유 클라이언트만 필요한 경우
      • 3) 생성 시 초기화되지만 런타임 시 변경되지 않는 경우
• 복제된 속성이 업데이트 될 때 일부 코드를 실행해야 하는 경우 RepNotify 함수를 선언하고 ReplicatedUsing 지정자를 사용할 수 있다. 복제 업데이트로 인해 값이 변경될 때마다 지정된 알림 함수가 클라이언트에서 호출된다.
  • 블루프린트에서 서버의 속성 값을 변경하면 서버에서 연관된 RepNotify 함수가 자동으로 호출된다는 점에 유의해야 한다. (C++에서는 아님.)
  • RepNotify 로직을 클라이언트뿐만 아니라 서버에서도 실행하려면 속성 값을 업데이트 한 후 RepNotify 함수를 수동으로 호출해야 한다.

Authority & Role

• 액터가 가질 수 있는 역할은 여러 가지가 존재하지만, 액터에 대한 권한이 나에게 있는지만 고려하면 된다.
  • Authority를 가지고 있는 것은 항상 서버이며, 클라이언트는 그저 업데이트를 받아 업데이트 사이에 액터에 시뮬레이션을 적용할 뿐이다.
• 액터 클래스에서 일부 코드를 실행할 때마다 권한을 확인할 수 있다.
  • 권한 O : 싱글 플레이 모드에서 실행되거나, 코드가 서버에 의해 실행되고 있거나, 액터가 클라이언트에만 존재하는 경우
  • 권한 X : 클라이언트에서 실행되고, 이 액터는 서버에서 복제된 경우
• PlayerController가 소유 클라이언트에 복제되는 것은 AutonomousProxy이고, 연관된 Pawn 또한 해당 클라이언트에 대한 AutonomousProxy이다. 다른 모든 클라이언트의 경우 Pawn은 SimulatedProxy로 복제된다.
  • AutonomousProxy는 클라이언트가 완전한 권한을 가지지는 못하더라도, 액터의 움직임과 행동을 직접적으로 제어한다는 것을 의미한다. (액터가 소유 클라이언트의 플레이어 컨트롤러에 의해 움직이는 경우)
• SimulatedProxy는 마지막으로 전송된 속도에 따라 시뮬레이션하고, AutonomousProxy는 플레이어 컨트롤러에 의해 입력된 정보에 따라 시뮬레이션한다.

👁️‍🗨️ 출처

• https://www.youtube.com/watch?v=JOJP0CvpB8w&t=182s
• https://docs.unrealengine.com/4.27/ko/InteractiveExperiences/Networking/Actors/

• 언리얼 엔진에는 멀티 플레이어 게임을 위한 네트워킹 시스템이 제공된다.
• 멀티 플레이어 게임은 동일한 게임의 여러 인스턴스가 동시에 실행되는 것을 목표로 한다.
• 즉, 아래의 예시들이 여러 인스턴스에 해당된다.
  • 1) 동일한 시스템의 다른 프로세스
  • 2) 동일한 로컬 네트워크의 다른 컴퓨터
  • 3) 인터넷을 통해 서로 다른 위치에 존재하는 플레이어
• 이처럼 다양한 게임 인스턴스는 서로 소통함으로써 공유하는 세계를 일관되게 구축해야 한다.

• 언리얼 엔진의 네트워크 모델에서 플레이어(Client)는 서버에 연결 상태를 유지하고, 서버는 월드를 신뢰할 수 있는 상태(Reliable)로 유지한다.
• 서버에서 변경 사항이 발생하면 해당 변경 사항은 리플리케이션(Replication)이라는 프로세스의 일부로 필요에 따라 클라이언트로 전파된다.
  • 리플리케이션 시스템은 게임 코드와 통합되어 멀티 플레이어 게임을 쉽게 개발하도록 해준다.
  • 통신을 위해 소켓을 따로 열거나 패킷을 보내지 않아도 되며, 데이터 직렬화(Serealization) / 인코딩(Encoding) / 바이트 순서 / 타임스탬프 / 재정렬 및 라우팅(Routing) 등을 처리하지 않고, 단순히 해당 프로퍼티를 복제하기를 요구하면 복제되는 시스템이다.

Net Mode

• World의 속성으로 네 가지의 모드(Standalone / DedicatedServer / ListenServer / Client)가 존재하며, 아래의 3가지 질문을 통해 모드를 나눌 수 있다.

1. Playable?

• 게임을 플레이 할 수 있는가?
• GameInstance에 LocalPlayer가 존재하고, 해당 플레이어의 입력을 처리하고, 월드를 뷰포트로 렌더링하고 있는가?

  2. Authority?

• 우리는 서버인가?
• GameInstance에 GameMode 액터가 포함된 World의 정식 사본이 있는가?

  3. Open To Clients?

• (우리가 서버라면) 원격 연결 시도를 위해 열려있는가?
• 다른 플레이어가 클라이언트로 참여해 게임을 플레이 할 수 있는가?

• 게임을 시작하면 프로세스의 수명동안 유지되는 GameInstance 개체를 얻은 다음, 게임에서 URL(서버 주소 또는 맵 이름)을 탐색한다.
• 이후 게임이 맵을 로드하게 되고, 맵은 World를 제공하며, 이 World의 Net Mode는 GameInstance가 시작된 방식에 따라 달라진다.

4가지 Net Mode의 차이점

1. Standalone

• 게임 인스턴스가 로컬로 맵을 로드한 경우, World의 Net Mode는 Standalone이 된다.
• 단일 게임 인스턴스는 서버이자 클라이언트이지만, 단일 플레이어 구성에서 실행되기 때문에 다른 클라이언트가 연결할 수 없다.

2. Dedicated Server

• 로컬 플레이어와 뷰포트가 없는 게임 인스턴스
• 사운드, 그래픽, 사용자 입력 등 플레이어 관련 기능을 제거하여 효율적인 실행 가능한 서버
• 플레이어가 클라이언트로 연결할 수 있는 서버 전용 콘솔 응용 프로그램으로서 작동한다.

3. Listen Server

• 맵을 로컬로 로드하지만 Listen 옵션을 추가하면 Listen Server로 실행된다.
• 기본적으로 Standalone과 동일하지만 게임의 다른 인스턴스들이 클라이언트로 연결할 수 있다.

4. Client

• 게임 인스턴스가 원격 서버로 연결된 경우, 해당 World는 Client 모드를 갖는다.
• 이 때 게임은 로컬 플레이어가 플레이 할 수 있지만, 서버 요청에 따라 World가 업데이트 된다.
• 서버가 아닌 유일한 모드로, 서버 측의 로직이 실행되지 않는다.

언리얼 엔진의 네트워킹 시나리오

1. Single Player

• 하나의 게임 인스턴스가 있고, 해당 World는 Standalone 모드에서 실행된다.

2. Multi Player

• 각각 고유한 게임 인스턴스들이 있고, 고유한 World 복사본이 있는 여러 프로세스가 있다.
• 이러한 프로세스 중 하나는 Listen Server 또는 Dedicated Server가 된다.

Replication 시스템 개요

• 멀티 플레이어 게임이 실행되면 언리얼 엔진의 Replication 시스템이 동작하여 게임의 다양한 인스턴스가 모두 동기화되도록 한다.
• 각 인스턴스는 공유되는 World에 대해 자체적으로 복사본을 만들고, Replication 시스템은 이것이 정확하게 동작하는지 확인한다.
• 이러한 역할 수행을 위해 Replication 시스템은 NetDriver, NetConnection, Channel 라는 클래스들에 의존한다.

• 서버를 부팅하면 NetDriver가 생성되고, 원격 프로세스로부터의 메시지 수신이 시작된다.
• 클라이언트를 부팅하면 자체 NetDriver가 생성되어 서버에 연결 요청을 보낸다.
• 서버와 클라이언트의 NetDriver가 연결되면 각 NetDriver 내에서 NetConnection이 설정된다.
  • 서버에는 연결된 각 원격 플레이어에 대해 하나의 NetConnection이 존재한다.
  • 각 클라이언트에는 서버에 대한 연결을 나타내는 단일 NetConnection이 존재한다.

• 모든 NetConnection에는 다양한 채널이 존재한다.
• 일반적으로 NetConnection에는 ControlChannel, VoiceChannel이 있고, 각 NetConnection에는 현재 해당 NetConnection을 통해 복제되고 있는 각 액터들에 대한 ActorChannel들이 있다.
  • 이를 통해 Replicate는 Actor 수준에서 발생한다는 것을 알 수 있다.

• 네트워크를 통해 동기화를 유지하기 위해 액터가 필요한 경우, 해당 액터를 Replication 가능하도록 설정한다.
• Replicate 가능한 액터가 특정 플레이어와 관련된 것이면 서버는 해당 플레이어의 NetConnection에서 ActorChannel을 만들고, 서버와 클라이언트는 해당 채널을 사용하여 해당 액터에 대한 정보를 교환한다.

Actor Replication

• 액터가 Replicate 될 때, 세 가지의 결과가 발생한다.

1) LifeTime

• 액터의 수명이 서버와 클라이언트 간에 동기화되어 유지된다.
• 서버가 Replicate 설정된 액터를 생성하면 클라이언트에 알림이 전달되어 자체적인 복사본을 생성한다.
• 액터가 서버에서 소멸되면 클라이언트에서도 자동으로 소멸된다.

2) Property Replication

• 액터에 Replicate 플래그가 지정된 속성이 있는 경우, 해당 속성이 서버에서 변경되면 새 값이 클라이언트에 전달된다.

3) RPCs(Remote Procedure Call)

• RPC에는 3가지 종류가 있다.
  • Client : 서버에서 호출되지만 클라이언트에서 실행되는 RPC
    • 해당 액터를 실제 소유하고 있는 클라이언트에서만 함수 실행
  • Server : 클라이언트에서 호출되지만 서버에서 실행되는 RPC
    • 클라이언트는 RPC가 호출되는 액터를 소유해야 한다.
  • Multicast : 서버에서 호출된 후 서버를 포함하여 연결된 모든 클라이언트에서 실행되는 RPC
    • 클라이언트에서 호출될 경우, 로컬에서만 실행되고 서버에서는 실행 X
• RPC를 사용하여 서버와 클라이언트 간에 메시지를 주고 받을 수 있다.
• 실행될 때만 Replicate 된다.

Ownership (소유권)

• 모든 액터는 소유자로 지정된 다른 액터를 가질 수 있다.

• 일반적으로 액터 생성 시 소유자를 설정하지만, 런타임에 SetOwner를 호출할 수도 있다.

  

• NetConnection은 플레이어를 나타내며, 플레이어가 게임에 로그인되면 이와 연결된 PlayerController 액터를 소유한다. 이 경우 NetConnection은 다시 PlayerController로 추적할 수 있는 모든 액터를 소유한다.

• 아래와 같은 경우, Weapon 액터로부터 시작해 PlayerController에 대한 소유자 참조 체인을 따라가면서 해당 Weapon 액터가 특정 클라이언트 연결에 속해 있는지 알 수 있다.

Enabling Actor Replication

• 액터가 Replicate 되려면 bReplicates 플래그가 활성화 되어야 한다.
• 런타임에 Replicate를 켜거나 끌 수도 있다.
• 서버는 해당 액터를 해당 클라이언트에 Replicate 하기 위해 지정된 NetConnection 내에서 ActorChannel을 열 수 있다.

Relevancy (관련성)

• 액터의 관련성에 따라 어떤 연결이 언제 발생할지 결정된다.
• 액터가 Replicate 가능할 때, 서버의 NetDriver는 각 클라이언트 연결에 대해 해당 액터를 확인해 해당 액터가 해당 클라이언트와 관련 있는지 확인한다.
• 일부 액터는 Replicate가 가능한 한, 서버가 이를 항상 모든 클라이언트에 복제한다. (bAlwaysRelevant = true)
  • 예를 들면, GameState 및 PlayerState는 항상 모든 클라이언트와 관련이 있다.
• 소유권은 관련성에 있어 중요한 역할을 한다. 특정 플레이어가 소유하거나 특정 행동을 지시하는 액터는 항상 해당 클라이언트와 관련된 것으로 간주한다. 일부 액터(ex. PlayerController)는 소유자에게만 관련되도록 구성되어 있으므로 소유하지 않은 클라이언트에는 복제되지 않는다.
• 소유자로부터 관련성을 상속하도록 액터를 구성할 수도 있다.
• 위와 같은 특수 플래그 중 어느 것도 설정되지 않고, 어떤 클라이언트도 액터를 소유하지 않은 경우도 있다.
  • 해당 경우에는 액터가 숨겨져 있고, 충돌이 비활성화 되어있으면 관련성이 없는 것으로 간주된다.
  • 그렇지 않은 경우 관련성은 클라이언트 연결에 해당하는 플레이어와의 거리를 기반으로 한다. 액터에서 플레이어까지의 제곱 거리가 NetCullDistanceSquared보다 작으면 액터는 해당 플레이어와 관련이 있다.

Update Frequency & Priority (업데이트 빈도 및 우선순위)

• 액터가 Replicate 되면 업데이트 빈도 및 우선순위에 따라 서버가 해당 액터와 관련된 클라이언트에 업데이트를 보내는 빈도가 결정된다.
• NetUpdateFrequency를 설정할 경우, 액터를 확인하여 변경사항이 있을 경우 잠재적으로 클라이언트에 새 데이터를 보내는 초당 횟수가 결정된다.
• 서버의 NetDriver는 대역폭 포화를 완화하기 위해 몇 가지 간단한 로드 밸런싱을 사용한다. NetDriver가 작업할 수 있는 대역폭은 한정되어 있으므로, 우선순위에 따라 관련 액터를 정렬한 뒤, 사용 가능한 대역폭을 모두 사용할 때까지 네트워크 업데이트를 실행한다.
  • 플레이어에 더 가까운 액터는 더 높은 우선순위로 가중치가 부여되고, 한동안 업데이트 되지 않은 액터에도 더 높은 우선순위가 부여되므로 모든 액터는 결국 언젠가는 우선순위에 따라 작업된다.
• 액터의 NetPriority 속성을 설정하면 추가적인 가중치를 부여할 수 있다.
  • 예를 들면, NetPriority를 5.0으로 설정할 경우 그렇지 않은 경우보다 5배 더 자주 업데이트 되어야 한다고 지시하는 것이다.
    

👁️‍🗨️ 출처

• https://www.youtube.com/watch?v=JOJP0CvpB8w&t=182s
• https://docs.unrealengine.com/5.2/ko/networking-overview-for-unreal-engine/
• https://docs.unrealengine.com/4.27/ko/InteractiveExperiences/Networking/Actors/

https://www.acmicpc.net/problem/18436

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 내의 짝수 개수와 홀수 개수를 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, pair(짝수 개수, 홀수 개수) 트리를 저장할 tree 배열을 선언한다. 이 때 트리의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n을 입력받아 저장하고, n개의 수를 입력받아 datas에 저장한다. 이후 쿼리의 개수 m을 입력 받아 저장한다.

3) init() 함수를 통해 pair(짝수 개수, 홀수 개수) 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간곱을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
  • 현재 순서 노드의 값 = pair(왼쪽 자식 노드의 짝수 개수 + 오른쪽 자식 노드의 짝수 개수, 왼쪽 자식 노드의 홀수 개수 + 오른쪽 자식 노드의 홀수 개수)
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때)
  • 해당 수가 짝수라면 pair(1, 0)를 현재 노드의 값으로 초기화
    • 해당 수가 홀수라면 pari(0, 1)를 현재 노드의 값으로 초기화

4) m번의 쿼리를 실행한다.

• 쿼리로 주어지는 수 a, b, c를 입력 받는다.
• a가 1이라면 update()를 실행하고, b번째 수를 c로 변경한다.
  • update()는 하위 노드 값부터 상위 노드로 바뀌는 방식으로 진행한다.
  • 범위 밖에 있는 경우 무시한다.
  • 범위 안에 있다면
    • 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때)
      • 변경할 수가 짝수라면 현재 순서 노드를 pair(1, 0)으로 변경한다.
      • 변경할 수가 홀수라면 현재 순서 노드를 pair(0, 1)으로 변경한다.
    • 분할할 수 있다면 데이터 범위를 반으로 분할해 현재 순서 노드의 값 = pair(왼쪽 자식 노드의 짝수 개수 + 오른쪽 자식 노드의 짝수 개수, 왼쪽 자식 노드의 홀수 개수 + 오른쪽 자식 노드의 홀수 개수)로 변경한다.
    • update() 함수 실행 이후 datas의 특정 인덱스 값도 변경해주어야 한다.
• a가 2라면 b, c 범위 내 짝수 개수를 출력한다.
• a가 3이라면 b, c 범위 내 홀수 개수를 출력한다.
  • get() 함수를 통해 현재 순서에서 구해야하는 범위의 짝수 개수 및 홀수 개수를 구한다.
    • 범위 밖에 있는 경우 pair(0, 0)을 반환한다.
    • 범위 안에 있는 경우 현재 순서 노드의 값을 반환한다.
    • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 get()을 실행한다.
  • 짝수 개수는 get().first를, 홀수 개수는 second를 출력하면 된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<long long, int> pii;    // 짝수, 홀수 개수

pii tree[400004];
int datas[100001];
int n, m;

pii init(int start, int end, int node)
{
    if (start == end)
    {
        if (datas[start] % 2 == 0)
            return tree[node] = pii(1, 0);
        else
            return tree[node] = pii(0, 1);
    }
    int mid = start + (end - start) / 2;
    pii leftNode = init(start, mid, node * 2);
    pii rightNode = init(mid + 1, end, node * 2 + 1);
    return tree[node] = pii(leftNode.first + rightNode.first,
        leftNode.second + rightNode.second);
}

pii get(int start, int end, int node, int left, int right)
{
    if (end < left || right < start) return pii(0, 0);
    if (left <= start && end <= right)
        return tree[node];
    int mid = start + (end - start) / 2;
    pii leftNode = get(start, mid, node * 2, left, right);
    pii rightNode = get(mid + 1, end, node * 2 + 1, left, right);
    return pii(leftNode.first + rightNode.first, leftNode.second + rightNode.second);
}

pii update(int start, int end, int node, int index, int dif)
{
    if (index < start || end < index) return tree[node];
    if (start == end)
    {
        if (dif % 2 == 0)
            return tree[node] = pii(1, 0);
        else
            return tree[node] = pii(0, 1);
    }
    int mid = start + (end - start) / 2;
    pii leftNode = update(start, mid, node * 2, index, dif);
    pii rightNode = update(mid + 1, end, node * 2 + 1, index, dif);
    return tree[node] = pii(leftNode.first + rightNode.first, leftNode.second + rightNode.second);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> datas[i];
    init(1, n, 1);
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            update(1, n, 1, b, c);
            datas[b] = c;
        }
        else if (a == 2)
            cout << get(1, n, 1, b, c).first << '\n';
        else
            cout << get(1, n, 1, b, c).second << '\n';
    }
}

https://www.acmicpc.net/problem/2357

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 내의 최솟값과 최댓값을 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, 최솟값 트리를 저장할 minTree 배열, 최댓값 트리를 저장할 maxTree 배열을 선언한다. 이 때 트리들의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n과 최솟값 및 최댓값을 구해야하는 범위의 개수 m을 입력 받아 저장하고, n개의 수를 입력받아 datas에 저장한다.

3) minInit(), maxInit() 함수를 통해 최솟값 트리와 최댓값 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간곱을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
• 최솟값 트리의 경우
  • 현재 순서 노드의 값 = 왼쪽 자식 노드의 값과 오른쪽 자식 노드의 값 중 더 작은 값
• 최댓값 트리의 경우
  • 현재 순서 노드의 값 = 왼쪽 자식 노드의 값과 오른쪽 자식 노드의 값 중 더 큰 값
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때) 해당 수를 현재 순서 노드의 값으로 설정하고 반환한다.

4) m번의 최솟값 및 최댓값 출력을 실행한다.

• 항상 a < b임이 보장되지 않기 때문에 a < b일 때와 아닐 때의 조건을 나눈다.
• findMin()과 findMax() 함수를 통해 현재 순서에서 구해야하는 범위의 최솟값 및 최댓값을 구한다.
• 최솟값 트리의 경우
  • 범위 밖에 있는 경우 INF(수열의 수로 올 수 없는 큰 값)을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 최솟값을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 findMin()을 실행한다.
• 최댓값 트리의 경우
  • 범위 밖에 있는 경우 0을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 최댓값을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 findMax()을 실행한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
long long minTree[400004];
long long maxTree[400004];
long long datas[100001];
const long long INF = 1000000001;

long long minInit(int start, int end, int node)
{
    if (start == end) return minTree[node] = datas[start];
    int mid = start + (end - start) / 2;
    return minTree[node] = min(minInit(start, mid, node * 2), minInit(mid + 1, end, node * 2 + 1));
}

long long findMin(int start, int end, int node, int left, int right)
{
    if (end < left || right < start) return INF;
    if (left <= start && end <= right) return minTree[node];
    int mid = start + (end - start) / 2;
    return min(findMin(start, mid, node * 2, left, right), 
        findMin(mid + 1, end, node * 2 + 1, left, right));
}

long long maxInit(int start, int end, int node)
{
    if (start == end) return maxTree[node] = datas[start];
    int mid = start + (end - start) / 2;
    return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1));
}

long long findMax(int start, int end, int node, int left, int right)
{
    if (end < left || right < start) return 0;
    if (left <= start && end <= right) return maxTree[node];
    int mid = start + (end - start) / 2;
    return max(findMax(start, mid, node * 2, left, right),
        findMax(mid + 1, end, node * 2 + 1, left, right));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> datas[i];

    minInit(1, n, 1);
    maxInit(1, n, 1);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        if (a < b)
        {
            cout << findMin(1, n, 1, a, b) << ' ';
            cout << findMax(1, n, 1, a, b) << '\n';
        }
        else
        {
            cout << findMin(1, n, 1, b, a) << ' ';
            cout << findMax(1, n, 1, b, a) << '\n';
        }    
    }
}

https://www.acmicpc.net/problem/11505

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 곱을 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, 구간합 트리를 저장할 tree 배열을 선언한다. 이 때 구간합 트리의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n과 수의 변경이 일어나는 횟수 m, 구간 곱을 구하는 횟수 k 를 입력 받아 저장하고, n개의 수를 입력받아 datas에 저장한다.

3) init() 함수를 통해 구간합 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간곱을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
• 현재 순서 노드의 값 = 왼쪽 자식 노드의 값 * 오른쪽 자식 노드의 값
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때) 해당 수를 현재 순서 노드의 값으로 설정하고 반환한다.

4) m + k 만큼의 (곱 구하기, 수 바꾸기)를 실행한다.

• mul() 함수를 통해 현재 순서에서 구해야하는 범위의 구간합을 구하고 이를 출력한다.
  • 범위 밖에 있는 경우 1을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 구간곱을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 mul()을 실행한다.
• update() 함수를 통해 특정 인덱스의 수를 다른 수로 변경한다.
  • 구간합과 달리 특정 노드의 값이 0으로 바뀌거나, 0에서 다른 값으로 바뀔 때 상위 노드부터 계산해 값을 수정할 수 없다. 따라서 init()과 같이 하위 노드 값부터 상위 노드로 바뀌는 방식으로 진행한다.
    • 범위 밖에 있는 경우 무시한다.
    • 범위 안에 있다면
  • 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때)는 바뀔 수(dif)를 현재 순서 노드의 값으로 설정하고 반환한다.
  • 분할할 수 있다면 데이터 범위를 반으로 분할해 각 범위에 대해 update()를 실행한다.
    • update() 함수 실행 이후 datas의 특정 인덱스 값도 변경해주어야 한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k;
long long tree[4000004];
long long datas[1000001];
const long long MOD = 1000000007;

// 구간곱 트리 초기화
long long init(int start, int end, int node)
{
    if (start == end) return tree[node] = datas[start];
    int mid = start + (end - start) / 2;
    return tree[node] = (init(start, mid, node * 2) * init(mid + 1, end, node * 2 + 1)) % MOD;
}

// 구간곱 구하기
long long mul(int start, int end, int node, int left, int right)
{
    if (end < left || right < start) return 1;
    if (left <= start && end <= right) return tree[node];
    int mid = start + (end - start) / 2;
    return (mul(start, mid, node * 2, left, right)
        * mul(mid + 1, end, node * 2 + 1, left, right)) % MOD;
}

// 특정 수 변경
long long update(int start, int end, int node, int index, long long dif)
{
    if (index < start || end < index) return tree[node];
    if (start == end) return tree[node] = dif;    // index가 현재 구간에 들어오고, 구간 내에 수가 하나 뿐이다 -> 해당 수가 바꾸고자 하는 수이므로 해당 노드 값 변경 
    int mid = start + (end - start) / 2;
    return tree[node] = (update(start, mid, node * 2, index, dif) * update(mid + 1, end, node * 2 + 1, index, dif)) % MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> datas[i];

    init(1, n, 1);
    for (int i = 0; i < m + k; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            update(1, n, 1, b, c);
            datas[b] = c;
        }
        else
            cout << mul(1, n, 1, b, c) << '\n';
    }
}

https://www.acmicpc.net/problem/1238

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 마을 개수 n과 도로의 개수 m, 파티가 열리는 마을 x 를 입력 받아 저장한다. => 이 때 n은 노드 개수, m은 간선 개수, x는 시작 지점이자 도착 지점으로 볼 수 있다.

2) (다른 도시들에서 x 도시까지 가는 거리 + x 도시에서 다른 도시들로 가는 거리)를 저장하기 위해 result 배열을 선언한다.

3) 1 ~ n 도시에서 x 도시까지의 거리를 각각 구하기 위해 1 ~ n을 시작점으로하는 다익스트라 알고리즘을 각각 실행한다. (다익스트라 알고리즘 과정은 생략)

• 각 알고리즘을 실행하고 나면 dp[x]에 (현재 순서(i) 도시 ~ x 도시까지의 최단 거리)가 저장이 되므로, 이를 result[i]에 누적한다.
• 다익스트라 알고리즘 실행 전에 매번 dp 배열을 INF로 초기화해준다.

4) x 도시에서 1 ~ n 도시까지의 거리를 구하기 위해 x를 시작점으로 하는 다익스트라 알고리즘을 1회 실행한다.

• 알고리즘을 실행하고나면 dp[1 ~ n]에 각각 (x 도시에서 1 ~ n도시까지의 최단 거리)가 저장이되므로, 이를 result[1 ~ n]에 누적한다.
• 다익스트라 알고리즘 실행 전에 dp 배열을 INF로 초기화해준다.

5) 오고 가는 데에 시간이 가장 오래 걸리는 경우를 구해야하므로, result 배열에 들어있는 모든 값들을 탐색해 그 중 가장 큰 값을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> graph;
int dp[1001];
int result[1001];
int n, m, x;
const long long INF = 1e9;

void dijkstra(int start)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, start));
    dp[start] = 0;
    while (!pq.empty())
    {
        int dist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dp[cur] < dist)    continue;
        for (int i = 0; i < graph[cur].size(); i++)
        {
            pii curEdge = graph[cur][i];
            int cost = dist + curEdge.first;
            if (cost < dp[curEdge.second])
            {
                dp[curEdge.second] = cost;
                pq.push(pii(cost, curEdge.second));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m >> x;
    graph.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(pii(c, b));
    }

    // 1 ~ n 도시부터 x 도시까지의 거리 구하기
    for (int i = 1; i <= n; i++)
    {
        fill(dp, dp + n + 1, INF);
        dijkstra(i);
        result[i] += dp[x];
    }

    // x 도시부터 1 ~ n 도시까지의 거리 구하기
    fill(dp, dp + n + 1, INF);
    dijkstra(x);
    for (int i = 1; i <= n; i++)
        result[i] += dp[i];

    int maxTime = 0;
    for (int i = 1; i <= n; i++)
    {
        if (maxTime < result[i])
            maxTime = result[i];
    }
    cout << maxTime;
}

✍️ 더 효율적인 풀이

• 위 코드의 경우 다익스트라 알고리즘이 n + 1회 실행된다. (다른 도시에서 x 도시까지의 최단 거리 구하기 위해 n회 + x 도시에서 다른 도시까지의 거리 구하기 위해 1회)

• 하지만 다른 도시에서 x 도시까지의 최단 거리를 구하는 데에 다익스트라 알고리즘을 1회만 실행할 수 있는 방법이 있다.

  • 모든 노드에서 특정 노드까지의 최단 거리
  • 기존 그래프의 역그래프에서 특정 노드에서 다른 모든 노드까지의 최단 거리

• 위 두 경우는 같은 결과값을 가지게 된다. 첫 번째 경우는 모든 노드를 시작점으로 다익스트라 알고리즘을 n회 실행해야하지만, 두 번째 경우는 특정 노드를 시작점으로 다익스트라 알고리즘을 1회만 실행하면 되므로 시간적으로 더 효율적이다.

• 따라서 (기존 그래프에서 x를 시작점으로 하는 다른 모든 노드까지의 최단 거리) + (역 그래프에서 x를 시작점으로 하는 다른 모든 노드까지의 최단 거리)를 구하면 각 노드에서 x까지 갔다가 되돌아오는 거리를 구할 수 있다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> graph;
vector<vector<pii>> reverse_graph;
int dp[1001];
int result[1001];
int n, m, x;
const long long INF = 1e9;

void dijkstra(int start, bool reverse)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, start));
    dp[start] = 0;
    while (!pq.empty())
    {
        int dist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dp[cur] < dist)    continue;
        if (!reverse)
        {
            for (int i = 0; i < graph[cur].size(); i++)
            {
                pii curEdge = graph[cur][i];
                int cost = dist + curEdge.first;
                if (cost < dp[curEdge.second])
                {
                    dp[curEdge.second] = cost;
                    pq.push(pii(cost, curEdge.second));
                }
            }
        }
        else
        {
            for (int i = 0; i < reverse_graph[cur].size(); i++)
            {
                pii curEdge = reverse_graph[cur][i];
                int cost = dist + curEdge.first;
                if (cost < dp[curEdge.second])
                {
                    dp[curEdge.second] = cost;
                    pq.push(pii(cost, curEdge.second));
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m >> x;
    graph.resize(n + 1);
    reverse_graph.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(pii(c, b));
        reverse_graph[b].push_back(pii(c, a));
    }

    // 1 ~ n 도시부터 x 도시까지의 거리 구하기
    fill(dp, dp + n + 1, INF);
    dijkstra(x, true);
    for (int i = 1; i <= n; i++)
        result[i] += dp[i];

    // x 도시부터 1 ~ n 도시까지의 거리 구하기
    fill(dp, dp + n + 1, INF);
    dijkstra(x, false);
    for (int i = 1; i <= n; i++)
        result[i] += dp[i];

    int maxTime = 0;
    for (int i = 1; i <= n; i++)
    {
        if (maxTime < result[i])
            maxTime = result[i];
    }
    cout << maxTime;
}

https://www.acmicpc.net/problem/1275

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 합을 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, 구간합 트리를 저장할 tree 배열을 선언한다. 이 때 구간합 트리의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n과 턴의 개수 q를 입력 받아 저장하고, n개의 수를 입력받아 datas에 저장한다.

3) init() 함수를 통해 구간합 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간합을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
• 현재 순서 노드의 값 = 왼쪽 자식 노드의 값 + 오른쪽 자식 노드의 값
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때) 해당 수를 현재 순서 노드의 값으로 설정하고 반환한다.

4) q 만큼의 (합 구하기, 수 바꾸기)를 실행한다.

• sum() 함수를 통해 현재 순서에서 구해야하는 범위의 구간합을 구하고 이를 출력한다.
  • 범위 밖에 있는 경우 0을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 구간합을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 합을 구한다.
  • 이 때 반드시 x < y 인 것은 아니므로, x < y일 때와 x > y일 때 매개변수를 다르게 입력한다.
• update() 함수를 통해 특정 인덱스의 수를 다른 수로 변경한다.
  • 범위 밖에 있는 경우 무시한다.
  • 범위 안에 있으면 현재 순서 노드에 변경 값을 더해주고, 하위 노드로 내려가며 범위 내에 있는 다른 원소도 갱신한다.
  • update() 함수 실행 이후 datas의 특정 인덱스 값도 변경해주어야 한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long tree[400004];
long long datas[100001];
int n, q;

long long init(int start, int end, int node)
{
    if (start == end) return tree[node] = datas[start];
    int mid = (start + end) / 2;
    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

long long sum(int start, int end, int node, int left, int right)
{
    if (left > end || right < start)
        return 0;
    if (left <= start && end <= right)
        return tree[node];
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right)
        + sum(mid + 1 ,end, node * 2 + 1, left, right);
}

void update(int start, int end, int node, int index, long long dif)
{
    if (index < start || index > end) return;
    tree[node] += dif;
    if (start == end) return;
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index, dif);
    update(mid + 1, end, node * 2 + 1, index, dif);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> datas[i];

    init(1, n, 1);
    for (int i = 0; i < q; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a < b)
            cout << sum(1, n, 1, a, b) << '\n';
        else
            cout << sum(1, n, 1, b, a) << '\n';
        long long calcNum = d - datas[c];
        update(1, n, 1, c, calcNum);
        datas[c] = d;
    }
}

: 여러 개의 데이터가 연속적으로 존재할 때 특정 범위 데이터의 합을 빠르고 간단하게 구할 수 있는 자료구조

2. 배열에서 특정 구간 합 구하기

1) 단순 배열을 이용해 선형적으로 구하기 : 범위 내 값을 하나씩 더해가면서 구할 수 있다. 이 때 데이터 개수가 N개이면 시간 복잡도는 O(N)이 된다. 이 경우에는 구간 합을 구하는 속도가 너무 느리기 때문에 더 나은 알고리즘을 고안해야 한다.

2) 세그먼트 트리를 이용해 구하기 : 트리 구조 특성 상 N개 데이터의 합을 구할 때 시간 복잡도가 O(logN)이 된다.

3. 세그먼트 트리를 이용한 구간 합

단순 배열을 위와 같은 트리 구조로 변경했을 때 구간 합을 구하는 방법을 알아볼 것이다.

1) 구간 합 트리 생성하기

• 가장 먼저 최상단 노드에 전체 원소(0 ~ 11)를 더한 값을 삽입한다.

• 이후 최상단 노드의 양쪽 자식 노드에 각각 인덱스 0 ~ 5 원소의 합, 인덱스 6 ~ 11 원소의 합을 삽입한다.

• 위와 같이 부모 노드의 데이터 범위를 반씩 분할하여 그 구간의 합들을 저장하는 방식으로 트리를 채워 나가는 것이다. 이러한 과정을 반복하면 구간 합 트리의 전체 노드를 구할 수 있다.

  • 부모 노드의 데이터 범위를 start ~ end 라고 하면
  • 부모 노드 크기를 반으로 분할 : mid = (start + end) / 2
  • 자식 노드 중 왼쪽 노드는 start ~ mid / 오른쪽 노드는 mid + 1 ~ end

• 구간 합 트리를 만들 때는 인덱스 번호를 1로 시작한다.

  • 데이터의 인덱스는 0부터 시작하지만, 구간 합 트리를 1부터 시작하면 부모 노드 번호에 2를 곱하면 왼쪽 자식 노드를 가리키므로 인덱스를 설정하기 편하기 때문이다.

• 데이터의 개수가 N개일 때, 구간 합 트리는 N보다 큰 가장 가까운 제곱수를 구한 뒤, 그 수의 2배의 크기를 가져야 한다.

  • ex. 데이터의 개수가 12개라면, 12보다 큰 가장 가까운 제곱수는 16
  • 16 x 2 = 32이므로 구간 합 트리의 크기는 32이다.
  • 계산하기 귀찮다면 데이터 개수 x 4를 해주면 메모리를 조금 더 먹지만 편리하게 계산 가능하다.

🖥️ 예제 코드

int tree[32];
int datas[12];

// start : 범위 시작 / end : 범위 끝 / node : 현재 구간합 트리 노드 번호
int init(int start, int end, int node)
{
    // 범위에 수가 하나 남을 때까지 분할하고, 하나 남으면 해당 수 반환
    if (start == end) return tree[node] = datas[start];
    int mid = (start + end) / 2;
    // 현재 노드의 범위를 재귀적으로 반으로 분할하여 두 부분의 합을 자기 자신으로 할당
    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

2) 구간 합을 구하는 함수 만들기

• 만약 4 ~ 8 범위에 대한 합을 구한다고 하면 색칠 된 노드들의 값만 더해주면 된다.

🖥️ 예제 코드

// 범위 안에 있는 경우에 한해서만 더해주면 된다.
// start : 범위 시작 / end : 범위 끝 // node : 현재 구간합 트리 노드 번호
// left : 구하고자 하는 범위 시작 / right : 구하고자 하는 범위 끝
int sum(int start, int end, int node, int left, int right)
{
    // 범위 밖에 있는 경우
    if (left > end || right < start) return 0;
    // 범위 안에 있는 경우
    if (left <= start && end <= right) return tree[node];
    // 범위에 걸쳐있는 경우 두 부분으로 나누어 합 구하기
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) 
        + sum(mid + 1, end, node * 2 + 1, left, right);
}

3) 특정 원소 값을 수정하는 함수 만들기

• 특정 원소 값을 수정할 때는 해당 원소를 포함하고 있는 모든 구간 합 노드들을 갱신해준다.
• 만약 인덱스 7의 노드를 수정한다고 하면 색칠 된 노드들의 값만 수정하면 된다.

🖥️ 예제 코드

// index : 값을 수정하고자 하는 노드 / dif : 수정할 값
void update(int start, int end, int node, int index, int dif)
{
    // 범위 밖에 있는 경우
    if (index < start || index > end) return;
    // 범위 안에 있으면 내려가며 다른 원소도 갱신
    tree[node] += dif;
    if (start == end) return;
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index, dif);
    update(mid + 1, end, node * 2 + 1, index, dif);
}

4) 모든 과정 취합 코드

int tree[32];
int datas[12] = { 1, 9, 3, 8, 4, 5, 5, 9, 10, 3, 4, 5 };

// start : 범위 시작 / end : 범위 끝 / node : 현재 구간합 트리 노드 번호
int init(int start, int end, int node)
{
    // 범위에 수가 하나 남을 때까지 분할하고, 하나 남으면 해당 수 반환
    if (start == end) return tree[node] = datas[start];
    int mid = (start + end) / 2;
    // 현재 노드의 범위를 재귀적으로 반으로 분할하여 두 부분의 합을 자기 자신으로 할당
    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

// 범위 안에 있는 경우에 한해서만 더해주면 된다.
// start : 범위 시작 / end : 범위 끝 // node : 현재 구간합 트리 노드 번호
// left : 구하고자 하는 범위 시작 / right : 구하고자 하는 범위 끝
int sum(int start, int end, int node, int left, int right)
{
    // 범위 밖에 있는 경우
    if (left > end || right < start) return 0;
    // 범위 안에 있는 경우
    if (left <= start && end <= right) return tree[node];
    // 범위에 걸쳐있는 경우 두 부분으로 나누어 합 구하기
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) 
        + sum(mid + 1, end, node * 2 + 1, left, right);
}

// index : 값을 수정하고자 하는 노드 / dif : 수정할 값
void update(int start, int end, int node, int index, int dif)
{
    // 범위 밖에 있는 경우
    if (index < start || index > end) return;
    // 범위 안에 있으면 내려가며 다른 원소도 갱신
    tree[node] += dif;
    if (start == end) return;
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index, dif);
    update(mid + 1, end, node * 2 + 1, index, dif);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    init(0, 11, 1);
    // 구간 합 구하기
    cout << "0 ~ 12 구간 합 : " << sum(0, 11, 1, 0, 11) << endl;
    cout << "4 ~ 8 구간 합 : " << sum(0, 11, 1, 4, 8) << endl;

    // 특정 원소 값 수정하기
    cout << "인덱스 5의 원소 -5만큼 수정" << endl;
    update(0, 11, 1, 5, -5);

    // 구간 합 구하기
    cout << "0 ~ 12 구간 합 : " << sum(0, 11, 1, 0, 11) << endl;
}

[출력 결과]
0 ~ 12 구간 합 : 66
4 ~ 8 구간 합 : 33
인덱스 5의 원소 -5만큼 수정
0 ~ 12 구간 합 : 61

👁️‍🗨️ 참고 https://m.blog.naver.com/ndb796/221282210534

https://school.programmers.co.kr/learn/courses/30/lessons/67257

✍️ 문제 풀이

해당 문제는 단순 구현 문제로, 문자열 처리가 중점인 문제이다.

1) 입력받은 expression 문자열을 각 숫자와 연산자로 따로 나누어 저장한다.

• split() 함수 : 인수로 전달된 문자열을 숫자와 연산자로 나누어 같은 벡터에 순서대로 저장한다.
  • 문자열 내에서 '*', '+', '-' 를 각각 find 하여 그 인덱스(위치)가 가장 작은 연산자 (가장 앞에 있는 것)를 찾는다.
  • 해당 연산자를 기준으로 앞에 있는 문자열, 해당 연산자를 각각 result 벡터에 집어넣고, 기존 문자열을 연산자 뒤의 문자열로 교체한다.
  • 위 과정을 더 이상 연산자가 남지 않을 때까지 반복하고, 마지막 남은 문자열을 result 벡터에 집어넣고 result를 반환한다.
• 리스트 nums와 op를 선언하고, split() 함수에서 반환된 벡터를 확인하여 숫자 문자열은 nums에, 연산자는 op에 삽입한다.

2) 2차원 벡터 orders를 선언해 3개의 연산자로 만들 수 있는 우선순위 6개를 저장한다.

3) orders에 저장된 각각의 연산자 우선순위에 따라 주어진 문자열을 계산한다.

• nums와 op를 numsCopy, opCopy에 복사해 저장한다.
• 현재 순서 orders에 저장된 연산자들을 순서대로 적용하여 아래 과정을 반복한다.
  • opCopy에 저장된 각 연산자를 차례대로 확인한다.
    • 만약 해당 연산자가 orders의 현재 순서 연산자가 아니라면 다음 연산자로 넘어간다.
    • 현재 순서 연산자라면 opCopy의 끝 인덱스까지 확인할 때까지 아래 과정을 반복한다.
      • numsCopy에 저장된 해당 연산자의 앞과 뒤에 있는 숫자들을 해당 연산자로 계산해 , 원래 numsCopy에 앞에 있는 숫자의 위치에 저장한다.
      • opCopy의 해당 연산자와, numsCopy의 뒤에 있는 숫자를 삭제한다. (리스트이므로 자동으로 당겨짐)
      • opCopy의 맨 앞으로 돌아간다.
    • opCopy의 끝까지 확인했다면 orders의 다음 순서 연산자로 넘어간다.
• 위 과정이 완료되면 numsCopy에 계산 완료된 숫자 하나만이 남는다. 이 숫자를 result 벡터에 삽입한다.

4) 6개의 우선순위를 각각 적용하여 계산된 값들이 최종적으로 result에 저장되고, 이 값들의 절대값들을 비교하여 가장 큰 값을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <list>
using namespace std;

// 문자열을 각 연산자를 기준으로 나누어 숫자와 연산자로 저장
vector<string> split(string str)
{
    char dlim1 = '*', dlim2 = '+', dlim3 = '-';
    vector<string> result;
    int a, b, c;

    while (true)
    {
        a = find(str.begin(), str.end(), dlim1) - str.begin();
        b = find(str.begin(), str.end(), dlim2) - str.begin();
        c = find(str.begin(), str.end(), dlim3) - str.begin();

        if (a == str.size() && b == str.size() && c == str.size())
        {
            result.push_back(str);
            return result;
        }            
        else
        {
            int dlim = min({ a, b, c });
            result.push_back(str.substr(0, dlim));
            result.push_back(str.substr(dlim, 1));
            str = str.substr(dlim + 1, str.size() - dlim);
        }
    }
}

long long solution(string expression)
{
    // 연산자는 op, 숫자는 nums에 저장
    vector<string> v = split(expression);
    list<string> nums, op;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == "*" || v[i] == "+" || v[i] == "-")
            op.push_back(v[i]);
        else
            nums.push_back(v[i]);
    }

    vector<vector<string>> orders;
    orders.push_back({ "*", "+", "-" });
    orders.push_back({ "*", "-", "+" });
    orders.push_back({ "+", "*", "-" });
    orders.push_back({ "+", "-", "*" });
    orders.push_back({ "-", "+", "*" });
    orders.push_back({ "-", "*", "+" });

    vector<long long> result;
    for (int i = 0; i < orders.size(); i++)
    {
        list<string> numsCopy = nums, opCopy = op;
        for (int k = 0; k < 3; k++)
        {
            int j = 0;
            while(true)
            {
                if (j >= opCopy.size())
                    break;

                auto it = opCopy.begin();                // 연산자 이터레이터
                advance(it, j);
                if (*it != orders[i][k])
                {
                    j++;
                    continue;
                }

                auto prevNumsIt = numsCopy.begin();        // 연산자 이전 글자 이터레이터
                auto postNumsIt = numsCopy.begin();        // 연산자 다음 글자 이터레이터
                advance(prevNumsIt, j);
                advance(postNumsIt, j + 1);

                if (*it == "*")
                    *prevNumsIt = to_string(stoll(*prevNumsIt) * stoll(*postNumsIt));
                else if (*it == "+")
                    *prevNumsIt = to_string(stoll(*prevNumsIt) + stoll(*postNumsIt));
                else
                    *prevNumsIt = to_string(stoll(*prevNumsIt) - stoll(*postNumsIt));
                opCopy.erase(it);
                numsCopy.erase(postNumsIt);
                j = 0;
            }
        }
        result.push_back(stoll(*numsCopy.begin()));
    }

    long long maxValue = 0;
    for (int i = 0; i < result.size(); i++)
    {
        long long cur = llabs(result[i]);
        if (cur > maxValue)
            maxValue = cur;
    }
    return maxValue;
}

https://www.acmicpc.net/problem/14950

✍️ 문제 풀이

해당 문제는 최소 신장 트리(MST) 문제로, 모든 노드(== 도시)에서 다른 모든 노드로 향하는 간선이 있다고 가정하고, 이 간선들에 대해 크루스칼 알고리즘을 사용하여 모든 노드들이 이어지되, 이어지는 간선들의 가중치의 합이 최소가 되는 경우를 구해야 한다. 단, 도시가 하나 이어질 때마다 가중치가 증가하는 부분을 고려해야 한다.

1) 모든 노드들 사이에 존재하는 간선에 대한 tuple(두 노드 간 가중치, 노드A 번호, 노드B 번호)들을 저장하는 벡터인 edges에 모든 노드에서 다른 모든 노드로 향하는 간선에 대한 가중치를 계산해 저장한다.

2) edges 벡터에 대해 크루스칼 알고리즘을 적용한다.

• edges 벡터를 가중치의 오름차순으로 정렬한다.
• 모든 노드들에 대한 사이클 테이블이 자기 자신을 가리키도록 한다.
• 간선들을 차례대로 확인하며 아래 과정을 반복한다.
  • 간선에 연결된 노드A와 노드B가 같은 부모를 갖는지(같은 그래프에 포함되는지) 확인한다. (== find)
  • 만약 같은 부모를 갖지 않는다면 두 노드의 부모를 같게 합친다. (== union)
  • sum에 해당 간선의 가중치 + (t * count)를 누적한다.
    • sum : mst를 이루는 모든 간선의 가중치의 합
    • count : 지금까지 정복한 도시의 개수
    • 도시가 하나 정복될 때마다 다른 도시의 비용이 t만큼 증가하기 때문에, 다음 도시를 정복할 때 (지금까지 정복된 도시의 개수 * t)만큼 더 더해주어야 한다.
  • count를 하나 증가시킨다.

3) 위 크루스칼 알고리즘 과정이 끝나면 sum에 모든 도시를 정복하는 데에 필요한 최소 비용이 저장된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> tiii;

int n, m, t;
vector<tiii> edges;
int parent[10001];

int getParent(int n)
{
    if (parent[n] == n)
        return n;
    else
        return parent[n] = getParent(parent[n]);
}

void unionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);

    if (a < b)
        parent[b] = a;
    else
        parent[a] = b;
}

bool findParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);

    return (a == b);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> t;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back(tiii(c, a, b));
        edges.push_back(tiii(c, b, a));
    }

    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++)
        parent[i] = i;

    int sum = 0;
    int count = 0;
    for (int i = 0; i < edges.size(); i++)
    {
        int curA = get<1>(edges[i]);
        int curB = get<2>(edges[i]);

        if (!findParent(curA, curB))
        {
            unionParent(curA, curB);
            sum += get<0>(edges[i]);
            sum += t * count;
            count++;
        }
    }
    cout << sum;
}

https://www.acmicpc.net/problem/13549

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 수빈이의 현재 위치 n과 동생의 위치 k를 입력 받아 저장한다. => 이 때 n은 시작점, k는 목표 지점, 각 위치 지점들을 노드로 볼 수 있다.

2) 시작점에서 각 위치까지 최단 거리를 저장하는 배열 dp를 선언하고, dp의 모든 값을 무한대로 초기화한다.

3) 다익스트라 알고리즘을 실행하여 시작점에서부터 각 위치까지의 최단 거리를 구한다.

• 최소힙으로 구현하기 위해 우선순위 큐 pq를 선언하고, 오름차순으로 정렬되도록 한다.
  • pq에는 노드 정보 (해당 노드까지 최소 거리, 노드 번호)가 저장된다.
• pq에 (0, 시작 위치)를 삽입한다.
• dp[start](시작점에서부터 시작점까지의 최단 거리)를 0으로 초기화한다.
• pq가 빌 때까지 아래 과정을 반복한다.
  • pq에 저장되어 있는 노드 중 가중치가 가장 작은 노드에 대한 정보를 꺼낸다.
    • dist : 현재 노드까지의 거리
    • cur : 현재 노드의 번호
  • 만약 dp[cur] < dist라면 이미 최단 거리가 구해진 노드이므로 무시한다.
  • 위 경우가 아니라면 아래 과정을 반복한다.
    • 해당 문제는 미리 간선 정보가 제공되어 저장하고 시작하는 것이 아니고, 현재 위치에서 1, 1, 0의 가중치로 -1, +1, *2 위치에 이동이 가능하도록 되어있다. 즉, 이동했을 때의 위치가 현재 위치의 인접 노드라고 보는 것이다.
    • 따라서 cost에 현재 노드까지의 거리 + 현재 노드 ~ 이동했을 때 거리를 저장한다.
    • 만약 이동 했을 때 수빈이가 있을 수 있는 범위(0 이상 100000 이하)에 위치하고, cost가 저장되어있던 이동 위치의 dp보다 작다면 (cost < dp[인접 노드])
      • 인접 노드의 dp를 cost로 갱신한다.
      • 갱신된 인접 노드 정보 (인접 노드까지의 최소 거리, 노드 번호)를 pq에 삽입한다.

4) 위 과정이 끝나면 dp에는 시작점부터 다른 노드까지의 최소 거리들이 저장된다. 이 때, 동생의 위치 k까지의 최단 거리를 알고 싶은 것이기 때문에 dp[k]를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;

int n, k;
int dp[100001];
const long long INF = 1e9;

pii move(int cur, int i)
{
    if (i == 0)
        return pii(cur - 1, 1);
    else if (i == 1)
        return pii(cur + 1, 1);
    else
        return pii(cur * 2, 0);
}

void dijkstra(int start)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, start));
    dp[start] = 0;

    while (!pq.empty())
    {
        int dist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dp[cur] < dist) continue;
        for (int i = 0; i < 3; i++)
        {
            pii curEdge = move(cur, i);
            int cost = dist + curEdge.second;
            if (curEdge.first >= 0 && curEdge.first <= 100000 && cost < dp[curEdge.first])
            {
                dp[curEdge.first] = cost;
                pq.push(pii(cost, curEdge.first));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    fill(dp, dp + 100001, INF);
    dijkstra(n);
    cout << dp[k];
}

https://www.acmicpc.net/problem/5972

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 헛간 개수 n과 길의 개수 m을 입력 받아 저장한다. 이 때, 헛간 개수 == 노드 개수 / 길의 개수 == 간선 개수 라고 볼 수 있다.

2) 2차원 벡터 graph를 선언하고 n + 1 크기로 초기화 한다. 그리고 m개의 길에 대한 정보 pair(헛간 번호, 소의 마리수(가중치))를 입력 받아 graph에 저장한다. 이 때, 헛간끼리 이어진 길은 양방향으로 이동 가능하므로 간선 저장 시 양방향으로 이어준다.

3) 시작점인 1에서 각 헛간까지 최단 거리를 저장하는 배열 dp를 선언하고, dp의 모든 값을 무한대로 초기화한다.

4) 다익스트라 알고리즘을 실행하여 시작점에서부터 각 위치까지의 최단 거리를 구한다.

• 최소힙으로 구현하기 위해 우선순위 큐 pq를 선언하고, 오름차순으로 정렬되도록 한다.
  • pq에는 노드 정보 (해당 노드까지 최소 거리, 노드 번호)가 저장된다.
• pq에 (0, 시작 위치)를 삽입한다.
• dp[start](시작점에서부터 시작점까지의 최단 거리)를 0으로 초기화한다.
• pq가 빌 때까지 아래 과정을 반복한다.
  • pq에 저장되어 있는 노드 중 가중치가 가장 작은 노드에 대한 정보를 꺼낸다.
    • dist : 현재 노드까지의 거리
    • cur : 현재 노드의 번호
  • 만약 dp[cur] < dist라면 이미 최단 거리가 구해진 노드이므로 무시한다.
  • 위 경우가 아니라면 해당 노드의 인접 노드들에 대해 아래 과정을 반복한다.
    • cost : 현재 노드까지의 거리 + 현재 노드 ~ 인접 노드까지의 거리
    • 만약 cost가 저장되어있던 인접 노드의 dp보다 작다면 (cost < dp[인접 노드])
      • 인접 노드의 dp를 cost로 갱신한다.
      • 갱신된 인접 노드 정보 (인접 노드까지 최소 거리, 노드 번호)를 pq에 삽입한다.

4) 위 과정이 끝나면 dp에는 시작점부터 다른 노드까지의 최소 거리들이 저장된다. 이 때, 헛간 n까지의 최단 거리를 알고 싶은 것이기 때문에 dp[n]을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

int n, m;
vector<vector<pii>> graph;
int dp[50001];
const long long INF = 1e9;

void dijkstra(int start)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, start));
    dp[start] = 0;

    while (!pq.empty())
    {
        int dist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dp[cur] < dist) continue;
        for (int i = 0; i < graph[cur].size(); i++)
        {
            int cost = dist + graph[cur][i].second;
            if (cost < dp[graph[cur][i].first])
            {
                dp[graph[cur][i].first] = cost;
                pq.push(pii(cost, graph[cur][i].first));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    graph.resize(n + 1);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // 양방향 간선이므로 양쪽 노드에 모두 추가
        graph[a].push_back(pii(b, c));
        graph[b].push_back(pii(a, c));
    }

    fill(dp, dp + n + 1, INF);
    dijkstra(1);

    cout << dp[n];
}

https://www.acmicpc.net/problem/1446

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 지름길의 개수 m과 고속도로의 길이 n을 입력 받아 저장한다. => 여기서 고속도로 길이는 노드의 개수와 같다.

2) 2차원 벡터 graph를 선언하고 n + 1 크기로 초기화 한다. 그리고 m개의 지름길에 대한 정보 pair(상대 노드 번호, 가중치)를 입력 받아 graph에 저장한다. 또한 0 ~ n까지 각 위치에서 +1 위치로 가중치 1의 간선을 연결한다.

3) 시작점에서 각 위치까지 최단 거리를 저장하는 배열 dp를 선언하고, dp의 모든 값을 무한대로 초기화한다.

4) 다익스트라 알고리즘을 실행하여 시작점에서부터 각 위치까지의 최단 거리를 구한다.

• 최소힙으로 구현하기 위해 우선순위 큐 pq를 선언하고, 오름차순으로 정렬되도록 한다.
  • pq에는 노드 정보 (해당 노드까지 최소 거리, 노드 번호)가 저장된다.
• pq에 (0, 시작 위치)를 삽입한다.
• dp[start](시작점에서부터 시작점까지의 최단 거리)를 0으로 초기화한다.
• pq가 빌 때까지 아래 과정을 반복한다.
  • pq에 저장되어 있는 노드 중 가중치가 가장 작은 노드에 대한 정보를 꺼낸다.
    • dist : 현재 노드까지의 거리
    • cur : 현재 노드의 번호
  • 만약 dp[cur] < dist라면 이미 최단 거리가 구해진 노드이므로 무시한다.
  • 위 경우가 아니라면 해당 노드의 인접 노드들에 대해 아래 과정을 반복한다.
    • cost : 현재 노드까지의 거리 + 현재 노드 ~ 인접 노드까지의 거리
    • 만약 cost가 저장되어있던 인접 노드의 dp보다 작다면 (cost < dp[인접 노드])
      • 인접 노드의 dp를 cost로 갱신한다.
      • 갱신된 인접 노드 정보 (인접 노드까지 최소 거리, 노드 번호)를 pq에 삽입한다.

4) 위 과정이 끝나면 dp에는 시작점부터 다른 노드까지의 최소 거리들이 저장된다. 이 때, 0 ~ n이 현재 위치라고 가정할 때, 현재 위치까지의 최소 거리 + (목적지 - 현재 위치)를 전부 비교하여 가장 작은 값을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

int n, m;
vector<vector<pii>> graph;    // 0 ~ n까지 각 위치와 연결된 다른 위치들의 pii(인덱스, 거리)를 저장 
int dp[10001];                
const long long INF = 1e9;

void dijkstra(int start)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, start));
    dp[start] = 0;

    while (!pq.empty())
    {
        int dist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dp[cur] < dist) continue;
        for (int i = 0; i < graph[cur].size(); i++)
        {
            int cost = dist + graph[cur][i].second;
            if (cost < dp[graph[cur][i].first])
            {
                dp[graph[cur][i].first] = cost;
                pq.push(pii(cost, graph[cur][i].first));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m >> n;
    graph.resize(n + 1);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(pii(b, c));
    }

    // 0 ~ n까지 각 위치에서 +1 위치로 간선 연결 (길이는 1)
    for (int i = 0; i <= n; i++)
        graph[i].push_back(pii(i + 1, 1));

    fill(dp, dp + n + 1, INF);
    dijkstra(0);

    // 0 ~ n이 현재 위치일 때 -> 현재 위치까지의 최소 거리 + (목적지 - 현재 위치)를 전부 비교하여 가장 작은 값 찾기
    int minDist = INF;
    for (int i = 0; i <= n; i++)
    {
        int curDist = dp[i] + (n - i);    
        if (curDist < minDist)
            minDist = curDist;
    }
    cout << minDist;
}

• 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
• 음의 간선이 없을 때 정상적으로 동작
  • 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다.
• 그리디 알고리즘으로 분류된다.
  • 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
  • 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
    • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해 가능

2. 동작 과정

1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. (다른 노드로 가는 거리를 무한으로 설정. 자기 자신은 0) 3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5) 위 과정에서 3)과 4)를 반복한다. 6) 알고리즘이 끝나고 나면 최단 거리 테이블에 각 노드까지의 최단 거리 정보가 저장된다.

3. 동작 예시

1) 최단 거리 테이블에서 출발 노드 자신에 대해서는 0, 다른 노드들에 대해서는 무한으로 초기화

2) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 1번이므로 1번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)

• 2번 노드 : 1번 노드까지 최단 거리 0 + 1번 노드 ~ 2번 노드까지의 거리 2 = 2 (< 무한)
• 3번 노드 : 1번 노드까지 최단 거리 0 + 1번 노드 ~ 3번 노드까지의 거리 5 = 5 (< 무한)
• 4번 노드 : 1번 노드까지 최단 거리 0 + 1번 노드 ~ 4번 노드까지의 거리 1 = 1 (< 무한)

3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 4번이므로 4번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)

• 3번 노드 : 4번 노드까지 최단 거리 1 + 4번 노드 ~ 3번 노드까지의 거리 3 = 4 (< 5)
• 5번 노드 : 4번 노드까지 최단 거리 1 + 4번 노드 ~ 5번 노드까지의 거리 1 = 2 (< 무한)

4) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 2번이므로 2번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)

• 3번 노드 : 2번 노드까지 최단 거리 2 + 2번 노드 ~ 3번 노드까지의 거리 3 = 5 (> 4)
• 4번 노드 : 2번 노드까지 최단 거리 2 + 2번 노드 ~ 4번 노드까지의 거리 2 = 4 (> 1) => 4번 노드는 이미 방문 처리 된 노드여서 값이 확정되었으므로 이 같은 경우에는 더이상 확인하지 않아도 된다.

5) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 5번이므로 5번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)

• 3번 노드 : 5번 노드까지 최단 거리 2 + 5번 노드 ~ 3번 노드까지의 거리 1 = 3 (< 4)
• 6번 노드 : 5번 노드까지 최단 거리 2 + 5번 노드 ~ 6번 노드까지의 거리 2 = 4 (< 무한)

6) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 3번이므로 3번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)

• 2번 노드 : 3번 노드까지 최단 거리 3 + 3번 노드 ~ 2번 노드까지의 거리 3 = 6 (> 2)
• 6번 노드 : 3번 노드까지 최단 거리 3 + 3번 노드 ~ 6번 노드까지의 거리 5 = 8 (> 4)

7) 마지막까지 남은 노드 6에 대해서는 처리하지 않아도 된다.

4. 우선순위 큐를 이용한 동작 과정

1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. (다른 노드로 가는 거리를 무한대로 설정. 자기 자신은 0) 3) 우선순위 큐를 생성하고 출발 노드를 우선순위 큐에 넣는다. (거리 기준 오름차순 정렬) 4) 우선순위 큐의 가장 위에 있는 노드를 꺼내고, 해당 노드가 방문하지 않은 노드라면 그 노드의 인접 노드들까지의 거리를 기존 최단 거리 테이블과 비교한다. 5) 기존 최단 거리보다 짧으면 갱신한 뒤 해당 노드들을 우선순위 큐에 넣는다. 5) 위 과정에서 4)와 5)를 반복한다. 6) 알고리즘이 끝나고 나면 최단 거리 테이블에 각 노드까지의 최단 거리 정보가 저장된다.

5. 코드 예시

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

int n, m, start;            // 노드의 개수, 간선의 개수, 시작 노드 번호
vector<vector<pii>> graph;    // 그래프 데이터 저장
int d[100001];                // 최단 거리 테이블
const long long INF = 1e9;    // 무한을 의미하는 값

void dijkstra(int start)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;    // priority_queue는 최대힙으로 구현되어 있으므로, 최소힙으로 작동하기 위해 greater 추가
    pq.push(pii(0, start));
    d[start] = 0;

    while (!pq.empty())
    {
        // 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
        int dist = pq.top().first;    // 현재 노드까지의 비용
        int cur = pq.top().second;    // 현재 노드 번호
        pq.pop();
        // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if (d[cur] < dist) continue;
        // 현재 노드와 연결된 다른 인접 노드들을 확인
        for (int i = 0; i < graph[cur].size(); i++)
        {
            pii curEdge = graph[cur][i];
            int cost = dist + curEdge.second;
            // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[curEdge.first])
            {
                d[curEdge.first] = cost;
                pq.push(pii(cost, curEdge.first));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> start;

    graph.resize(n + 1);
    // 간선 정보 입력 받기
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(pii(b, c));    // a 노드에서 b 노드로 가는 비용이 c라는 의미
    }

    // 최단거리 테이블을 모두 무한으로 초기화
    fill(d, d + 100001, INF);

    // 다익스트라 알고리즘 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n + 1; i++)
    {
        if (d[i] == INF)
            cout << "INFINITY" << endl;
        else
            cout << d[i] << endl;
    }
}

6. 시간복잡도

• 힙 자료구조 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)
• 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상 횟수로는 처리되지 않는다.
  • 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선 개수(E)만큼 연산이 수행될 수 있다.
• 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사하다.
  • 시간 복잡도를 O(ElogE)로 판단할 수 있다.
  • 중복 간선을 포함하지 않는 경우 이를 O(ElogV)로 정리할 수 있다.
    • O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)

👁️‍🗨️ 참고 https://www.youtube.com/watch?v=acqm9mM1P6o&t=514s (동빈나 채널)

스마일게이트 x 에픽게임즈 에서 진행하는 언리얼 프로그래머 양성 교육으로, 이번이 1기 첫 모집이었다. 약 4개월의 시간 동안 제공되는 언리얼 엔진 교육을 들으면서, 자기주도 프로젝트를 진행하여 결과물을 구현하는 것이 교육 목표이다. 최근까지 유니티 교육을 받아 왔지만, 앞으로 내 목표를 위해서는 언리얼 엔진을 배워야 하지 않을까 라고 생각하던 중에 해당 교육을 알게 되어 지원했다.

선발 과정

1) 서류

서류 과정은 아래와 같이 필수 제출 항목과 선택 제출 항목으로 나눠져 있었다.

• 필수 제출
  • 지원 동기 및 목표
  • 프로젝트 계획서
• 선택 제출
  • 자기소개 및 개발 경험
  • 기술 포트폴리오

이 프로그램에 대한 열정을 보이기 위해서는 모든 항목을 제출하는 것이 당연하다고 생각하여 필수, 선택 여부에 상관없이 전부 제출했다. 지원 동기 및 목표는 지금까지 유니티 엔진을 사용하면서 느낀 언리얼 엔진의 필요성을 중점으로 작성했다.

그리고 앞으로 4개월 동안 진행할 프로젝트 계획서를 준비했는데, 지금까지 대부분 모작 프로젝트만 진행했던 것과 달리 이번에는 시놉시스부터 기능까지 내가 만들어 보고 싶은 게임을 처음으로 기획해봤다. 만약에 선정이 안 되더라도 혼자서 이 계획서로 프로젝트를 진행해 봐야겠다고 생각할 정도로 열심히 준비했다.

선택 제출 항목들은 이전에 메타버스 아카데미에서 진행했던 유니티 프로젝트들을 중심으로 각 프로젝트를 진행하면서 사용한 기술, 느낀 점 등의 내용을 작성하여 제출했다.

2) 테스트

테스트 과정은 미리 알려주신 주제 내에서 출제되는 객관식·주관식 혼합형 온라인 테스트였다. C++, 자료구조, 게임 알고리즘, 게임 수학 등과 같은 주제로 출제되었는데, 주제가 미리 주어졌었기 때문에 관련 내용들을 정리하고 공부해 두어서 많이 어렵지는 않았다. 다만 내가 수학에 약해서 게임 수학 관련 내용들이 좀 어렵게 느껴졌던 것 같다.. 수학 공부 열심히 해야지..

3) 면접

면접 과정은 판교에 있는 스마일게이트 건물에서 대면 면접으로 진행되었는데, 이런 면접은 처음 해보는 거라 그 전날부터 엄청 떨렸었다. 판교까지 가는 내내 미리 써둔 자기소개만 외우면서 갔다 ㅎㅎ..

면접은 약 40분 동안 3 : 1 (면접관님들 : 나) 로, 간단한 자기소개 + 프로젝트 계획서 설명 이후 면접관님들의 질문 순서로 진행되었다. 서류 단계 때 제출한 포트폴리오에 대한 질문이 많이 나올 것 같아서 포트폴리오 위주로 보고 갔었는데, 포트폴리오 관련 질문은 하나도 안 나왔다.. 거의 CS 지식이나 알고리즘, 게임 수학 위주로 질문하셨다.

대답 못 한 질문이 꽤 있어서 나오면서 아쉬운 마음이 들었었다. 여담으로 시설이 정말 좋아서 나중에 취업 준비 열심히 해서 꼭 이런 곳에서 일하고 싶다는 생각이 들기도 했다!

결과

면접을 본 뒤 1주 후인 어제 결과가 발표되었고, 최종 합격하게 되었다! 인턴 채용도 아니고 남들이 보기엔 별 거 아닐 수도 있겠지만, 면접 본 이후 결과가 나오기만을 기다리고 있었어서 결과 확인 후에 너무 기뻤다😢 이 프로그램이 내가 한 단계 더 성장할 수 있는 계기가 되었으면 좋겠다!

https://www.acmicpc.net/problem/11054

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, LIS 문제를 응용하여 푸는 문제이다. 최장 바이토닉 부분 수열은 ** 특정 인덱스에서의 최장 증가 수열과 최장 감소 수열을 합친 것의 최대값**이라고 볼 수 있다. ex. 수열 {50 10 20 30 25 20}의 최장 바이토닉 부분 수열은

• 인덱스 4에서의 최장 증가 수열인 {10 20 30}
• 인덱스 4에서의 최장 감소 수열인 {30 25 20}
• 위 둘을 합친 {10 20 30 25 20} 이 최장 바이토닉 부분 수열이 된다.

1) nums에 수열을 입력받아 저장하고, nums2에 입력 받은 수열을 역순으로 저장한다.

2) 배열 dp1, dp2를 선언하고, 각각을 차례대로 갱신한다.

• dp1[i] : i 번째 수까지 있을 때, 수열의 부분 수열 중 최장 증가 수열의 길이
• dp2[i] : i 번째 수까지 있을 때, 역순 수열의 부분 수열 중 최장 증가 수열의 길이 == 수열의 부분 수열 중 최장 감소 수열의 길이

3) i가 0 ~ n일 때

• (dp1[i]와 dp2[n - i + 1]의 합 - 1)을 구해 maxValue와 비교한다.

  • -1을 해주는 이유 : 가운데 수가 중복되어 더해지기 때문이다. ex. 인덱스 i에서의 최장 증가 부분 수열이 {10 20 30} 이고, 최장 감소 부분 수열이 {30 25 20} 일 때 최장 바이토닉 부분 수열은 {10 20 30 25 20}인데, 이 때 30이 중복되기 때문에 1을 빼준다.

• 만약 위 수가 maxValue보다 크다면 maxValue를 위 수로 갱신한다.

  

4) 최종적으로 maxValue에 최장 바이토닉 부분 수열의 길이가 저장된다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>
using namespace std;

int nums[1001];
int nums2[1001];
int dp1[1001];        
int dp2[1001];

int solution(int n)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (nums[i] > nums[j] && dp1[j] + 1 > dp1[i])
                dp1[i] = dp1[j] + 1;

            if (nums2[i] > nums2[j] && dp2[j] + 1 > dp2[i])
                dp2[i] = dp2[j] + 1;
        }
    }

    int maxValue = 0;
    for (int i = 0; i <= n; i++)
    {
        int sum = dp1[i] + dp2[n - i + 1] - 1;
        if (maxValue < sum)
            maxValue = sum;
    }
    return maxValue;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
        nums2[n - i + 1] = nums[i];
        dp1[i] = 1;
        dp2[i] = 1;
    }

    cout << solution(n);
}

https://www.acmicpc.net/problem/2565

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, LIS 문제를 응용하여 푸는 문제이다.

1) n에 전깃줄의 개수를 입력받아 저장한다.

2) edges 벡터를 선언하고, n개 만큼의 전깃줄에 대해 pair(A 전봇대 번호, B 전봇대 번호)를 입력받아 저장한다. 그리고 A 전봇대 번호를 기준으로 edges를 오름차순 정렬한다.

3) A 전봇대 번호의 오름차순으로 A 전봇대와 연결된 B 전봇대의 번호들을 정렬하면 하나의 수열이 만들어진다. 겹치는 전깃줄이 없으려면 (모든 A 전봇대 번호에 연결된 B 전봇대 번호)는 (더 큰 A 전봇대 번호와 연결된 B 전봇대 번호)보다 작아야 한다.

• ex. (A 전봇대 1 - B 전봇대 5) 와 (A 전봇대 2 - B 전봇대 4) 가 있으면 서로 겹치게 됨.

4) 따라서 만들어진 수열에서 최장 증가 수열을 구하면 -> 가장 많은 전깃줄 개수를 유지함과 동시에 전깃줄이 겹치지 않는 경우이다.

5) 최장 증가 수열(LIS) 구하기

• dp[i] : 수열이 i 번째 인덱스까지 있을 때, i 번째 수를 포함하는 최장 증가 수열의 길이
• i 번째 인덱스의 수와 j(0 ~ i-1) 번째 수를 차례대로 비교하며 dp를 갱신한다.
  • 만약 (i 번째 수 > j 번째 수) and (dp[j] + 1 > dp[i]) 라면
    • dp[i]를 dp[j] + 1로 갱신한다.
    • maxCount < dp[i]면 maxCount를 dp[i]로 갱신한다. (maxCount = 현재까지 최장 증가 수열 길이)

6) 전체 수열 길이 n에서 maxCount를 빼면 필요 없는 전깃줄 == 제거해야하는 전깃줄의 개수가 나온다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

int n;
vector<pii> edges;    // 전선의 시작 번호, 끝 번호 저장
int dp[101];

int solution()
{
    int maxCount = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (edges[j].second < edges[i].second && dp[j] + 1 > dp[i])
            {
                dp[i] = dp[j] + 1;

                if (maxCount < dp[i])
                    maxCount = dp[i];
            }
        }
    }
    return n - maxCount;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    edges.push_back(pii(0, 0));
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        edges.push_back(pii(a, b));
        dp[i] = 1;
    }
    sort(edges.begin(), edges.end());
    cout << solution();
}

https://www.acmicpc.net/problem/9252

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n 인덱스까지의 A 문자열이 있을 때, 1 ~ n 인덱스까지의 B 문자열과의 최장 공통 수열을 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

• 이 문제는 기존 LCS 문제와 같으나, 개수 뿐만 아니라 해당 수열을 직접 출력까지 해야한다. 따라서 LCS의 길이를 구하는 부분은 생략하고, 수열을 출력하는 부분만 알아보겠다. (9251번 : LCS 링크)

1) A 문자열의 길이가 n이고, B 문자열의 길이가 m이라고 할 때, dp[n][m]에는 A 문자열과 B 문자열 사이의 최장 증가 수열의 길이가 저장된다. 따라서 이 dp[n][m]까지 오는 경로를 역추적하면 최장 증가 수열이 어떤 문자로 구성되어있는지 알 수 있다.

2) 변수 i, j를 선언하고, 각각 n과 m으로 초기화한다. 또한 최장 증가 수열을 저장할 문자열 변수 answer를 선언한다.

3) i와 j가 모두 0이 될 때까지 아래 과정을 반복한다.

• 만약 str1[i] == str2[j]일 때(현재 순서 A 문자열의 글자와 B 문자열의 글자가 같을 때)
  • i와 j를 1씩 감소시키고, answer에 str1[i](현재 순서 글자)를 추가한다.
  • 두 문자열의 현재 순서 글자가 같은 글자일 때만 수열 길이가 증가하기 때문이다.
• 위 경우가 아니라면
  • 만약 dp[i][j] == dp[i - 1][j] 라면 (A 문자열의 길이가 B 문자열보다 1 짧은 경우의 최장 증가 수열의 길이를 가져온 경우)
    • i를 1 감소시킨다.
  • 만약 dp[i][j] == dp[i][j - 1] 라면 (B 문자열의 길이가 A 문자열보다 1 짧은 경우의 최장 증가 수열의 길이를 가져온 경우)
    • j를 1 감소시킨다.

4) answer에 최장 증가 수열이 뒤집힌 상태로 저장되어있으므로, 이를 반대로 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int dp[1001][1001];
string str1, str2, answer;

void solution()
{
    int maxCount = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (str1[i - 1] == str2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (maxCount < dp[i][j])
                {
                    maxCount = dp[i][j];
                }
            }
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[n][m] << endl;

    int i = n, j = m;
    while (i != 0 && j != 0)
    {
        if (str1[i - 1] == str2[j - 1])
        {
            answer += str1[i - 1];
            i--;
            j--;
        }
        else
        {
            if (dp[i][j] == dp[i - 1][j])
                i--;
            else if (dp[i][j] == dp[i][j - 1])
                j--;
        }
    }

    for(int i = answer.length() - 1; i >= 0; i--)
        cout << answer[i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> str1;
    cin >> str2;
    n = str1.size();
    m = str2.size();
    solution();
}

https://www.acmicpc.net/problem/11052

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n 종류의 카드팩까지 있을 때 1 ~ n 개의 카드를 사는 최대 금액을 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

• 이 문제는 평범한 배낭 문제와 유사하나, 배낭 문제는 현재 순서 물건이 하나밖에 존재하지 않는 반면, 해당 문제는 같은 물건(== 카드팩)을 여러 개 사용 가능하다.
• 따라서 현재 순서 물건을 넣는 경우에 현재 물건을 포함하는 경우의 dp값을 참조한다. (배낭 문제는 직전 물건까지만 있을 때의 dp를 참조)

1) n에 구매하고자 하는 카드의 개수를 입력받아 저장한다.

2) 2차원 배열 dp를 선언하고, 각 dp를 차례대로 갱신한다.

• dp[i][j] : i 번째 카드팩까지 있을 때, j개의 카드를 사는 최대 금액
• 문제 조건에 의해 n개보다 많은 개수의 카드를 살 수 없다. 따라서 현재 순서의 카드팩으로 j개의 카드를 사는 경우는 두 가지로 나뉜다.
  • 현재 순서 카드팩에 사고자 하는 카드 개수보다 많은 카드가 들어있을 때 (i > j) : 이 때는 현재 순서(i) 카드팩으로 j개의 카드를 살 수 없으므로 직전 순서(i-1) 카드팩까지 있을 때 j개의 카드를 사는 최대 금액과 같다.
  • 위 경우가 아닐 때는 아래 두 경우 중 큰 값을 dp[i][j]로 갱신한다.
    • 현재 순서 카드팩을 무조건 한 개 이상 넣는 경우 : 현재 순서 카드팩까지 있을 때 (j-현재 순서 카드팩 개수)개 카드 사는 최대 금액 + 현재 순서 카드팩의 금액
    • 현재 순서 카드팩을 사지 않는 경우 : 직전 순서 카드팩까지 있을 때 j개의 카드 사는 최대 금액
  • 위 과정을 점화식으로 나타내면
  • 각 i와 j에 대해 (i : 현재 카드 순서 (1 ~ n) / j : 사고자 하는 카드 개수 (1 ~ n))
  • if(i > j) dp[i][j] = dp[i - 1][j]
  • else dp[i][j] = max(dp[i][j - i] + costs[i], dp[i - 1][j])

3) dp[n][n]에 카드 종류가 n가지 있을 때, n개의 카드를 사는 최대 금액이 저장되므로 이를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
vector<int> costs;
int dp[1001][1001];        // dp[i][j] : i 번째 카드팩까지 있을 때 j개의 카드를 사는 최대 금액

int solution() 
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i > j)        
                dp[i][j] = dp[i - 1][j];
            else            
                dp[i][j] = max(dp[i][j - i] + costs[i], dp[i - 1][j]);                 
        }
    }
    return dp[n][n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    costs.push_back(0);
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        costs.push_back(num);
    }
    cout << solution();
}

https://www.acmicpc.net/problem/10844

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 각 자리 계단 수 중에 맨 끝이 0 ~ 9로 끝나는 수의 개수를 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

1) n에 계단 수의 개수를 구하고자 하는 자리 수를 입력받아 저장한다.

2) 2차원 배열 dp를 선언하고, dp[1][1 ~ 9]를 모두 1로 초기화 한다.

• dp[i][j] : i자리 수인 계단 수 중에 맨 끝이 j인 수의 개수
• 1자리 계단 수는 19가 존재. 따라서 1자리 계단 수 중 19로 끝나는 수의 개수는 각 1개

3) i가 2 ~ n일 때까지 계단 수의 개수를 전부 갱신한다.

• 현재 자리 수의 계단 수는 이전 자리 계단 수 끝에 (이전 자리 계단 수의 끝 자리 수 -1, +1) 해준 수를 붙이는 경우이다.
• ex. 2자리 계단 수를 구한다고 할 때
  • 1의 자리 계단 수 = 1, 2, 3, 4, 5, 6, 7, 8, 9
    • 1의 끝에 (1-1 = 0) 과 (1+1 = 2)를 붙인 수 -> 10, 12
    • 2의 끝에 (2-1 = 1) 과 (2+1 = 3)를 붙인 수 -> 21, 23
    • 3의 끝에 (3-1 = 2) 과 (3+1 = 4)를 붙인 수 -> 32, 34
    • 4의 끝에 (4-1 = 3) 과 (4+1 = 5)를 붙인 수 -> 43, 45
    • 5의 끝에 (5-1 = 4) 과 (5+1 = 6)를 붙인 수 -> 54, 56
    • 6의 끝에 (6-1 = 5) 과 (6+1 = 7)를 붙인 수 -> 65, 67
    • 7의 끝에 (7-1 = 6) 과 (7+1 = 8)를 붙인 수 -> 76, 78
    • 8의 끝에 (8-1 = 7) 과 (8+1 = 9)를 붙인 수 -> 87, 89
    • 9의 끝에 (9-1 = 8)를 붙인 수 -> 98
• 위 과정을 일반화하여 dp를 갱신하면
  • 맨 끝이 0인 자리 수의 개수 = 이전 자리 수 중 1로 끝나는 수의 개수
  • 맨 끝이 9인 자리 수의 개수 = 이전 자리 수 중 8로 끝나는 수의 개수
  • 맨 끝이 j(1~8)인 자리 수의 개수 = 이전 자리 수 중 j - 1, j + 1로 끝나는 수의 개수의 합
• 이를 점화식으로 표현하면
  • dp[i][0] = dp[i - 1][1]
  • dp[i][9] = dp[i - 1][8]
  • *(j : 1 ~ 8) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] *

4) dp[n]에 0 ~ 9로 끝나는 i자리 계단 수들의 개수가 각각 저장되어있으므로 해당 수들을 전부 더하면 n자리 계단 수들의 총 개수를 알 수 있다.

❗계단 수의 개수를 더하는 과정에서 오버플로우가 발생할 수 있기 때문에 dp를 구하는 과정마다 미리 MOD 연산을 해준다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
long long dp[101][10];        // dp[i][j] : i자리 수 계단 수 중에 맨 끝이 j인 수의 개수
const long long MOD = 1000000000;

long long solution() 
{
    // 1자리 계단수는 1 ~ 9 이므로 1 ~ 9로 끝나는 수의 개수는 각 1개씩
    for (int i = 1; i <= 9; i++)
        dp[1][i] = 1;

    for (int i = 2; i <= n; i++)
    {
        // 맨 끝이 0인 i자리 수의 개수 = 이전 자리(i - 1) 수 중 1로 끝나는 수의 개수
        dp[i][0] = dp[i - 1][1] % MOD;                                        
        // 맨 끝이 j(1 ~ 8)인 i자리 수의 개수 = 이전 자리(i - 1) 수 중 (j - 1)로 끝나는 수의 개수 + (j + 1)로 끝나는 수의 개수
        for (int j = 1; j <= 8; j++)
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;            
        // 맨 끝이 9인 i자리 수의 개수 = 이전 자리(i - 1) 수 중 8로 끝나는 수의 개수
        dp[i][9] = dp[i - 1][8] % MOD;        
    }

    long long maxValue = 0;
    for (int i = 0; i <= 9; i++)
        maxValue = (maxValue + dp[n][i]) % MOD;

    return maxValue;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    cout << solution();
}