: Raycast 스크립팅을 가진

게임오브젝트의 원점에서 내가 설정한 방향으로 Ray(광선)를 날려 내가 설정한 거리 이내에 물체가 있는지 없는지 충돌감지를 해주는 것

사용방법

Physics.Raycast

1.

public static bool Raycast(Vector3 origin, Vector3 direction, float maxDistance, int layerMask, QueryTriggerInteraction queryTriggerInteraction);

파라미터

반환

bool 변수를 return -> 만약 ray가 collider와 교차되었다면 true를 리턴, 아니라면 false를 리턴한다.

설명

씬(scene)의 모든 collider에 대해 점 origin에서 점 direction으로 , maxDistance 길이의 광선을 투사한다.

충돌을 생성하는 데 관심이 없는 모든 collider를 필터링하기 위해 선택적으로 레이어 마스크를 사용할 수 있다.

queryTriggerInteraction 작용을 통해 Trigger colliders가 hit를 생성하는지 여부 또는 global Physics.queriesHitTriggers 설정을 사용할지 여부를 제어할 수 있다.

Note: Raycasts는 Raycast origin이 콜라이더 내부에 있는 콜라이더를 감지하지 못한다.

2.

public static bool Raycast (Vector3 origin, Vector3 direction, out RaycastHit hitInfo, float maxDistance, int layerMask, QueryTriggerInteraction queryTriggerInteraction);

파라미터

설명

씬(scene)의 모든 collider에 ray 투사하고 적중된 대상에 대한 자세한 정보를 반환한다.

출처 : https://chameleonstudio.tistory.com/63 https://docs.unity3d.com/kr/530/ScriptReference/Physics.Raycast.html

1. Navigation and Pathfinding

• 내비게이션 시스템은 Scene geometry에서 자동으로 생성되는 내비게이션 메시를 사용하여 게임 월드에서 지능을 갖고 움직일 수 있는 캐릭터를 생성하는 데 도움을 줍니다. 역동적인 장애물은 런타임 시점에 캐릭터의 내비게이션을 바꾸도록 하며 off-mesh 링크는 문을 열거나 절벽 같은 지형에서 뛰어내릴 수 있도록 특정한 액션을 빌드한다.

2. 내비게이션 영역 및 비용

• Navigation Areas는 특정 영역을 걸어서 지나가는데 드는 비용(cost)을 뜻하며, 경로를 탐색할 때에는 낮은 비용 영역순으로 선택됨. 또한 각각의 navmesh agent에는 Area Mask가 있어 에이전트가 이동할 수 있는 영역을 지정할 수 있다.

• Water : 높은 비용이 할당되어 있어 걸어가는데 더 많은 비용이 소요됨. 이를 통해 물이 얕은 곳을 느리게 걸어가는 시나리오를 처리할 수 있다.

• Door : 특정 캐릭터만 접근할 수 있다. 이를 통해 사람은 통과할 수 있지만 좀비는 통과할 수 없는 시나리오를 처리할 수 있다.

3. 경로 탐색 비용

• 비용을 조절하여 경로 탐색자가 경로를 탐색할 때 선호하는 영역을 제어할 수 있다.
  • ex) 영역의 비용을 3.0으로 설정하면 해당 영역을 지나가기 위해서는 다른 경로로 지나갈 때보다 3배의 시간이 걸린다.

• Unity는 A* 를 사용하여 nav mesh에서 최단 경로를 계산한다.

• A* 는 연결된 노드 그래프에서 작동한다.

• Unity 내비게이션은 폴리곤 메시로 나타내기 때문에 경로 탐색자는 우선 각 폴리곤에 노드의 위치가 되는 포인트를 배치해야한다. 최단 경로는 이 노드들 사이에서 계산된다.

• 어떤 레벨에서 경로 탐색자는 항상 최단 경로를 선택하지 않는다는 점도 알아두어야 한다. 이는 노드 배치 때문이다. 작은 장애물 옆에 큰 열린 영역이 있을 때, 즉 내비게이션 메시에 아주 큰 폴리곤과 아주 작은 폴리곤이 포함될 때 이런 현상을 쉽게 볼 수 있다. 큰 폴리곤의 노드는 해당 폴리곤의 아무 곳에나 배치될 수 있는데, 경로 탐색자의 관점에서 볼 때 이것이 우회 경로로 보일 수 있다.

4. 내비게이션 시스템

• NavMesh : 내비게이션 메시의 줄임말로, 게임 월드에서 걸을 수 있는 표면을 뜻하며, 내비 메시를 사용하여 게임 월드 안에 움직일 수 있는 한 위치에서 다른 위치로 이동할 수 있는 경로를 찾을 수 있다. 데이터 구조는 level geometry에서 자동으로 빌드 또는 베이크 된다.

• NavMesh Agent : 컴포넌트를 사용하여 각자의 목적지를 이동하는 동안 서로를 피할 수 있는 캐릭터를 생성할 수 있다. 에이전트는 내비메시를 사용하여 게임 월드를 추론하며, 움직이는 장애물 뿐만 아니라 서로를 피하는 방법을 알게 된다.

• Off-Mesh Link : 컴포넌트를 사용하여 걸을 수 있는 표면만으로는 정의할 수 없는 내비게이션 단축키를 통합할 수 있다. 예를 들어 배수로나 울타리를 뛰어넘거나 문을 지나가기 전에 여는 행동 등은 모두 오프 메시 링크로 정의할 수 있다.

  • 

  • 

• NavMesh Obstacle : 컴포넌트를 사용하여 에이전트가 월드를 탐색하는 동안 회피해야 하는 움직이는 장애물을 정의할 수 있다. 이에 대한 예로는 물리 시스템이 제어하는 통이나 상자를 들 수 있다. 움직이는 장애물이라면 에이전트가 이를 피하도록 하고, 장애물이 정지한 경우 내비메시에 구멍을 carving하여 에이전트가 장애물을 돌아가도록 경로를 변경하거나, 정지한 장애물이 경로를 완전히 차단할 경우 에이전트가 다른 경로를 찾게 할 수 있다.

5. 내비게이션 시스템의 내부 작업

• 게임에서 캐릭터(agent)를 지능적으로 움직이려면 목적지를 찾기 위해 필요한 레벨 추론과 목적지까지 이동하는 방법이라는 두가지 문제를 해결해야함.

• 레벨을 추론하는 문제는 Scene 전체를 고려해야 한다는 점에서 훨씬 전역적이고 정적이다. 목적지까지의 이동은 지역적이고 동적이며, 이동하는 방향과 이동중인 다른 에이전트와의 충돌을 방지하는 방법에 대해서만 고려하면 된다.

걸을 수 있는 영역

• 게임 Scene에서 걸을 수 있는 영역을 나타내기 위해 내비게이션 시스템은 자체적인 데이터가 필요하다. 걸을 수 있는 영역은 씬에서 에이전트가 서거나 움직일 수 있는 장소를 정의한다.

• 걸을 수 있는 영역은 Scene의 geometry에서 에이전트가 설 수 있는 위치를 테스트하여 자동으로 빌드된다. 그런 다음 이러한 위치가 Scene geometry의 맨 위에 위치한 표면에 연결된다.

• nav mesh는 이 표면을 Convex 폴리곤으로 저장한다. Convex 폴리곤은 폴리곤 안의 두 지점 사이에 아무런 장애물이 없기 때문에 이러한 목적으로 유용하게 사용된다. 폴리곤의 경계를 비롯하여 서로 이웃한 폴리곤에 대한 정보도 저장한다. 이렇게 하면 걸을 수 있는 모든 영역을 추론할 수 있다.

경로 찾기

• Scene에서 두 위치 사이의 경로를 찾기 위해서는 먼저 시작 위치와 목적지 위치를 가장 가까운 폴리곤에 매핑해야 한다.

• 시작 위치에서 탐색을 시작하여 모든 이웃 폴리곤을 거쳐 목적지 폴리곤에 도달한다. 이동 중에 방문한 모든 폴리곤의 경로를 추적하여 시작에서 목적지까지 연결해주는 폴리곤의 시퀀스를 찾을 수 있다. -> A* 알고리즘 사용

장애물 회피

• Steering logic은 통로 선상에 있는 다음 코너의 포지션을 파악하고, 이에 기반하여 목적지에 도달하기 위한 원하는 방향과 속도를 계산한다. 원하는 속도를 사용하여 에이전트를 움직일 때 다른 에이전트와의 충돌이 발생할 수 있다.

  • Steering logic은 제어 신호의 설정에 따라 데이터 입력을 출력으로 라우팅하는 회로

• 장애물 회피는 원하는 방향으로 나아가되 다른 에이전트 및 내비게이션 메시의 가장자리와 충돌하지 않게 적절한 균형점을 찾아 새로운 속도를 선택한다. Unity는 상호간 속도 장애물(RVO)을 사용하여 충돌을 예견하고 방지한다.

글로벌 및 로컬

• 글로벌 내비게이션은 월드에서 통로를 찾는데 사용된다. 월드에서 경로를 탐색하려면 상당한 프로세싱 능력과 메모리가 필요하다.

• 경로를 정의하는 폴리곤의 linear list는 스티어링을 위한 유연한 데이터 구조이며, 에이전트의 포지션이 움직임에 따라 로컬하게 조정될 수 있다.

• 로컬 내비게이션은 다른 에이전트나 움직이는 오브젝트와 충돌없이 어떻게 효율적으로 다음 코너를 향해 나아갈 수 있는지를 결정한다.

장애물의 두가지 사례

• 내비게이션에는 다른 에이전트보다 다른 타입의 장애물이 많이 응용된다.

• 움직이는 장애물이라면 로컬 장애물 회피를 사용하는 것이 좋다. 이 경우 에이전트가 장애물을 예측하며 회피한다.

• 정지해 있을 수 있고 모든 에이전트의 경로를 차단하는 장애물이라면 글로벌 내비게이션인 내비게이션 메시에 영향을 주어야한다.

• 내비메시를 변경하는 것을 carving 이라고 한다. 이 프로세스는 장애물의 어떤 부분이 내비메시에 닿는지를 감지한 다음, 내비메시에서 해당 부분을 깎아내어 구멍을 만든다. 이를 계산할 때 매우 많은 비용이 소모되기 때문에 움직이는 장애물은 충돌 회피를 통해 처리하는 이유이기도 하다.

• 로컬 충돌 회피는 종종 흩어진 장애물을 피하는데 사용되기도 한다. 알고리즘이 로컬이므로 바로 직면한 충돌만 회피할 수 있으며 함정을 피하거나 장애물이 경로를 차단하는 경우를 처리할 수 없다. 이러한 경우는 카빙을 통해 처리할 수 있다.

출처 : https://docs.unity3d.com/kr/2021.3/Manual/nav-InnerWorkings.html

https://docs.unity3d.com/kr/current/Manual/nav-NavigationSystem.html

https://docs.unity3d.com/kr/530/Manual/class-OffMeshLink.html

• Dynamic A*

• D* 알고리즘은 시작점(Start state)에서 목표점(Goal state)까지의 경로비용을 최소화하는 서치 알고리즘 중의 하나.

• D* 알고리즘의 전역경로계획은 지도 데이터를 바탕으로 로봇이 출발하기 전에 이루어 질 수 있는데 Fig. 3의 각 셀의 화살표(Back pointer)는 전역경로 계획된 결과를 나타낸다. 셀에서 화살표의 방향은 근처 셀 중에서 경로비용이 가장 작은 셀을 나타낸다.

• 전역 경로계획은 목표점에서 거꾸로 시작점을 찾아가는 Backward 서치 방법으로 이루어진다.

• 지역 경로 계획은 로봇의 이동 중 새로운 고정 또는 이동장애물이 발견된 경우 기존 계획된 전역경로계획 결과를 바탕으로 새로운 장애물 근방의 고유비용을 수정한 후 이를 바탕으로 주위셀들의 경로비용과 화살표(Back Pointer)를 수정하게 된다.

• D star 알고리즘은 주어진 환경의 지도데이터가 틀렸을 경우와 움직이는 장애물이 있는 경우 새로운 환경 데이터를 기반으로 다시 맵을 구성해서 새로운 환경 데이터를 기반으로 다시 맵을 구성해서 새로운 경로를 찾아야하는 A* 알고리즘과 달리 이미 계획된 전역경로계획을 기반으로 필요한 영역에서만 지역경로계획을 수행하므로 실시간으로 경로를 변경 계획하는 것이 용이하다.

2. D* 알고리즘의 비용(cost) 함수

• D star 알고리즘은 경로비용을 최소화하는 알고리즘이므로 D* 알고리즘을 효율적으로 사용하기 위해서 경로 비용의 설계가 매우 중요한 역할을 한다.

• 식 (1)에서 h(X)는, 예를 들어 Fig 3에서 상태 X까지 소요되는 총 경로비용이며 Y는 상태 X에 도달하기 바로 이전 상태를 의미하며, 식 (2)에서 c(X,Y)는 근접 경로 비용으로 이전 상태 Y에서 현재 상태 X로의 경로 비용을 의미한다.

• 식 (2)에서 A(X,Y)는 상태 X와 상태 Y로 이동하는데 드는 비용이며, I(X)는 상태의 고유비용으로 인접 고정 장애물과 이동 장애물을 고려한 비용 함수이다.

3. D* 알고리즘의 장단점

• 장점

  • 전역 경로계획 뿐만 아니라 지역 경로계획도 동시에 사용 가능하다.

  • 예기치 못한 고정 장애물이나 움직이는 장애물을 회피하여 주어진 목적지까지 빠르게 도달할 수 있는 지역 경로계획을 신속히 알고리즘 통해 구현할 수 있다.

• 단점

  • 다른 알고리즘에 비해서 많은 데이터 저장공간을 필요로 한다.

출처 : https://www.koreascience.or.kr/article/JAKO201022262413085.pdf

4. D* lite 알고리즘

• LPA star 를 기반으로 하는 Sven Koenig 및 Maxim Likhachev 의 증분 휴리스틱 검색 알고리즘 , A* 및 Dynamic SWSF-FP 의 아이디어를 결합한 증분 휴리스틱 검색 알고리즘

• D star lite 는 원래 D star 또는 Focused D* 를 기반으로 하지 않지만 동일한 동작을 구현한다. 이해하기 쉽고 더 적은 수의 코드 줄로 구현할 수 있으므로 이름이 "D star Lite".

• LPA* 알고리즘

  • Lifelong Planning A*

  • A* 를 기반으로 하는 증분 휴리스틱 검색 알고리즘

  • A star 와 마찬가지로 LPA* 는 주어진 노드에서 목표까지의 경로 비용에 대한 하한선인 발견적 방법을 사용한다.

  • 휴리스틱이 음수가 아닌 것으로 보장되고(0은 허용 가능) 목표에 대한 가장 저렴한 경로의 비용보다 결코 크지 않은 경우 휴리스틱이 허용된다.

  • 에지 비용이 변경되면 노드의 일부만 다시 확장하면 되므로 LPA star 는 A star 보다 성능이 뛰어나다(후자가 처음부터 실행된다고 가정).

출처: https://en.wikipedia.org/wiki/Lifelong_Planning_A*

5. D* 알고리즘 구현

• Pseudo code

while (!openList.isEmpty()) {
    point = openList.getFirst();
    expand(point);
}

• Expend

void expand(currentPoint) {
    boolean isRaise = isRaise(currentPoint);
    double cost;
    for each (neighbor in currentPoint.getNeighbors()) {
        if (isRaise) {
            if (neighbor.nextPoint == currentPoint) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            } else {
                cost = neighbor.calculateCostVia(currentPoint);
                if (cost < neighbor.getCost()) {
                    currentPoint.setMinimumCostToCurrentCost();
                    openList.add(currentPoint);
                }
            }
        } else {
            cost = neighbor.calculateCostVia(currentPoint);
            if (cost < neighbor.getCost()) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            }
        }
    }
}

• check for raise

boolean isRaise(point) {
    double cost;
    if (point.getCurrentCost() > point.getMinimumCost()) {
        for each(neighbor in point.getNeighbors()) {
            cost = point.calculateCostVia(neighbor);
            if (cost < point.getCurrentCost()) {
                point.setNextPointAndUpdateCost(neighbor);
            }
        }
    }
    return point.getCurrentCost() > point.getMinimumCost();
}

출처 : https://en.wikipedia.org/wiki/D*

1. 다익스트라 알고리즘이란?

• 다익스트라 알고리즘(Dijkstra algorithm)은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.

• 다익스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다.

• 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS-IS (Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에서 주로 사용된다.

2. 알고리즘

• 시작할 꼭짓점은 초기점으로, 꼭짓점 Y의 거리를 초기점에서 Y까지의 거리로 정의한다. 다익스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 간선 완화(edge relaxation)이라고 한다.

  1. 모든 꼭짓점을 미방문 상태로 표시한다. 미방문 집합이라는 모든 미방문 꼭짓점의 집합을 만든다.

  2. 모든 꼭짓점에 시험적 거리 값을 부여한다: 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정한다. 초기점을 현재 위치로 설정한다.

  3. 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 시험적 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 A의 거리가 6이라고 표시되었고, 인접 꼭짓점 B로 연결되는 변의 길이가 2라고 한다면, A를 통한 B까지의 거리는 6 + 2 = 8이 된다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.

  4. 만약 현재 꼭짓점에 인접한 모든 미방문 꼭짓점까지의 거리를 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거한다. 방문한 꼭짓점은 이후에는 다시 방문하지 않는다.

  5. 두 꼭짓점 사이의 경로를 찾는 경우: 도착점이 방문한 상태로 표시되면 멈추고 알고리듬을 종료한다.

  6. 완전 순회 경로를 찾는 경우: 미방문 집합에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면 이는 출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘을 종료한다.

  7. 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 "현재 위치"로 선택하고 3단계로 되돌아간다.

3. 구현 (우선순위 큐 사용)

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    
        // 초기화
3
4      create vertex set Q
5
6      for each vertex v in Graph:
7          if v ≠ source
8              dist[v] ← INFINITY                          
        // 소스에서 v까지의 아직 모르는 길이
9          prev[v] ← UNDEFINED                             
        // v의 이전 노드
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                          
        // 메인 루프
15         u ← Q.extract_min()                         
            // 최고의 꼭짓점을 제거하고 반환한다
16         for each neighbor v of u:              
            // Q에 여전히 남아 있는 v에 대해서만
17             alt ← dist[u] + length(u, v)
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

출처 : https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

4. 다익스트라 알고리즘 vs A* 알고리즘

1. 목표점

   • 다익스트라는 시작점으로부터 나머지 정점들까지의 최단거리를 구한다.

   • A* 는 시작점이 정해지고, 목표점이 정해지면 두 개의 최단 거리를 구한다.

2. 남은 거리 고려

   • 다익스트라는 시작점에서 정점에 이르는 최단 거리만을 고려. 목적 정점이 없기에 남은 거리를 구할 수도 없다.

   • A* 는 고려한다.

3. 최적 경로

   • 다익스트라는 임의의 시작점으로부터 시작하여 모든 정점을 탐색. 최적 경로를 보장하지 않는다.

   • A* 는 시작지점부터 목표 지점까지의 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를 바탕으로 빠른 탐색을 한다. 최적 경로의 근사값을 보장한다.

출처 : https://hyo-ue4study.tistory.com/m/195

• A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나이다.

• 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x) 을 매기는 방법을 이용한다는 것이다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류 할 수 있다.

• A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 f(n)은 다음과 같다.

  

  • g(n) : 출발 꼭짓점으로부터 꼭짓점 n까지의 경로 가중치

  • h(n) : 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치 -> 휴리스틱 함수

장점과 단점

• 장점

  • 올바른 휴리스틱 함수를 사용하면 보다 빠른 최단거리 길찾기가 가능하다.

  • 주변환경 또는 추정값이 반영된 실질적 최단거리를 찾기 용이하다.

• 단점

  • 휴리스틱 함수 의존도가 강하다.

  • 최단경로를 결정 이후, 환경에 변동이 있을 시 유연하게 반응하기 힘들다.

  • 탐색할 지형정보의 크기가 방대해질수록 관리를 요하는 리스트 목록이 늘어나 시스템 메모리 고갈 및 CPU 처리시간 과다 요인이 될 수 있다는 것

  
  

A* 알고리즘 구현

• 구현방법

  • 우선순위 큐 사용 ( 우선순위 정렬요소는 f / 오름차순)

  1. 시작노드를 우선순위 큐에 넣는다.

  2. 우선순위 큐에서 다음 노드를 꺼내 현재 노드로 설정한다. 현재 노드는 지나간 노드 (close list)로 설정한다.

  3. 현재 노드의 주변 노드를 탐색한다.

     • close list에 포함된 노드라면 무시.

     • 만약 우선순위 큐(open list)에 포함되지 않은 노드라면 f(x)값을 구하고, 현재 노드를 주변 노드의 부모로 설정하고, 우선순위 큐에 등록한다.

       • 만약 주변 노드가 이미 open list에 등록되어 있다면, 자신보다 G값이 적은 노드가 있는지 확인하여 해당 노드를 현재노드의 부모노드로 바꾸고 f(x)를 재계산한다. (G값이 크다면 무시)

  4. 목표에 도달할 때까지 2~3을 반복한다.

  5. 목표를 찾으면 거꾸로 부모노드를 쫒아 역정렬하면 최단거리 경로가 된다.

• pseudo code

pq.enqueue(start_node, g(start_node) + h(start_node))       
// 우선순위 큐에 시작 노드를 삽입한다.

while pq is not empty       // 우선순위 큐가 비어있지 않은 동안
    node = pq.dequeue       // 우선순위 큐에서 pop한다.

    if node == goal_node    
    // 만약 해당 노드가 목표 노드이면 반복문을 빠져나온다.
        break

    for next_node in (next_node_begin...next_node_end)       
    // 해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        pq.enqueue(next_node, g(node) + cost + h(next_node)) 
        // 우선순위 큐에 다음 노드를 삽입한다.

return goal_node_dist       
// 시작 노드에서 목표 노드까지의 거리를 출력한다.

출처 : https://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://zprooo915.tistory.com/78

https://www.koreascience.or.kr/article/JAKO201115537947327.pdf

연도별 경로 탐색 알고리즘

D star 알고리즘 VS A star 알고리즘

• 객체의 이동 시작점과 목표점이 선정되면 D* 알고리즘의 내부 함수를 통해 셀 별 백 포인터를 형성한 후 초기경로를 생성하여 객체가 백 포인터를 따라 이동한다. 실시간 감지된 장애물은 해당 셀 주변의 백 포인터만을 변경하여 최종 목적지에 도달하게 된다.

• A* 알고리즘과의 특징적 차이는 최초 지형 정보와 경로탐색 과정에서 주어지는 추후 지형정보가 동일한지를 평가하는 기능

• A star 알고리즘이 정적으로 초기의 완전한 지형정보를 바탕으로 전방향 탐색(forward search)으로 최적의 경로를 산출하는 반면, D star 알고리즘은 불완전한 사전정보를 통해 후방향 탐색(backward search)으로 목적지가 변하거나 지형정보가 변화할 때 비교적 신속하게 적용이 가능하다는 점

1. XYZ축 그리기

////////////////draw XYZ
void DrawXYZ()
{
    glDisable(GL_LIGHTING);

    //x축 그리기 (빨간색)
    glColor3f(1.f, 0.f, 0.f);
    glBegin(GL_LINE_LOOP);
    glVertex3f(10.0, 0.0, 0.0);
    glVertex3f(-10.0, 0.0, 0.0);
    glEnd();

    //y축 그리기 (초록색)
    glColor3f(0.f, 1.f, 0.f);
    glBegin(GL_LINE_LOOP);
    glVertex3f(0.0, 10.0, 0.0);
    glVertex3f(0.0, -10.0, 0.0);
    glEnd();

    //z축 그리기 (파란색)
    glColor3f(0.f, 0.f, 1.f);
    glBegin(GL_LINE_LOOP);
    glVertex3f(0.0, 0.0, 10.0);
    glVertex3f(0.0, 0.0, -10.0);
    glEnd();

}

2. 정육면체 그리기

삼각형을 그리는 함수를 만든 뒤 그 함수를 이용하서 사각형을 만드는 함수를 만든다. 사각형을 만드는 함수를 이용하여 정육면체를 그리면 된다.

void DrawTriangle(GLfloat I)
{
    glColor3f(0.2f, 0.2f, 0.6f);
    glBegin(GL_TRIANGLES);
    glNormal3f(0.0, 0.0, 1.0);
    glVertex3f(0.0, 0.0, 0.0);
    glNormal3f(0.0, 0.0, 1.0);
    glVertex3f(I, 0.0, 0.0);
    glNormal3f(0.0, 0.0, 1.0);
    glVertex3f(0.0, I, 0.0);
    glEnd();

}

void DrawSquare(GLfloat I)
{
    glPushMatrix();
    glTranslatef(-0.5 * I, -0.5 * I, 0.5 * I);
    DrawTriangle(I);
    glPopMatrix();

    glPushMatrix();
    glRotatef(180.0, 0.0, 0.0, 1.0);
    glTranslatef(-0.5 * I, -0.5 * I, 0.5 * I);
    DrawTriangle(I);
    glPopMatrix();
}

void DrawCube(GLfloat I)
{
    glPushMatrix();
    DrawSquare(I);
    glRotatef(90.0, 0.0, 1.0, 0.0);
    DrawSquare(I);
    glRotatef(90.0, 0.0, 1.0, 0.0);
    DrawSquare(I);
    glRotatef(90.0, 0.0, 1.0, 0.0);
    DrawSquare(I);
    glPopMatrix();

    glPushMatrix();
    glRotatef(90.0, 1.0, 0.0, 0.0);
    DrawSquare(I);
    glRotatef(180.0, 1.0, 0.0, 0.0);
    DrawSquare(I);
    glPopMatrix();

}

3. 두 개의 OpenGL 광원 적용

DrawScene 함수 안에서 구현. 숫자 3을 누르면 실행되게 했다.

if (b_number_3)
    {
        glEnable(GL_LIGHTING);
        glDisable(GL_LIGHT0);
        glDisable(GL_LIGHT3);
        glDisable(GL_LIGHT4);
        glEnable(GL_LIGHT1);
        glEnable(GL_LIGHT2);
        GLfloat light12_ambient[] = { 0.5f, 0.5f, 0.9f, 1.0f };
        GLfloat light12_diffuse[] = { 0.2f, 0.2f, 0.2f, 1.0f };
        GLfloat light12_position[] = { 3.0f, 3.0f, 6.0f, 1.0f };
        GLfloat mat0_noemission[] = { 0.0f, 0.0f, 0.0f, 1.0f };

        GLfloat mat0_shininess[] = { 50.0 };
        GLfloat mat0_properties[2][4] =
        {
        {0.3f, 0.3f, 0.3f, 1.0f}, //ambient 
        {0.2f, 0.2f, 0.2f, 1.0f}, //diffuse
        };

        glLightfv(GL_LIGHT1, GL_AMBIENT, light12_ambient);
        glLightfv(GL_LIGHT2, GL_DIFFUSE, light12_diffuse);
        glLightfv(GL_LIGHT2, GL_POSITION, light12_position);

        glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, mat0_shininess);
        glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, mat0_properties[mat_diffuse]);
        glMaterialfv(GL_FRONT_AND_BACK, GL_AMBIENT, mat0_properties[mat_ambient]);
        glMaterialfv(GL_FRONT_AND_BACK, GL_EMISSION, mat0_noemission);
    }

4. Spotlight가 정육면체 주변을 돌면서 정육면체를 비추도록 하기

숫자 4를 누르면 실행되게 했다.

    if (b_number_4)
    {
        glEnable(GL_LIGHTING);
        glDisable(GL_LIGHT1);
        glDisable(GL_LIGHT2);
        glEnable(GL_LIGHT0);

        GLfloat spotlight_ambient[] = { 0.7f, 0.7f, 0.7f, 1.0f };
        GLfloat spotlight_diffuse[] = { 0.2f, 0.2f, 0.7f, 1.0f };
        GLfloat spotlight_specular[] = { 0.3f, 0.3f, 0.3f, 1.0f };
        GLfloat mat0_no[] = { 0.3f, 0.3f, 0.3f, 1.0f };
        GLfloat spotlight_direction[] = { 0.0f, 0.0f, -1.0f, 1.0f };
        GLfloat mat0_noemission[] = { 0.0f, 0.0f, 0.0f, 1.0f };

        glLightfv(GL_LIGHT0, GL_SPECULAR, spotlight_specular);
        glLightfv(GL_LIGHT0, GL_DIFFUSE, spotlight_diffuse);
        glLightfv(GL_LIGHT0, GL_AMBIENT, spotlight_ambient);
        glLightf(GL_LIGHT0, GL_SPOT_CUTOFF, 80.0f);
        glLightf(GL_LIGHT0, GL_SPOT_EXPONENT, 80.0f);
        glLightfv(GL_LIGHT0, GL_SPOT_DIRECTION, spotlight_direction);

        glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, mat0_no);
        glMaterialfv(GL_FRONT_AND_BACK, GL_AMBIENT, mat0_no);
        glMaterialfv(GL_FRONT_AND_BACK, GL_EMISSION, mat0_noemission);

        spot_angle += 0.1f;
        glPushMatrix();
        glTranslatef(0.0, 0.0, 0.0);
        glRotatef(spot_angle, 0, 0, 1);
        GLfloat lightpos[4] = { 1.0f, 1.0f, 10.0f, 1.0f };
        glLightfv(GL_LIGHT0, GL_POSITION, lightpos);
        glPopMatrix();
        glDisable(GL_LIGHT3);
        glDisable(GL_LIGHT4);
    }

5. 정육면체에 GL_EMISSION을 적용

숫자 5를 누르면 실행되게 함.

if (b_number_5)
    {
        glEnable(GL_LIGHTING);
        glEnable(GL_LIGHT3);
        glEnable(GL_LIGHT4);
        glDisable(GL_LIGHT0);
        glDisable(GL_LIGHT1);
        glDisable(GL_LIGHT2);

        ////light 3,4 설정
        GLfloat light_emission[] = { 0.5f, 0.6f, 0.2f, 1.0f };  //emission
        GLfloat light34_ambient[] = { 0.1f, 0.1f, 0.1f, 1.f };
        GLfloat light34_diffuse[] = { 0.3f, 0.3f, 0.3f, 1.f };
        GLfloat mat0_shininess[] = { 50.0 };
        GLfloat mat0_no[] = { 0.3f, 0.3f, 0.3f, 1.0f };

        glLightfv(GL_LIGHT3, GL_DIFFUSE, light34_ambient);
        glLightfv(GL_LIGHT4, GL_AMBIENT, light34_diffuse);

        glMaterialfv(GL_FRONT_AND_BACK, GL_EMISSION, light_emission);
        glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, mat0_shininess);
        glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, mat0_no);
        glMaterialfv(GL_FRONT_AND_BACK, GL_AMBIENT, mat0_no);
    }

과제 2

Texture Mapping

void DrawGLScene() {
    gluLookAt(0.f, 30.f, m_cameraDist, 0.f, 0.f, 0.f, 0.f, 1.f, 0.f);

    if (b_mouseMove) {
        glRotatef(angleVelocity * (m_currentPoint.x - m_anchorPoint.x), 0.0, 1.0, 0.0);
        glRotatef(angleVelocity * (m_currentPoint.y - m_anchorPoint.y), 1.0, 0.0, 0.0);
    }

    BuildCheckerImage();

    glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
    glTexImage2D(GL_TEXTURE_2D, 0, 3,
        checkerImageWidth, checkerImageHeight, 0, GL_RGB,
        GL_UNSIGNED_BYTE, &checkerImage[0][0][0]);
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
    glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_DECAL);

    //up
    glEnable(GL_TEXTURE_2D);
    CString fname("image\\up.bmp");
    BindTextureFile((LPCSTR)fname, 0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(-500.0, 500.0, 500.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(-500.0, 500.0, -500.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(500.0, 500.0, -500.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(500.0, 500.0, 500.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    //down
    glEnable(GL_TEXTURE_2D);
    CString fname1("image\\down.bmp");
    BindTextureFile((LPCSTR)fname1, 0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(-500.0, -500.0, 500.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(-500.0, -500.0, -500.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(500.0, -500.0, -500.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(500.0, -500.0, 500.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    glEnable(GL_TEXTURE_2D);
    CString fname2("image\\left.bmp");
    BindTextureFile((LPCSTR)fname2, 0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(-500.0, 500.0, 500.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(-500.0, 500.0, -500.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(-500.0, -500.0, -500.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(-500.0, -500.0, 500.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    glEnable(GL_TEXTURE_2D);
    CString fname3("image\\right.bmp");
    BindTextureFile((LPCSTR)fname3, 0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(500.0, 500.0, 500.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(500.0, 500.0, -500.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(500.0, -500.0, -500.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(500.0, -500.0, 500.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    glEnable(GL_TEXTURE_2D);
    CString fname4("image\\front.bmp");
    BindTextureFile((LPCSTR)fname4, 0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(-500.0, -500.0, 500.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(-500.0, 500.0, 500.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(500.0, 500.0, 500.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(500.0, -500.0, 500.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    glEnable(GL_TEXTURE_2D);
    CString fname5("image\\back.bmp");
    BindTextureFile((LPCSTR)fname5, 0);
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(-500.0, -500.0, -500.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(-500.0, 500.0, -500.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(500.0, 500.0, -500.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(500.0, -500.0, -500.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    //draw Box1
    glEnable(GL_TEXTURE_2D);
    CString fname7("image\\crate.bmp");
    BindTextureFile((LPCSTR)fname7, 0);
    glBegin(GL_QUADS);
    //front
    glTexCoord2f(0.0, 1.0);            glVertex3f(0.0, 0.0, 10.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(0.0, 10.0, 10.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(10.0, 10.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(10.0, 0.0, 10.0);
    glEnd();

    //back
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(0.0, 10.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(10.0, 10.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(10.0, 0.0, 0.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(0.0, 0.0, 0.0);
    glEnd();

    //up
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(0.0, 10.0, 10.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(0.0, 10.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(10.0, 10.0, 0.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(10.0, 10.0, 10.0);
    glEnd();

    //down
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(0.0, 0.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(10.0, 0.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(10.0, 0.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(0.0, 0.0, 10.0);
    glEnd();

    //left -> 1번씩 당긴거
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(0.0, 0.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(0.0, 10.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(0.0, 10.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(0.0, 0.0, 10.0);
    glEnd();

    //right
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(10.0, 10.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(10.0, 0.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(10.0, 0.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(10.0, 10.0, 10.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);
    //draw Box1 finish

    //draw Box2
    glEnable(GL_TEXTURE_2D);
    CString fname8("image\\crate.bmp");
    BindTextureFile((LPCSTR)fname8, 0);
    //down
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(5.0, 10.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(15.0, 10.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(15.0, 10.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(5.0, 10.0, 10.0);
    glEnd();

    //up
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(5, 20.0, 10.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(5, 20.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(15, 20.0, 0.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(15, 20.0, 10.0);
    glEnd();

    //front
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(5, 10.0, 10.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(5, 20.0, 10.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(15, 20.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(15, 10.0, 10.0);
    glEnd();

    //back
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(5.0, 20.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(15.0, 20.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(15.0, 10.0, 0.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(5.0, 10.0, 0.0);
    glEnd();

    //left
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(5, 10.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(5, 20.0, 0.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(5, 20.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(5, 10.0, 10.0);
    glEnd();

    //right
    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 1.0);            glVertex3f(15, 20.0, 0.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(15, 20.0, 10.0);
    glTexCoord2f(1.0, 0.0);            glVertex3f(15, 10.0, 10.0);
    glTexCoord2f(1.0, 1.0);            glVertex3f(15, 10.0, 0.0);
    glEnd();
    glDisable(GL_TEXTURE_2D);

    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
    glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
    glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_DECAL);

    //draw grass
    glEnable(GL_TEXTURE_2D);
    CString fname9("image\\grass.bmp");
    BindTextureFile((LPCSTR)fname9, 0);

    glBegin(GL_QUADS);
    glTexCoord2f(0.0, 80.0);            glVertex3f(-50.0, 0.0, -50.0);
    glTexCoord2f(0.0, 0.0);            glVertex3f(-50.0, 0.0, 50.0);
    glTexCoord2f(80.0, 0.0);            glVertex3f(50.0, 0.0, 50.0);
    glTexCoord2f(80.0, 80.0);            glVertex3f(50.0, 0.0, -50.0);
    glEnd();

    glDisable(GL_TEXTURE_2D);

}

1. virtual 함수란?

virtual 키워드를 추가하면 컴퓨터는 런타임 시에 적절한 함수를 찾아서 실행하게 된다.

virtual 키워드가 붙은 함수를 가상 함수(virtual function)이라고 한다.

그리고 파생 클래스에서의 함수가 기본 클래스의 가상 함수를 오버라이드(override) 하려면 두 함수의 꼴이 완전히 동일해야 한다.

출처 : https://junstar92.tistory.com/177

• 클래스에 virtual 함수를 선언하면 vtable이 생성된다.

• 클래스의 virtual 함수들은 이 vtable에 매핑이 됨.

• 자식 클래스가 부모 클래스의 virtual 함수를 오버라이딩하면 자식 클래스의 vtable에 오버라이딩 함수가 매핑 된다.

• 다형성을 사용하여 자식 클래스가 부모 클래스로 형변환이 되었을경우, virtual로 선언된 함수들은 vtable에서 가져오기 때문에 자식 클래스가 오버라이딩한 함수를 제대로 호출할 수 있게 된다.

2. 소멸자에 virtual을 쓰는 이유

• 다형성을 사용하여 자식 클래스가 부모 클래스로 형변환을 하고 삭제를 한 경우, virtual로 소멸자를 선언하지 않았다면 vtable을 참조하지 않고 부모의 소멸자만 호출하게 된다.

• 이런 경우 만약 자식 클래스에서 메모리를 추가 할당한 경우 메모리 누수가 발생한다.

3. 포함과 상속의 차이점을 설명

• 파생 클래스가 부모 클래스와 is-a 관계가 성립할 때는 상속

• 클래스 2개가 has-a 관계가 성립할 때는 포함

• is-a 관계가 성립하지 않음에도 단지 편의 때문에 상속을 남발해서는 안된다.

• is-a : 상속을 기반으로 함. ex) Apple은 과일의 일종

• has-a : 하나의 객체가 다른 객체를 가지고 있는 관계. ex) Car에는 Engine이 있다.

4. 메모리 단편화를 해결할 수 있는 기법들

• External Fragmentation의 해결방안

  • 1) Storage Compaction (압축)

      : 주기적으로 삭제 공간을 회수하여 메모리 공간들을 정리하는 방식. 
    비용이 많이 들어 자주 쓸 수 없는 것이 단점.
    주로 정해진 주기에 따라서 실행됨.

• 2) Coalescing (통합)

   : 단편화로 인해 쪼개진 공간들 중 인접한 공간들을 합쳐서 더 크게 만드는 방식

  • 3) Placement strategy (배치전략) : 배치를 잘하는 방식을 사용하여 단편화의 발생 가능성을 최대한 줄이는 방식. (best-fit, first-fit, worst-fit)

  • 4) paging 기법 사용 : 고정 길이 방식의 대표 유형

• Internal fragmentation의 해결방법

  • 1) Segmentation(세그멘테이션) : 가변 길이 방식의 대표 유형

    • 2) 메모리 풀 : 동적 할당의 방식 중 하나. 미리 필요한 만큼 할당받아서 만들어 둔 다는 것이 동적할당과의 차이점.

출처 : https://nevertheless-intheworld.tistory.com/8

5. 멀티 코어를 활용할 수 있는 프로그래밍 기법

• 멀티 스레드

• 멀티 프로세스

• OpenMP

6. STL에서 erase와 remove의 차이점

• erase : iterator에 해당하는 하나의 요소만을 삭제한다. Capacity가 실제로 감소한다.

• remove : 해당 범위 중에 해당 값과 일치하는 모든 요소를 삭제한다. Capacity가 감소하지는 않는다.

7. 스택과 큐의 차이점

• 스택은 Last-in - first-out 후입선출 구조이다. (LIFO)

• 큐는 First-In - First-Out 선입선출 구조이다. (FIFO)

8. 배열과 리스트의 차이점

• 1) 배열

• 배열은 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조이다.

  • 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리가 남게되어 메모리가 낭비된다.

  • 처음 크기를 10으로 지정한다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이 됨.

• 데이터 개수가 정해져있고 접근이 빈번할 경우 배열이 효율적

• 2) 리스트

• 리스트는 원소들 간의 순서로 순서가 있는 데이터의 모임. 다른 이름으로는 시퀀스(Sequence)라고도 부른다.

• 빈틈없는 데이터의 적재라는 장점을 가짐.

• Array List와 Linked List는 구현 방법에 따라 나뉜다.

  • Array List
    • 배열을 이용해 리스트를 구현한 것

- 접근이 빠름. 하지만 데이터 추가와 삭제가 느림.

- 동적으로 사용하기 힘듦.

• Linked List

  • 연결로 구현한 리스트

  • 한 원소에서 값과 다음 원소의 주소를 알고 연결하는 방식

  • 순차적으로 접근함 W(n)

  • 삽입, 삭제는 O(1)이지만 해당 지점까지 접근해야 하므로 W(n)일 수 있음.

  • 배열과 다르게 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다.

• 배열은 Compile time에 할당되는 정적 메모리 할당, 리스트는 새로운 Node가 추가되는 runtime에 할당되는 동적 메모리 할당

출처 : https://jy-tblog.tistory.com/38

9. vector와 list의 차이점

• vector를 중간 삽입 시 원소를 밀어내지만 list는 노드를 연결만 하기 때문에 삽입/삭제 부분에서 시간복잡도의 우위를 가짐

• vector는 랜덤 부분 접근이 가능하지만 list는 더블 링크드리스트로 되어 있기 때문에 랜덤 접근이 불가능. 검색 측면에서는 vector가 우위를 가짐

• 1) Vector

  • 연속적인 메모리

  • 미래에 들어갈 요소를 위해 선할당을 한다.

  • 요소를 추가하는 어느 때나, 전체 vector의 메모리를 재할당 할 수 있다.

  • 랜덤하게 vector 요소에 접근 할 수 있다.

  • 장점

    • 개별 원소들 접근 가능 & 접근 속도 빠름

    • 원소를 마지막에 삽입하는 것이 빠름

    • 랜덤으로 원소 순회가 가능

  • 단점

    • 컨테이너 끝이 아닌 곳에 삽입/제거시 성능이 현저히 떨어짐

    • 동적이라 확장/축소가 편하나 확장시 비용이 큼

• 2) 리스트

  • 비연속적인 메모리

  • 리스트는 double linked list로 구현되어 있음

  • 메모리 선할당을 하지 않음

  • 추가와 제거에 비용이 싸고, 리스트 어디서든 일어날 수 있음

  • 요소에 랜덤 접근 불가능

  • 장점

    • 컨테이너 어느 위치에서라도 삽입/제거가 빠름

    • 원소들의 컨테이너 내 이동이 빠름

  • 단점

    • 원소의 인덱스로 직접 접근이 불가능함

    • 특정 원소에 접근하려면 처음이나 끝부터 선형 탐색을 해야함

    • 컨테이너 내 순회가 forward / reverse만 가능하여 느림

    • 원소 간 상호 연결 정보를 위해 추가적 메모리 비용 발생

출처 : https://chanheess.tistory.com/154

10. 클래스와 구조체의 차이점

• 구조체는 접근제어 지시자를 선언하지 않으면 public으로, 클래스는 private로 선언된다는 것

11. OOP의 특징

1. 캡슐화, Encapsulation : 한 객체가 특정한 하나의 목적을 위해 필요한 데이터나 메소드를 하나로 묶는 것

   • 데이터는 외부에서 직접 접근을 하면 안되고 함수를 통해서만 접근해야함

2. 정보 은닉, Information hiding : 캡슐화의 목표. 내부 구조는 private하게 감춰두고 외부에서 조작할 수 있는 정보만 public으로 공개함.

3. 상속, Inheritance : 기존 메소드와 변수를 물려받되, 필요한 기능을 더 추가하거나 자식클래스에게 맞게 재정의하는 방법

4. 추상화, Abstraction : 공통의 속성이나 기능을 묶어 이름을 붙이는 것

5. 다형성, Polymorphism : 하나의 변수명이 상황에 따라 다른 의미로 해석될 수 있다는 것을 뜻함

   • 일반적으로 오버라이딩 혹은 오버로딩을 의미

6. 동적 바인딩 : runtime 값에 따라 변수 데이터 타입, 호출될 함수가 결정됨

출처 : https://computasha.github.io/CS-OOP/

12. SOLID

1. SRP(Single Responsibility Principle), 단일 책임 원칙 : 모든 클래스는 단 한 가지의 책임을 부여 받아 수정할 이유가 단 한가지여야 함

2. OCP(Open-Closed Principle), 개방 폐쇄 원칙 : 소프트웨어의 구성요소(컴포넌트, 클래스, 모듈, 함수)가 확장에 대해서는 유연하여야 하지만 수정에 대해서는 폐쇄적이어야 함

3. LSP(Liskov Substitution Principle), 리스코프 치환 원칙 : 상위 타입은 항상 하위 타입으로 대체할 수 있어야 함

4. ISP(Interface Segreagation Principle), 인터페이스 분리 원칙 : 어떤 클래스가 다른 클래스에 종속될 때에는 가능한 최소한의 인터페이스만을 사용해야 함

5. DIP(Dependency Inversion Principle), 의존성 역전 원칙 : 상위 모듈이 하위 모듈에 종속성을 가져서는 안되며 양쪽 모두 추상화에 의존해야 함

13. template란?

• 템플릿(template)은 C++ 프로그래밍 언어의 한 기능으로, 함수와 클래스가 제네릭 형과 동작할 수 있게 도와 준다. 함수나 클래스가 개별적으로 다시 작성하지 않고도 각기 다른 수많은 자료형에서 동작할 수 있게 한다.

• 템플릿은 C++에서 프로그래머들에게 유용한데, 특히 다중 상속과 연산자 오버로딩과 결합할 때 그러하다. C++ 표준 라이브러리는 연결된 템플릿의 프레임워크 안에서 수많은 유용한 함수들을 제공한다.

출처 : https://ko.wikipedia.org/wiki/%ED%85%9C%ED%94%8C%EB%A6%BF_(C%2B%2B)

14. 스마트포인터란?

• 스마트 포인터

  • c++에서 new 키워드를 통해 동적 할당한 메모리는 반드시 delete를 사용하여 해제해야한다. 만약 해제 하지 않으면 메모리 누수(Memory leak)가 발생하게 되는데 스마트 포인터에서는 이러한 실수를 방지하기 위해 사용이 끝난 메모리를 자동으로 해제해주는 것 외에 다양한 기능을 제공한다.

    • 장점

      • 자동 메모리 해제 (예외가 발생해도 메모리를 해제해줌)

      • 포인터 자동 초기화

    • c++ 11 부터는 3가지 스마트 포인터를 제공한다. 이 3가지 스마트 포인터는 참조 횟수(Reference count)에 따라서 구별된다.

    • 참조 횟수 : 해당 메모리를 참조하는 포인터가 몇 개인지 나타내는 값, 참조 횟수가 0이 되면 메모리를 자동으로 해제한다.

      • unique_ptr : 참조 횟수가 1인 스마트 포인터, 한 객체(메모리 주소) 당 하나의 포인터만 허용함

      • shared_ptr : 참조 횟수가 1 이상인 스마트 포인터

      • weak_ptr : 객체를 참조를 해도 참조 횟수가 증가하지 않는 포인터. (스마트 포인터가 서로를 가리키면 영원히 참조 횟수가 0이 되지 않는 순환 참조가 발생하므로 이를 제거하기 위해 사용됨)

              unique_ptr<T> p(new T);
             shared_ptr<T> p(new T);
              weak_ptr<T> p(new T);

출처 : https://janghyeonjun.github.io/language/smartpointer-memorypool/

15. 메모리 풀이란?

• 사용할 큰 메모리를 미리 할당하고 이를 작은 메모리 블록으로 나누어 메모리가 필요할 때마다 이 블록을 건네주고, 다 사용한 블록은 돌려받는 기법

• 직접 구현하거나 apr_pool, boost::pool과 같은 라이브러리를 통해 사용할 수 있다.

• 장점

  • 잦은 할당/해제시 발생하는 비용을 줄여준다.

  • 메모리 할당 시 실제로 몇 바이트를 할당했는지 추가적으로 기록하는데, 이러한 메모리 사용을 줄여준다.

  • 메모리 단편화 문제 해결

• 단점

  • 쓸데없이 메모리 공간을 차지할 수 있기 때문에 적절하게 크기를 설정하지 않으면 공간 활용도가 떨어지는 문제가 있다.

16. 스택으로 큐 구현하기, 큐로 스택 구현하기

• 스택으로 큐 구현하기

  class makeQueueUsingStack 
  {
  private:
    stack<int> a;
    stack<int> b;
  

public:

void enqueue(int data)
{
    a.push(data);
}

int dequeue()
{
    if (b.empty())
    {
        while (!a.empty())
        {
            b.push(a.top());
            a.pop();
        }
    }

    int data = b.top();
    b.pop();

    return data;
}

};

- 큐로 스택 구현하기

class makeStackUsingQueue { private: queue a; queue b;

public: void push(int data) { if (a.empty()) { a.push(data); } else { while (!a.empty()) { b.push(a.front()); a.pop(); }

        a.push(data);

        while (!b.empty())
        {
            a.push(b.front());
            b.pop();
        }
    }
}

int pop()
{
    int data = a.front();
    a.pop();

    return data;
}

};

출처 : https://tdm1223.github.io/algorithm/stackQueue/



# 컴퓨터 그래픽스

- 컴퓨터를 이용해 실제 세계의 영상을 조작하거나 새로운 영상을 만들어내는 기술을 가리킨다.

- 컴퓨터 그래픽스에는 가상 세계에 구축된 모델로부터, 계산에 의해서, 씬을 시뮬레이션 하는 경우, 실세계의 화상 정보를 가공해 화상을 조작하는 경우, 화상과는 직접 관계가 없는 데이터 등을 가시화하는 경우가 있다.

- 모양과 색을 수치로 변화하여 디지털로 나타내는 논리적 표현 방법이다. 확대, 축소, 회전 등의 변환이 가능하고 색의 변경이 쉽고, 3차원 공간에서 자유자재로 이동하면서 다각도에서도 볼 수 있다. 광원의 위치에서 물체 각 면의 밝기를 나타낼 수 있고, 표면의 재질감과 투명감 등 다양하고 섬세한 묘사가 가능하다. 이렇듯 시간과 공간을 자유롭게 조작할 수 있다는 점이 강점이다.

### 1. 타겟 위치와의 각도 계산

- 플레이어 정면 벡터를 A

- 플레이어에서 타겟 위치까지의 벡터를 B

- 각도 = acos(dot(A, B))

- 방향까지 정확히 구하기 위해선 외적을 사용해야함.

![](https://velog.velcdn.com/images/al_potato/post/b83b4f5f-72a7-41e3-9358-053a28382502/image.png)

<br>

### 2. 쿼터니언은 어떤 경우에 사용하는가? 그리고 사용하는 이유는 무엇인가?

- 회전각에 대한 보간(=구면 보간)이 필요한 경우 행렬보다 계산이 빠르고 간단하다.

- 회전 행렬에 의해서 두 축의 회전값이 겹칠 때 발생하는 문제(짐벌락)을 해결할 수 있다.

![](https://velog.velcdn.com/images/al_potato/post/7bd858ee-e35e-41aa-9fe4-49eda896ff98/image.png)

- 짐벌이란 단일 축으로 물체가 회전하도록 중심축을 가진 구조물이다.

- 오일러 각이라는 것은 3차원상의 강체의 방향과 회전을 정의하기위해 만들어낸 시스템이다.

- x,y,z 이 세축이 회전에서 종속적인 이유는 바로 오일러 각에서 회전 자체를 이 세 축으로 나눠서 계산하기 때문이다.

- 세 축에 대한 회전때문에 발생하는 짐벌락을 피하기 위해서는 특정한 축에 대한 회전을 시도하거나, 쿼터니언을 통해 회전시키면 된다.

출처: https://handhp1.tistory.com/3

<br>

### 3. 컬링 기법들을 아는 대로 나열하고 설명

- 컬링이란 카메라에 보이지 않는 부분을 제거하는 작업을 총칭한다.

- Backface Culling - 폴리곤의 후면 제거

- Frustum Culling - 시야 절두체 외 제거

- Occlusion Culling - 가려진 폴리곤 제거

- BSP, PVS (Potential Visibility Sets) - 구역 별로 보일 수 있는 구역 지정 컬링

- 기타 공간 처리 기법들

- Unity에서 Occlusion Culling 기법 사용해봤음
    -> 카메라에 보이지 않는 부분은 렌더링 비활성화하는 기능
   https://docs.unity3d.com/kr/2018.4/Manual/OcclusionCulling.html

<br>

### 4. 그림자를 생성하는 기법들을 아는 대로 나열하고 설명

- 원형 그림자

- Projected Shadow - 투영 그림자

- Shadow Map - 깊이 버퍼맵(쉐도우 맵) 사용

- Volume Shadow - 쉐도우 볼륨을 생성하고, 스텐실 버퍼를 사용


질문들 & 답 출처 : https://www.slideshare.net/agebreak/0410-10197035?related=2

<br>

### 5. 렌더링 파이프라인이 무엇인지와 그 순서

![](https://velog.velcdn.com/images/al_potato/post/b1a6102c-eb92-4e98-ae7b-3860884f48ad/image.png)

- 렌더링 파이프라인 : 3차원 이미지를 2차원 래스터 이미지로 표현을 하기위한 단계적인 방법을 말한다.

- 그래픽 파이프라인의 발생 -> 변형 -> 버텍스 당 광원 처리(vertex shader) -> 변형 가시화 및 변형 일반화 -> 프리미티브 발생(Geometry shader) -> 오려내기(클리핑) -> 뷰포트 변형 -> 스캔 변환 및 래스터화 -> 텍스처링, 음영 처리 -> 화면 표시

출처 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%BD%EC%8A%A4_%ED%8C%8C%EC%9D%B4%ED%94%84%EB%9D%BC%EC%9D%B8

![](https://velog.velcdn.com/images/al_potato/post/f3623695-137a-4142-af3a-9bd22d40d846/image.png)

<br>

### 6. transformation pipeline

![](https://velog.velcdn.com/images/al_potato/post/206192a1-6445-47f2-a549-39efccd665a0/image.png)

![](https://velog.velcdn.com/images/al_potato/post/5141008d-7390-4b1c-9e66-9147b1130ca5/image.png)

<br>

### 7. Lighting Types

![](https://velog.velcdn.com/images/al_potato/post/b5399b1a-4cdc-46c2-913e-9c48d7ba3a50/image.png)


- Ambient
  - scattered light (no directions)

  - From everywhere
    -  <span style="color: red">All-directions light</span>

- Diffuse
  - Directional light : <span style="color: red">from one direction light</span>
  - Once hit on a surface, it scatters in all directions
    - Viewpoint - independent

    - appears equally bright

- Specular
  - <span style="color: red">Directional light</span>

  - bounces off in a preferred direction
    - Creates highlights

    - Viewpiont - dependent

<br>

### 8. bump mapping

- 렌더링될 물체의 픽셀마다 표면 법선을 흔들어 높낮이가 있어 보이게 하는 컴퓨터 그래픽 기술 중 하나이다.

- 범프 매핑으로 주로 쓰이는 기술에는 법선 매핑, 시차 매핑이 있다.

- 범프 매핑은 울퉁불퉁한 표면을 텍스처를 통해 좀 더 사실적으로 나타내기 위한 방법이다.

- 3차원 장면을 렌더링할 때 3차원 모델과 조명에 따라 화면상의 픽셀의 밝기와 색이 결정된다. 물체가 보여야할 지 결정하는 기하학적인 계산을 하고, 표면 법선을 계산하기 위해 <span style="color: red">삼각법</span>을 사용한다.

- 표면법선과 빛의 방향만을 가지고, 퐁 셰이딩이나 이와 유사한 계산법으로 밝기를 계산한다. 빛이 표면과 평행하게 들어올 때는 표면은 검게 보이고, 수직으로 들어올 때는 가장 밝게 보인다. 그 이후에 물체를 좀 더 사실감있게 표현하기 위해 물체의 표면에 <span style="color: red">텍스쳐</span>를 씌운다.

- 텍스처를 씌운 후에, 각 픽셀마다 다음과 같은 처리를 한다.
  - 1. 렌더러는 표면의 각 지점에 대응하는 <span style="color: red">높이맵</span>을 찾는다.

  - 2. 그리고 삼각법을 통해서 높이맵의 표면법선을 계산한다.

  - 3. 2단계에서 계산된 범프맵의 법선을 물체 표면 법선에 더한다. (표면법선을 흐트려뜨린다고도 한다.)

  - 4. 새로운 울퉁불퉁한 표면에 퐁 셰이딩과 같은 방법으로 밝기를 계산한다.

<br>

### 9. phong shading

- 고러드 쉐이딩에서는 하이라이트나 반사광을 표현할 수 없는데 이것을 가능하게 해주는 쉐이딩 기법

- 게임에서는 퐁 쉐이딩이 적용될 명암 단계를 미리 이미지화 해놓고 면의 각에 따라 만들어 둔 이미지 중 필요한 부분만을 사용

- phong에 의해 제안된 방법으로 꼭짓점 벡터 역시 전체 삼각형 내에서 보정되어지는 방법이다.

- 퐁 쉐이딩된 삼각형 내의 모든 점은 그 표면 표준 벡터의 방향으로 벡터의 방향을 이루게 된다. 그러므로 조명 과정을 통해 삼각형 내의 모든 점들이 보다 정확한 색상을 가질 수 있도록 해준다.

출처 : https://cglink.com/terms/1085

<br>

# C#
### 1. C#의 특징

- 객체 지향 언어

- 닷넷 프로그램이 동작하는 닷넷 플랫폼을 가장 직접적으로 반영하고, 또한 닷넷 플랫폼에 강하게 의존하는 프로그래밍 언어

- Garbage Collection

- 자료형을 정확히 선언해야함.

<br>


### 2. namespace란?

- namespace는 관련 개체 집합을 포함하는 범위를 선언하는 데 사용된다. 네임스페이스를 사용하여 코드 요소를 구성하고 전역적으로 고유한 형식을 만들 수 있다.

- namespace끼리 이름은 달라야 한다.

- 다른 namespace 영역은 class 이름이 같아도 상관없다.

- using을 사용하면 namespace의 이름을 생략할 수 있다.

- namespace의 클래스 접근은 static 한정자를 이용해야함

출처 : https://m.blog.naver.com/bug_ping/221425846342

<br>


# Unity

### 1. 게임 최적화 방법

- Unity 게임을 더 빠르게 하기 위한 체크리스트

  - PC 용으로는 타겟 GPU의 스펙에 맞게 정점 수를 20만에서 300만보다 적게합니다.

  - 내장 쉐이더를 사용하는 경우, Mobile 또는 Unlit의 카테고리에서 선택합니다. 모바일이 아닌 플랫폼에서도 작동하지만 더 복잡한 쉐이더가 단순화되고 근사화(approximated)된 버전입니다.

  - 씬에서 다른 메테리얼의 수가 낮도록 억제합니다 - 서로 다른 오브젝트간에 메테리얼을 최대한 공유합니다.

  - 움직이지 않는 오브젝트에 대해 Static을 설정하고 Static Batching과 같은 내부 최적화를 허용합니다.

  - Only have a single (preferably directional) pixel light affecting your geometry, rather than multiples.

  - Bake lighting rather than using dynamic lighting.

  - 가능한한 압축 텍스처 포맷을 사용하고, 그 외의 경우는 32비트보다 16비트를 선택합니다.

  - Avoid using fog where possible.

  - Occlusion Culling의 장점을 배운 뒤, 복잡하고 static한 씬에 의해 표시되는 지오메트리의 양 및 드로우콜을 줄일 수 있습니다. 오클루전 컬링의 효과가 나오는 레벨의 설계를 합니다.

  - Skybox을 사용하여 멀리 있는 지오메트리를 “진짜처럼 보이게 합니다.”
픽셀 쉐이더를 사용하거나 Texture Combiner를 사용하여 다중 패스가 아닌 복수의 텍스처를 믹스합니다.

  - Use half precision variables where possible.

  - 복잡한 숫자 계산에서는 사용을 최소화하고, 예를 들면 pow, sin, cos 등을 픽셀 쉐이더에서의 사용을 최소화합니다.

  - 프라그먼트(Fragment) 당 텍스처를 보다 적어지도록 합니다.

출처 : https://docs.unity3d.com/kr/530/Manual/OptimizingGraphicsPerformance.html

<br>

### 2. Coroutine이란?

![](https://velog.velcdn.com/images/al_potato/post/93438659-32c2-4d84-be87-fdb8cc0899b9/image.png)


- Update 함수에 코드를 추가하는 것도 프레임마다 페이드 할 수 있다. 그러나 이러한 작업은 보통 코루틴을 사용하면 편리하다.

- 코루틴은 실행을 중지하여 Unity에 제어권을 돌려주고, 그러나 계속할 때는 다음 프레임에서 중지한 곳부터 실행을 계속할 수 있는 기능입니다.

- 게임 중의 태스크는 정기적으로 수행해야 하며, 간단한 방법은 Update 함수에서 할 수 있다. 그러나 이 함수는 초당 몇 번이나 호출된다. 작업이 너무 자주 반복할 필요가 없는 경우, 코루틴에 넣어 매 프레임 실행하지 않고 정기적으로 업데이트 할 수 있다.

- 단점
  - 스크립트가 disable 될 때 코루틴도 같이 종료시켜주어야 하는 번거로움

  - 가비지(Garbage)를 자주 생성함
     - StartCoroutine을 할 때 가비지를 많이 생성함

     - yield 문을 사용할 때, new WaitForSeconds와 같이 새로 인스턴스를 생성하는 부분이 문제가 된다. -> yield 문이 동일한 초나, 동일한 조건으로 계속 반복되는 상황이라면 캐싱하여 사용

<br>

### 3. particle 시스템이란?

- 파티클(Particles) 은 파티클 시스템에 의해 큰 숫자로 표시되고 이동되는 작고 단순한 이미지 또는 메시다. 각 파티클은 유체 또는 비정질 엔티티의 작은 부분을 나타내며, 모든 파티클의 효과가 전체 엔티티의 느낌을 만든다. 

- 액체, 연기, 구름, 화염 및 마법 주문과 같은 효과의 경우 Particle Systems 그래픽스 방식을 사용하여 고유한 유동성과 에너지를 표현할 수 있다.

출처 : https://docs.unity3d.com/kr/2017.4/Manual/ParticleSystems.html

<br>

# 네트워크

### 1. TCP/UDP가 무엇인지와 차이점

- TCP와 UDP는 전송 계층에서 사용하는, 데이터를 보내기 위해 사용하는 프로토콜

- TCP는 연결형 서비스로 가상 회선 방식을 제공하고, 높은 신뢰성을 보장하고 흐름 제어 및 혼잡 제어 기능을 제공한다.
  - 전자 메일이나 www 서비스에서 사용됨

- UDP는 비연결형 서비스로 데이터그램 방식을 제공하고, 패킷에 순서 부여나 재조립등의 기능을 처리하지 않기 때문에 연속성이 중요한 서비스에 사용된다.
   - 실시간 스트리밍에서 사용됨

• 프로그램 : 어떤 작업을 위해 실행할 수 있는 파일

• 프로세스 : 컴퓨터에서 연속적으로 실행되고 있는 프로그램

  • 동적인 개념으로는 실행된 프로그램을 의미

  • 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것

  • 메모리에 올라와 실행되고 있는 프로그램의 인스턴스 (독립적인 개체)

  • 운영체제로부터 시스템 자원(주소공간, 파일, 메모리 등)을 할당받는 작업의 단위

_ 프로그램과 프로세스는 다르다._

• 프로그램은 명령어를 내용으로 가진 디스크에 저장된 파일. 즉 수동적인 존재(Passive entity)

• 프로세스는 다음에 실행할 명령어를 지정하는 프로그램 카운터 및 관련된 자원의 집합을 가진 능동적 존재(active entity)

• 특징 : 프로세스는 각각의 독립적인 메모리 영역(Code, Data, Stack, Heap의 구조)를 할당

  • Code: 프로그램을 실행시키는 실행 파일 내의 명령어(소스코드)
  • Data: 전역변수, Static변수의 할당
  • Heap: 동적 할당을 위한 메모리 영역
  • Stack: 지역변수, 함수 호출 시 전달되는 파라미터를 위한 메모리 영역

  

1. Stack : 지역변수, 매개변수, 복귀 번지 등이 저장되어 있는 프로그램이 자동으로 사용하는 임시 메모리 함수 호출 시 생성되고, 함수 종료시 반환됨 (LIFO)

2. Heap : 프로그래머가 동적으로 사용하는 영역 malloc, free 또는 new, delete에 의하여 할당 또는 반환되는 영역. garbage collector가 활동하는 경우 자동으로 반환되는 경우도 있음

3. Data : 전역변수(global), 정적변수(Static), 배열(Array), 구조체(Structure)등이 저장됨

1) 초기화 된 데이터: data에 저장
2) 초기화 되지 않은 데이터 : bss(Block Stated Symbol)에 저장
=> data 영역이 런타임 이전에 초기화 하는 것이라면 bss는 런타임 이후 초기화 하는 것

4. Code(text) : 작성한 코드가 들어가는 부분 read-only 영역. 프로세스가 종료될 때 까지 계속 유지되는 영역

• 각 프로세스는 별도의 주소 공간에서 실행, 한 프로세스는 다른 프로세스의 변수나 자료구조에 접근X

• 한 프로세스가 다른 프로세스의 자원에 접근하려면 프로세스 간의 통신(IPC, Inter-Process Communication)을 사용

  • 파이프, 파일, 소켓등을 사용

스레드(Thread)

• 스레드(thread) : 한 프로세스 내에서 실행되는 여러 흐름의 단위

  • 프로세스의 특정한 수행경로

  • 프로세스가 할당받은 자원을 이용하는 실행의 단위, CPU 이용의 기본 단위

  • 프로세스 내의 주소 공간이나 자원을 공유

  • 스레드 ID, 프로그램 카운터(PC), 레지스터 집합, 스택으로 구성

  • 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 열린 파일이나 신호와 같은 운영체제 자원을 공유

  • 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상하는 것 => 멀티스레딩

  • 각각의 스레드는 독립적인 작업을 수행해야 하기 때문에 각각의 스택과 PC 레지스터를 가짐

  
  

• 특징

  • 스레드는 프로세스 내에서 각각 Stack과 레지스터를 따로 할당받고 Code, Data, Heap 영역은 공유

  • 한 스레드가 프로세스 자원을 변경하면, 다른 이웃 스레드(Sibling Thread)도 그 변경 결과를 즉시 확인 가능

• 분류 : 권한이 없는 스레드가 시스템 호출을 이용할 수 없도록 막기 위해 종류를 나눔

  • 사용자 수준의 스레드 (User Threads)

      - 사용자가 만든 라이브러리를 사용하여 스레드를 운용
    - 속도는 빠르지만 구현이 어려움
    - 시스템 호출 권한이 없는 스레드
    <br>

• 커널 수준의 스레드 (Kernel Threads)

   - 운영체제 커널에 의해 스레드를 운용
   - 구현은 쉽지만 유저 모드에서 커널 모드로 계속 바꿔줘야 하기 때문에 속도가 느림
   - 시스템 호출 권한이 있는 스레드

_ 스택을 스레드마다 독립적으로 할당하는 이유?_ : 스택은 함수 호출 시 전달되는 인자, 되돌아갈 주소 값 및 함수 내에서 선언하는 변수등을 저장하기 위해 사용되는 메모리 공간. 스택 메모리 공간이 독립적이라는 것은 독립적인 함수 호출이 가능하다는 것 => 독립적인 실행 흐름의 추가

_ PC 레지스터를 스레드마다 독립적으로 할당하는 이유?_ : PC 값은 스레드가 명령어의 어디까지 수행했는지를 나타낸다. 스레드는 CPU를 할당 받았다가 스케줄러에 의해 다시 선점 당하는데, 이 때문에 명령어가 연속적으로 수행되지 못하고 어느 부분까지 수행됐는지 기록을 해야한다.

• 스레드 풀(Thread Pools) : 웹 서버는 요청을 받을 때마다 요청을 위해 새로운 스레드를 생성

  • 프로세스를 시작할 때, 일정한 수의 스레드를 미리 풀로 만들어 두는 것

  • 평소에는 기다리다가 요청이 들어오면 풀의 한 스레드에게 서비스 요청을 할당

  • 요청이 끝나면 스레드는 다시 풀로 돌아가 다음 작업을 대기

• 다중 스레드 서버의 문제점

  1) 서비스 할 때마다 스레드를 생성하는데 시간이 소요

  • 스레드는 주어진 일만 끝나게 되면 곧장 폐기되기 때문에 더더욱 낭비

  2) 모든 요청마다 새로운 스레드를 만들어 서비스를 한다면 동시에 실행할 수 있는 최대 스레드의 한계를 정해야함

  • 무한정 생성 시 CPU 시간, 메모리 공간 등 시스템 자원이 고갈

• 장점

  • 새 스레드를 만들어 주는 것 보다 기존 스레드로 서비스 하는 것이 더 빠름

  • 스레드 풀은 임의 시각에 존재할 수 있는 스레드 개수에 제한. 많은 수의 스레드를 병렬 처리 할 수 없는 시스템에 도움

_ 왜 멀티 프로세스 대신 멀티 스레드를 사용할까?_ : 프로그램을 여러 개 켜는 것보다 하나의 프로그램에서 여러 작업을 하는 것

1. 응답성(Responsiveness) 증가

• 프로그램 일부분이 봉쇄되거나, 긴 작업을 실행하더라도 프로그램의 실행이 계속되는 것을 허용함으로써 사용자에 대한 응답성을 증가.

• ex) 웹 브라우저는 한 스레드가 이미지 파일을 로드하고 있는 동안 다른 스레드에서 사용자와의 상호작용

2. 자원 공유(Resource Sharing) : 자원의 효율성 증가

• 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리 가능

  • 프로세스 간의 Context Switching시 단순히 CPU 레지스터만 교체하는 것이 아니라 RAM과 CPU 사이의 캐시 메모리에 대한 데이터까지 초기화 하기 때문에 오버헤드가 큼

• 스레드는 프로세스 내의 메모리를 공유하기 때문에 독립적인 프로세스와 달리 스레드 간의 데이터를 주고 받는 것이 간단해지고 시스템 자원 소모가 감소

• 코드와 데이터를 공유하면 한 응용 프로그램이 같은 주소 공간 내에 여러 개의 다른 작업을 하는 스레드 보유 가능

3. 경제성(Economy) : 처리 비용 감소

• 프로세스 간의 통신(IPC)보다 스레드 간의 통신 비용이 적어 작업들 간의 통신 부담이 감소

  • 스레드는 Stack영역을 제외한 모든 메모리 공유

• 프로세스 생성을 위해 메모리와 자원을 할당하는 것보다 스레드를 생성하고 문맥 교환을 하는 것이 더 경제적

• 프로세스 간의 전환 속도보다 스레드 간의 전환 속도가 더 빠름

  • Context Switching 시 스레드는 Stack 영역만 처리해주면 됨. 캐시 메모리를 비우지 않아도 됨.

• 스레드가 프로세스보다 경량이기 때문에 생성과 제거가 쉽다.

4. 규모 가변성(Scalability)

• 다중 처리기 구조에서는 각각의 스레드가 다른 처리기에서 병렬로 실행 가능

_ 멀티 스레드에서 주의할 점_

1. 동기화 문제

   • 스레드 간의 자원 공유는 전역 변수(데이터 세그먼트)를 이용하므로 함께 사용시 충돌 발생 가능

   • 사용중인 변수나 자료구조에 접근하여 잘못된 값을 읽어오거나 수정할 수 있다.

   • 동기화를 통해 작업 처리 순서를 컨트롤하고 공유 자원에 대한 접근을 컨트롤 해야함

     • 그러나 병목 현상이 발생해 성능 저하 가능성

2. 멀티 스레드는 적은 공간을 차지하고 Context Switching이 빠르다는 장점을 가지고 있지만 오류로 인해 하나의 스레드가 종료될 때 전체 스레드가 종료될 수 있다.

Context Switching

• Context : CPU가 해당 프로세스를 실행하기 위한 해당 프로세스들의 정보

  • 프로세스의 PCB에 저장한다
  
  

• Context Switching : 현재 진행하고 있는 Task(Process, Thread)의 상태를 저장하고 다음 진행할 상태의 Task의 저장된 상태 값을 읽어 복구하는 작업

  • Context Switching이 진행되는 동안 시스템은 아무런 유용한 일도 하지 못하기 때문에 순수한 오버헤드

_ Context Switching을 하는 이유_

• 하나의 Task만 처리할 수 있다면?

  • 해당 Task가 끝날 때 까지 기다려야 함
  • 반응 속도가 느리고 사용하기 불편함

• 동시에 사용하는 것 처럼 하기 위해

  • Computer Multitasking
  • 빠른 속도로 Task를 바꿔가며 실행하기 때문에 사람의 눈으로는 실시간처럼 보임
  • CPU가 Task를 바꿔가며 실행하기 위해 Context Switching이 필요

• Context Switching 과정

1. Task의 대부분 정보는 Register에 저장되고 PCB(Process Control Block)로 관리

2. 현재 실행되고 있는 Task의 PCB 정보를 저장(Process Stack, Ready Queue)

3. 다음 실행할 Task의 PCB 정보를 읽어 Register에 적재하고 CPU가 이전에 진행했던 과정을 연속적으로 수행

   
   - Context Switching Cost - 많은 cost가 필요 - Cache 초기화 - Memory Mapping 초기화 - Kernel은 항상 실행되어야 함 (메모리의 접근을 막기 위해)
   

   • Process VS Thread

     • Process Context Switching Cost > Thread Context Switching Cost

     • Thread는 Stack 영역을 제외한 모든 메모리를 공유하기 때문에 Context Switching 수행 시 Stack 영역만 변경하면 되기 때문에 비용이 적다.

• Thread-Safe : 멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것

• 구현하기

  • 공유 자원에 접근하는 임계 영역(Critical Section)을 동기화 기법으로 제어해야 한다.

    • 상호 배제(Mutual Exclusion)

  • 동기화 기법으로는 Mutex나 Semaphore가 존재

• ReEntrant : 재진입성, 여러 스레드가 동시에 접근해도 언제나 같은 실행 결과를 보장하는 것 이를 만족하기 위해 해당 서브루틴에서 공유 자원을 사용하지 않으면 된다.

  • 예를 들어 정적(전역)변수를 사용하거나 반환하면 안되고 호출 시 제공된 매개 변수만으로 동작해야함.

    => 따라서 ReEntrant하면 Thread-Safe하지만 역은 성립되지 않는다.

• 동기화 기법의 종류

1. 유저 모드 동기화

   • 커널의 힘을 빌리지 않는 (커널 모드가 실행되지 않는) 동기화 기법

   • 성능상 이점, 기능상의 제한

   • ex) 크리티컬 섹션 기반의 동기화, 인터락 함수 기반의 동기화

   
   

2. 커널 모드 동기화

   • 커널에서 제공하는 동기화 기능을 활용하는 방법

   • 커널 모드로의 변경이 필요 -> 성능 저하

   • 다양한 기능 활용 가능

   • ex) 뮤텍스 기반의 동기화, 세마포어 기반의 동기화, 이벤트 기반의 동기화

프로세스 동기화

• 경쟁상황(Race Condition) : 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황

• 임계 영역(Critical Section) : 동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역

• 임계 영역 문제(Critical Section Problem) : 프로세스들이 Critical Section을 함께 사용할 수 있는 프로토콜을 설계하는 것

• 해결을 위한 기본 조건

  • Mutual Exclusion(상호배제) : 프로세스 1이 임계 영역에서 실행중이라면 다른 프로세스들은 그들이 가진 임계 영역에서 실행될 수 X

  • Progress(진행) : 임계 영역에서 실행 중인 프로세스가 없고 별도의 동작이 없는 프로세스들만 임계 영역 후보로서 참여 가능

  • Bounded Waiting(한정된 대기) : 프로세스 1이 임계 영역 진입 신청 후 받아들여질 때까지 다른 프로세스들이 임계 영역에 진입하는 횟수는 제한이 있어야함

  
  

• 해결책

  • 뮤텍스(Mutex)

    • 공유된 자원의 데이터를 여러 프로세스나 스레드가 접근하는 것을 막는 것

    • 상호 배제(Mutual Exclusion)라고도 함

    • Critical Section을 가진 스레드의 Running Time이 겹치지 않도록 각각 단독으로 실행하게 하는 기술

    • 다중 프로세스들이 공유 리소스에 대한 접근을 조율하기 위해 Syncronized 또는 lock을 사용

      • 즉, 뮤텍스 객체를 두 스레드가 동시에 사용 불가

  • 세마포어(Semaphore)

    • 공유된 자원의 데이터를 여러 프로세스나 스레드가 접근하는 것을 막는 것

    • 리소스 상태를 나타내는 간단한 카운터로 생각

      • 운영체제 또는 커널의 한 지정된 저장장치 내의 값

      • 일반적으로 비교적 긴 시간을 확보하려는 리소스에 사용

      • 유닉스 시스템 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에 행동을 조정하거나 동기화 시키는 기술

    • 공유 리소스에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근하여 사용 가능

    • 각 프로세스는 세마포어 값을 확인하고 변경 가능

      • 사용중이지 않은 자원의 경우 그 프로세스가 즉시 자원을 사용

      • 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면 재시도하기 전에 일정 시간을 대기

      • 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 함.

      • 세마포어는 2진수를 사용하거나 추가적인 값을 가질 수 있음

      • 카운팅 세마포어 : 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용, 세마포어는 가용한 자원의 개수로 초기화. 자원을 사용하면 감소, 방출하면 증가

      • 이진 세마포어 : Mutex 라고도 부르며 상호 배제의 머리 글자를 따서 만들어짐. 이름 그대로 0과 1 사이의 값만 가능하며 다중 프로세스들 사이의 임계 영역 문제를 해결하기 위해 사용

  
  - 세마포어와 뮤텍스의 차이 - 가장 큰 차이는 관리하는 동기화 대상의 개수

  - Mutex는 동기화 대상이 오직 하나일 때, Semaphore는 동기화 대상이 하나 이상일 때 사용

  • Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없음

    • Mutex는 상태가 0, 1 두 개 뿐인 Binary semaphore

  • Semaphore는 소유할 수 없는 반면, Mutex는 소유 가능. 소유주가 이에 대한 책임을 가짐

    • Mutex의 경우 상태가 두 개 뿐인 lock 이므로 lock을 가질 수 있음

  • Mutex의 경우 Mutex를 소유하고 있는 thread가 Mutex를 해제 할 수 있지만 Semaphore는 Semaphore를 소유하지 않는 스레드가 해제 가능

  • Semaphore는 시스템 범위에 걸쳐 있고 파일 시스템 상의 형태로 존재하지만 Mutex는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 Clean up

<br>

교착상태의 개념과 조건

• 교착상태 (Deadlock) : 첫 번째 스레드는 두 번째 스레드가 들고 있는 객체의 락이 풀리기를 기다리고 있고, 두 번째 스레드 역시 첫 번째 스레드가 들고 있는 객체의 락이 풀리기를 기다리는 상황 모든 스레드가 락이 풀리기를 기다리고 있기 때문에 무한 대기 상태 => 교착상태

• 교착상태의 4가지 조건

  1. 상호 배제 (Mutual Exclusion)

  • 한 번에 한 프로세스만 공유 자원을 사용

  • 좀 더 정확하게는 공유 자원에 대한 접근이 제한

  • 자원의 양이 제한되어 있더라도 교착상태는 발생 가능

  2. 점유대기 (Hold and Wait)

  • 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구 가능

  3. 비선점 (Preemtive)

  • 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소 불가능

  4. 순환대기(Circular wait)

  • 두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클이 존재

=> 4가지 조건을 다 만족해야 교착상태

문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.

  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.

• 물에 잠긴 지역은 0개 이상 10개 이하입니다.

• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

#include <string>
#include <vector>

using namespace std;

int dp[101][101] = {0};

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    dp[1][1] = 1;

    for(int i=0; i<puddles.size(); i++)
    {
        dp[puddles[i][0]][puddles[i][1]] = -1;
    }

    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            int x = 0;
            int y = 0;

            if(dp[i][j] == -1)
                continue;

            if(dp[i-1][j] != -1)
                x = dp[i-1][j];

            if(dp[i][j-1] != -1)
                y = dp[i][j-1];

            dp[i][j] += (x+y) %1000000007;
        }
    }
    answer = dp[m][n];

    return answer;
}

참조 : https://ongveloper.tistory.com/84

문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

• 각 숫자는 1 이상 50 이하인 자연수입니다.

• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int sum, int index)
{
    if(index == numbers.size())
    {
        if(sum == target)
            answer++;

        return;
    }

    dfs(numbers, target, sum+numbers[index], index+1);
    dfs(numbers, target, sum-numbers[index], index+1);
}

int solution(vector<int> numbers, int target) {

    dfs(numbers, target, 0, 0);

    return answer;
}

문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool is_prime(int num)
{
    if(num==1 || num==0)
        return false;

    for(int i=2; i*i <= num; i++)
        if(num%i ==0)
            return false;

    return true;
}

int solution(string numbers) {
    vector<char> num;
    vector<int> temp;

    for (int i = 0; i<numbers.size(); i++)
    {
        num.push_back(numbers[i]);
    }

    sort(num.begin(), num.end());

    do
    {
        string str = "";
        for (int i = 0; i<num.size(); i++)
        {
            str += num[i];
            temp.push_back(stoi(str));
        }
    } while (next_permutation(num.begin(), num.end()));

    sort(temp.begin(), temp.end());

    temp.erase(unique(temp.begin(), temp.end()), temp.end()); 
    //중복제거

    int answer = 0;
    for (auto x : temp)
    {
        if (is_prime(x))
        {
            answer++;
        }
    }

    return answer;
}

문제

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 시험은 최대 10,000 문제로 구성되어있습니다.

• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.

• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;

    vector<int> number_one = {1,2,3,4,5};
    vector<int> number_two = {2,1,2,3,2,4,2,5};
    vector<int> number_three = {3,3,1,1,2,2,4,4,5,5};

    vector<int> vec(3);

    for(int i=0; i<answers.size(); i++)
    {
        if(answers[i] == number_one[i%number_one.size()])
            vec[0]++;
        if(answers[i] == number_two[i%number_two.size()])
            vec[1]++;
        if(answers[i] == number_three[i%number_three.size()])
            vec[2]++;
    }

    int max_ = *max_element(vec.begin(), vec.end());
    for(int i=0; i<3; i++)
        if(vec[i] == max_)
            answer.push_back(i+1);

    return answer;
}

문제

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.

• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;

    sort(citations.begin(), citations.end(), greater<>());

    for(int i=0; i<citations.size(); i++)
    {
        if(citations[i] >= i+1)
        {
            answer = i+1;
        }
    }

    return answer;
}

문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

• prices의 길이는 2 이상 100,000 이하입니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());

    for(int i=0; i<prices.size(); i++)
        for(int j=i+1; j<prices.size(); j++)
        {
            answer[i]++;
            if(prices[i] > prices[j])
                break;
        }

    return answer;
}

문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.

• numbers의 원소는 0 이상 1,000 이하입니다.

• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(string a, string b)
{
    return a+b > b+a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> vec;

    for(int i=0; i<numbers.size(); i++)
        vec.push_back(to_string(numbers[i]));

    sort(vec.begin(), vec.end(), cmp);

    if(vec[0] == "0")
        return "0";

    for(auto x : vec)
        answer += x;

    return answer;
}

문제

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.

2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.

3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.

• array의 각 원소는 1 이상 100 이하입니다.

• commands의 길이는 1 이상 50 이하입니다.

• commands의 각 원소는 길이가 3입니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {

    vector<int> answer;

    for(int i=0; i<commands.size(); i++)
    {
        vector<int> temp;
        for(int j = commands[i][0] -1; j< commands[i][1]; j++)
        {
            temp.push_back(array[j]);
        }

        sort(temp.begin(), temp.end());

        answer.push_back(temp[commands[i][2] -1]);
    }

    return answer;
}

문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한사항

• bridge_length는 1 이상 10,000 이하입니다.

• weight는 1 이상 10,000 이하입니다.

• truck_weights의 길이는 1 이상 10,000 이하입니다.

• 모든 트럭의 무게는 1 이상 weight 이하입니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int index =0;
    int sum_weight =0;

    queue<int> Q; //다리 위에 있는 트럭

    while(1)
    {
        if(index == truck_weights.size())
        {
            answer += bridge_length;
            break;
        }

        answer++;

        int tmp = truck_weights[index];

        //차가 다리를 다 건넜을 경우
        if(Q.size() == bridge_length)
        {
            sum_weight -= Q.front();
            Q.pop();
        }

        if(tmp + sum_weight <= weight)
        {
            sum_weight += tmp;
            Q.push(tmp);
            index++;
        }
        else
            Q.push(0); //다음 트럭이 다리에 올라가지 못한다면
                        // 0을 푸시해주어 시간+1
    }

    return answer;
}

while문 돌릴 때 시작을 어떻게 해야하는지에 너무 약한 것 같다... 구글링해서 풀었는데 while문 시작을 좀 더 고민해봐야겠다

문제

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.

3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.

• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.

• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

풀이1 (priority_queue 사용)

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    queue<pair<int, int>> Q; //pair로 저장할 큐
    priority_queue <int> p_Q; //우선순위로 저장하는 큐

    for(int i=0; i<priorities.size(); i++)
    {
        Q.push(make_pair(i, priorities[i]));
        p_Q.push(priorities[i]);
    }

    int index = 0; //출력 순서를 알기위한 변수
    while(!Q.empty())
    {
        int current_index = Q.front().first;
        int current_value = Q.front().second;
        Q.pop();

        if(current_value == p_Q.top())
        {
            p_Q.pop();
            index++;
            if(current_index == location)
            {
                answer = index;
                break;
            }
        }
        else
            Q.push(make_pair(current_index, current_value));
    }

    return answer;
}

처음에 priority 큐를 몰라서 헤메다가 다른 사람들 풀이를 보고 알았다,, 코드 짜는건 비슷했는데 while문안에만 조금 달랐던,,

+) priority Queue 사용안하려면 max_element 사용하면 된다고 한다. 해보기!

풀이2 (max_element사용)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    queue<int> Q; //priorities를 저장할 큐
    vector<int> sorted; //정렬된 큐 index 저장

    for(int i=0; i<priorities.size(); i++)
    {
        Q.push(i);
    }

    while(!Q.empty())
    {
        int index = Q.front();
        Q.pop();

        if(priorities[index] != *max_element(priorities.begin(), priorities.end()))
        {
            //max값이 아니라면 큐의 맨 뒤에 넣어주기
            Q.push(index);
        }
        else
        {
            //max값이 맞다면
            sorted.push_back(index);
            priorities[index] = 0; //비교되지 않게 0 넣어주기
        }

    }

    for(int i=0; i<sorted.size(); i++)
        if(location == sorted[i])
            answer = i+1; //index가 0부터 시작하므로 i+1

    return answer;
}

문제

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.

• 작업 진도는 100 미만의 자연수입니다.

• 작업 속도는 100 이하의 자연수입니다.

• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> Q;

    for(int i=0; i<progresses.size(); i++)
    {
        int days = 0;
        if((100 - progresses[i]) % speeds[i] == 0)
            Q.push((100 - progresses[i]) / speeds[i]);
        else
            Q.push(((100 - progresses[i]) / speeds[i]) + 1);

    }

    while(!Q.empty())
    {
        int count = 1;
        int current = Q.front();
        Q.pop();

        while(!Q.empty() && current >= Q.front())
        {
            Q.pop();
            count++;
        }
        answer.push_back(count);
    }

    return answer;
}

풀이2 (Queue 사용하지 않고 풀기)

이 풀이는 진짜 너무 똑똑한 것 같다.. vector.back() 하나 배워감니다,,

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

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

int main()
{
    //freopen("test.txt", "r", stdin);

    int N, M;
    cin >> N >> M;

    vector<string> vec_listen;
    vector<string> vec_result;

    for (int i = 0; i < N; i++)
    {
        string temp;
        cin >> temp;

        vec_listen.push_back(temp);
    }
    sort(vec_listen.begin(), vec_listen.end());

    for (int j = 0; j < M; j++)
    {
        string temp;
        cin >> temp;

        if (binary_search(vec_listen.begin(), vec_listen.end(), temp))
        {
            vec_result.push_back(temp);
        }
    }

    sort(vec_result.begin(), vec_result.end());

    cout << vec_result.size() << "\n";

    for (auto x : vec_result)
        cout << x << "\n";

    return 0;
}

이진탐색으로 같은 단어를 찾는 것이 핵심인듯,,

** hashmap과 hashtable 차이 정리하기