오늘 배운 내용
-
4주차 과제 - 텍스트 RPG 만들기
-
5주차 - 그래프 만들기
-
5주차 - 그래프 완전 탐색 DFS
-
5주차 - 그래프 완전 탐색 BFS
-
5주차 - 최단 경로 탐색 알고리즘
-
동적 프로그래밍 DP
-
분할정복 , DP와의 차이점
-
5주차 - leetcode 84. Largest Rectangle in Histogram
텍스트 RPG 만들기
public class Program
{
interface ICharacter
{
public string Name { get; set; }
public int Health { get; set; }
public int Attack { get; set; }
public bool IsDead { get; set; }
public void TakeDamage(int damage);
}
class Warrior : ICharacter
{
public string Name { get; set; }
public int Health { get; set; }
public int Attack { get; set; }
public bool IsDead { get; set; }
public bool HasItem()
{
if (Inventory.Count > 0)
{
return true;
}
return false;
}
public List<Iitem> Inventory = new List<Iitem>();
public void PickUpItem(Iitem _item)
{
Inventory.Add(_item);
Console.WriteLine($"{_item.Name}을 주웠습니다.");
}
public void UseItem()
{
if (HasItem())
{
Iitem item = Inventory[0];
item.Use(this);
Inventory.RemoveAt(0);
return;
}
Console.WriteLine("아이템이 없습니다.");
}
public void TakeDamage(int damage)
{
Console.WriteLine($"{Name} 가 {damage}의 피해를 받았습니다.");
Health -= damage;
if (Health < 0)
{
IsDead = true;
Console.WriteLine($"{Name}이 체력이 0이 되어 쓰러졌습니다.");
}
Console.WriteLine();
}
}
class Monster : ICharacter
{
public string Name { get; set; }
public int Health { get; set; }
public int Attack { get; set; }
public bool IsDead { get; set; }
public void TakeDamage(int damage)
{
Console.WriteLine($"{Name} 가 {damage}의 피해를 받았습니다.");
Health -= damage;
if (Health < 0)
{
IsDead = true;
Console.WriteLine($"{Name}이 체력이 0이 되어 쓰러졌습니다.");
}
Console.WriteLine();
}
}
class Goblin : Monster
{
public Goblin(int level)
{
switch (level)
{
case 1:
Name = "Goblin Lv1";
Health = 21;
Attack = 20;
IsDead = false;
break;
case 2:
Name = "Goblin Lv2";
Health = 42;
Attack = 25;
IsDead = false;
break;
case 3:
Name = "Goblin Lv3";
Health = 42;
Attack = 25;
IsDead = false;
break;
default:
break;
}
Console.WriteLine($"{Name} 가 출현했습니다.");
Console.WriteLine();
}
}
class Dragon : Monster
{
public Dragon()
{
Name = "Boss Dragon";
Health = 200;
Attack = 50;
IsDead = false;
Console.WriteLine($"{Name} 가 출현했습니다.");
Console.WriteLine();
}
}
interface Iitem
{
public string Name { get; set; }
public void Use(Warrior warrior);
}
class HealthPotion : Iitem
{
public string Name { get; set; }
public void Use(Warrior warrior)
{
warrior.Health += 100;
}
}
class StrengthPotion : Iitem
{
public string Name { get; set; }
public void Use(Warrior warrior)
{
warrior.Attack += 10;
Console.WriteLine("공격력 증가 포션이 사용되어 플레이어의 공격력이 10 증가 했습니다.");
}
}
class Stage
{
Warrior player;
Monster monster = new Monster();
bool isPlayerTurn = true;
public bool Start(Warrior _player, int level)
{
player = _player;
isPlayerTurn = true;
Console.WriteLine();
Console.WriteLine($"플레이어 {player.Name}이 {level} 스테이지에 입장합니다.");
Thread.Sleep(500);
Console.WriteLine();
// 스테이지 레벨에 알맞는 몬스터 등장
monster = level < 4 ? new Goblin(level) : new Dragon();
Thread.Sleep(500);
// 둘중 하나가 죽으면 스테이지가 종료
while (!player.IsDead && !monster.IsDead)
{
Console.WriteLine($"플레이어 {player.Name}의 정보 - 남은체력 : {player.Health}, 공격력 : {player.Attack}, 남은 포션 : {player.Inventory.Count}개");
Console.WriteLine($"{monster.Name}의 정보 - 남은체력 : {monster.Health}, 공격력 : {monster.Attack}");
Thread.Sleep(1000);
Console.WriteLine();
// 턴 전투 시작 isPlayerTurn에 따라서 턴이 진행된다.
if (isPlayerTurn)
{
PlayerTurn();
}
else
{
MonsterTurn();
}
Thread.Sleep(1000);
}
// 만약 플레이어가 살아남았다면 보상타임
if (player.IsDead)
{
return false;
}
else
{
Console.WriteLine($"{level} 스테이지 클리어!");
RewardPhase();
return true;
}
Console.WriteLine();
}
void PlayerTurn()
{
Console.WriteLine("플레이어의 턴 입니다.");
Console.WriteLine();
Console.WriteLine("1. 공격한다.");
Console.WriteLine();
// 포션이 없다면 뜨지않는다.
if (player.HasItem())
{
Console.WriteLine("2. 포션을 사용한다");
Console.WriteLine();
}
ConsoleKey Input = Console.ReadKey().Key;
// 키 입력
// 아이템이 없는데 D1를 누르면 통과
// 아이템이 있을때 D1,D2를 눌렀다면 통과
while (player.HasItem() && Input != ConsoleKey.D1 && Input != ConsoleKey.D2 || !player.HasItem() &&Input != ConsoleKey.D1 )
{
Input = Console.ReadKey().Key;
}
Console.WriteLine();
if (Input == ConsoleKey.D1)
{
Console.WriteLine($"{player.Name}의 공격!");
monster.TakeDamage(player.Attack);
//플레이어가 몬스터를 공격
}
else
{
player.UseItem();
//플레이어가 인벤토리에서 포션을 사용
}
isPlayerTurn = false;
}
void MonsterTurn()
{
Console.WriteLine($"{monster.Name}의 공격!");
player.TakeDamage(monster.Attack);
isPlayerTurn = true;
}
void RewardPhase()
{
Console.WriteLine("보상 페이즈 입니다. 보상을 선택해 주세요");
Console.WriteLine();
Console.WriteLine("1. 체력 회복 포션");
Console.WriteLine("2. 공격력 증가");
ConsoleKey Input = Console.ReadKey().Key;
// 키 입력
while (Input != ConsoleKey.D1 && Input != ConsoleKey.D2)
{
Input = Console.ReadKey().Key;
}
Console.WriteLine();
if (Input == ConsoleKey.D1)
{
HealthPotion healthPotion = new HealthPotion();
player.PickUpItem(healthPotion);
}
else
{
StrengthPotion strengthPotion = new StrengthPotion();
strengthPotion.Use(player);
}
}
}
static void Main(string[] args)
{
int stageLevel = 1;
Console.WriteLine("Enter 키를 누르면 게임이 시작됩니다.");
while (Console.ReadKey().Key != ConsoleKey.Enter)
{
Console.Clear();
Console.WriteLine("Enter 키를 누르면 게임이 시작됩니다.");
}
// 플레이어 객체를 생성
Console.WriteLine("플레이어의 이름을 입력해주세요.");
Console.WriteLine();
Warrior player = new Warrior(){ Name = Console.ReadLine(), Health = 100, Attack = 20, IsDead = false };
// 스테이지 객체를 생성
Stage stage = new Stage();
while (!player.IsDead)
{
Console.WriteLine();
Console.WriteLine($"현재 입장할 수 있는 스테이지 레벨은 {stageLevel}까지 입니다.");
Thread.Sleep(500);
Console.WriteLine("입장하시려는 스테이지를 입력해 주세요.");
int wantedStage;
// while 문을 false로 만들어야 진행되는데
// && 는 false가 하나라도 있으면 false가 된다.
//
while (!int.TryParse(Console.ReadLine(), out wantedStage) || wantedStage <= 0 || wantedStage > stageLevel)
{
Console.WriteLine("입력이 잘못되었습니다.");
Thread.Sleep(500);
Console.WriteLine("입장하시려는 스테이지를 입력해 주세요.");
}
// 스테이지 객체의 Start() 메서드 실행 == 플레이어 객체가 스테이지에 입장
if (stage.Start(player, wantedStage))
{
if (wantedStage == stageLevel)
{
stageLevel++;
}
if (stageLevel > 4)
{
Console.WriteLine("축하합니다 Boss 스테이지를 클리어 하셨습니다! 게임이 종료됩니다.");
break;
}
}
else
{
Console.WriteLine("플레이어가 몬스터에게 살해당했습니다. 게임이 종료됩니다.");
player.IsDead = true;
Thread.Sleep(3000);
}
}
}
}
4주차 강의의 숙제로 텍스트 RPG를 만들게 되었다.
스테이지 객체에 플레이어 객체를 입장시켜서
스테이지를 클리어하면 지금까지 했던 스테이지 중 선택해서 다시 입장할 수 있도록 만들었다.
스테이지는 입력 받은 레벨에 따라서 몬스터의 능력치가 달라지고
스테이지를 클리어 하면 플레이어는 보상을 받을수 있다.
보스 스테이지를 클리어하면 게임이 클리어되서 종료되고,
플레이어가 사망한 경우에도 게임이 종료된다.
그래프 만들기
public class Graph
{
private int V;
private List<int>[] adj;
public Graph(int _v)
{
V = _v;
adj = new List<int>[V];
for (int i =0; i< V; i++)
{
adj[i] = new List<int>();
}
}
public void AddEdge(int v, int w)
{
adj[v].Add(w);
}
}
class Program
{
static void Main(string[] args)
{
Graph graph = new Graph(6);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 3);
graph.AddEdge(2, 4);
graph.AddEdge(3, 4);
graph.AddEdge(3, 5);
graph.AddEdge(4, 5);
}
}
이 코드에서는 그래프를 리스트 배열로 선언한다. (2차원 자료구조)
배열의 인덱스는 노드를 뜻하고 인덱스에 저장된 리스트는 해당 노드에서 연결된 간선들을 뜻한다.
각 리스트에 AddEdge() 메소드를 통해서 출발 노드와 도착 노드를 매개변수로 주어서 두 노드를 연결하는 간선을 생성한다.
그래프 완전 탐색 DFS
DFS는 깊이 우선 탐색으로 시작점의 간선중 하나를 가장 깊은 곳까지 탐색한 후 시작점의 다음 간선을 탐색하는 방식이다.
이미 탐색한 노드를 재 방문 하지 않기 위해서 배열을 통해 방문 여부를 검사한다.
public void DFS(int _v)
{
bool[] visited = new bool[V];// 각 노드의 방문여부를 판별할 배열
DFSUtil(_v, visited);
}
private void DFSUtil(int _v, bool[] _visited)
{
_visited[_v] = true; // 이번 노드를 방문했으므로 true로 처리
Console.Write($"{_v}");
foreach(int n in adj[_v])// 이번 노드의 간선들을 모두 방문
{
if (!_visited[n]) // 이미 방문한 노드는 재 방문 하지 않음
{
DFSUtil(n, _visited); // 연결된 간선을 통해 노드를 방문 - 재귀
}
}
}
위에서 만든 그래프를 탐색하는 DFS코드이다.
노드를 재귀형태로 방문하기 때문에 앞에 위치한 간선부터 차례로
가장 깊은 곳까지 탐색하게 된다.
그래프 완전 탐색 BFS
BFS는 너비 우선 탐색으로 현재 노드의 간선을 모두 탐색한후 다음 노드들을 큐에 추가해서 순차적으로 탐색한다.
결국은 현재 노드에서 가까운 노드부터 탐색하여, 같은 레벨에 있는 노드를 모두 탐색해야 다음 레벨로 넘어가는
공평?한 방법이다.
public void BFS(int _v)
{
bool[] visited = new bool[V];// 각 노드의 방문여부를 판별할 배열
Queue<int> queue = new Queue<int>(); // 순서를 저장할 Queue
visited[_v] = true;// 첫 노드를 Queue에 넣는다
queue.Enqueue(_v);
while(queue.Count > 0)
{
int n = queue.Dequeue();// queue에서 요소 하나를 뺀다.
Console.Write($"{n}");
foreach(int node in adj[n]) // 노드에서 연견될 간선을 모두 확인한다.
{
if (!visited[node])
{
queue.Enqueue(node); // 방문하지 않은 노드를 queue에 모두 넣는다.
visited[node] = true;
}
}
}
}
최단 경로 탐색 알고리즘 - 다익스트라 알고리즘
다익스트라 알고리즘은
그래프를 만들때 각 노드의 간선들의 길이(가중치)를 저장한다. (간선이 없다면 0이 된다)
그리고 방문 여부 배열과 함께 시작점에서 각 정점까지의 거리를 저장할 거리 배열도 선언하고 거리 배열은 쓰이지 않을 큰값으로 초기화 한다.
방문 하지 않은 정점들 중 최소 거리를 찾아서 방문하고 그 정점에서 인접한 정점들의 최단 거리를 업데이트 합니다.
최종적으로 거리 배열에는 시작점 부터 각 정점들 까지의 최단 거리가 저장됩니다.
다익스트라 알고리즘 이외에도 대표적인 최단 경로 탐색 알고리즘으로 벨만-포드 알고리즘, A* 알고리즘 등이 있습니다.
class DijkstraExample
{
static int V = 6; // 정점의 수
// 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘
static void Dijkstra(int[,] graph, int start)
{
int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열
bool[] visited = new bool[V]; // 방문 여부 배열
// 거리 배열 초기화
for (int i = 0; i < V; i++)
{
distance[i] = int.MaxValue;
}
distance[start] = 0; // 시작 정점의 거리는 0
// 모든 정점을 방문할 때까지 반복
for (int count = 0; count < V - 1; count++)
{
// 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
int minDistance = int.MaxValue;
int minIndex = -1;
for (int v = 0; v < V; v++)
{
if (!visited[v] && distance[v] <= minDistance)
{
minDistance = distance[v];
minIndex = v;
}
}
// 최소 거리를 가진 정점을 방문 처리
visited[minIndex] = true;
// 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
for (int v = 0; v < V; v++)
{
// 갈수 있는 정점중 && 현재 최단거리가 max가 아니고 && 다른 최소거리가 없는경우
if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
{
distance[v] = distance[minIndex] + graph[minIndex, v];
}
}
}
// 최단 경로 출력
Console.WriteLine("정점\t거리");
for (int i = 0; i < V; i++)
{
Console.WriteLine($"{i}\t{distance[i]}");
}
}
static void Main(string[] args)
{
int[,] graph = {
{ 0, 4, 0, 0, 0, 0 },
{ 4, 0, 8, 0, 0, 0 },
{ 0, 8, 0, 7, 0, 4 },
{ 0, 0, 7, 0, 9, 14 },
{ 0, 0, 0, 9, 0, 10 },
{ 0, 0, 4, 14, 10, 0 }
};
int start = 0; // 시작 정점
Dijkstra(graph, start);
}
}
다익스트라 알고리즘은 나중에 따로 구현해보고 정리해봐야겠다.
동적 프로그래밍
문제를 작은 단위로 쪼개서 반복하여 해결하는 방법
작은 단위의 문제의 해결을 저장하고 이를 반복해서 이용해 큰 문제를 해결한다 이 저장 방법을 메모이제이션 이라고 한다.
일반적으로 재귀적인 구조를 가지고 하향식, 상향식 두가지 방법으로 구현한다.
public int Fibonacci(int n)
{
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for(int i =2; i<=n; i++)
{
dp[i] = dp[n - 1] + dp[i - 2];
}
return dp[n];
}
대표적인 상향식 DP로는 피보나치 수열이 있다.
분할정복 , DP와의 차이점
분할 정복 또한 큰 문제를 작은 부분으로 분할하여 문제를 해결하는 방법이다.
대표적으로 퀵 정렬, 병합 정렬이 분할 정복에 해당된다.
분할 정복은 DP와는 다르게 문제들을 독립적으로 처리하고 DP는 작은 단위의 해결을 큰 문제의 해결에 사용한다는 점이 다르다고 한다.
물론 분할 정복도 메모이제이션을 사용해서 중복계산을 피하기도 하고, 필요한 상황에 맞게 활용하면 된다.
5주차 - leetcode 84번
public int LargestRectangleArea(int[] heights)
{
int left = 0;
int right = heights.Length - 1;
bool[,] visited = new bool[heights.Length, heights.Length];
int answer = 0;
Search(left, right, visited, heights, ref answer);
return answer;
}
public void Search(int left, int right, bool[,] visited, int[] heights, ref int answer)
{
visited[left, right] = true;
int min = int.MaxValue;
//범위 안에서 가장 큰 값과 가증 작은 값을 찾음
for (int i = left; i<= right; i++)
{
min = Math.Min(min, heights[i]);
}
answer = Math.Max(answer, min * (right - left +1));
if (left < right && visited[left+1, right])
{
Search(left + 1, right, visited, heights, ref answer);
}
if (right > left && visited[left, right-1])
{
Search(left, right - 1, visited, heights, ref answer);
}
}
87/98 에서 런타임 에러 out of memory.가 발생했다 Input 내용을 보니 heights[] 배열이 1로 가득 채워져 있었는데
아마도 heights의 최대 길이인 길이가 10000인 상황으로 visited 2차원 배열에 문제가 생기나? 싶어서.
이번에는 visited 배열을 삭제해 봤더니 똑같은 부분에서 이번에는 중복 계산 때문에 Time Limit Exceeded 문제가 발생했다.
그리고 재귀를 아예 없애고 반복문으로도 시도했지만 마찬가지로 시간초과 였다.
시간복잡도를 줄여야만 문제를 풀수있다고 생각해서 처음부터 다시 문제를 생각해봤다.
// 정수 값의 높이를 가진 히스토그램 바들이 있다.
// 여기서 가장큰 직사각형의 넓이를 구해라
// 가장 큰 직사각형이 생성되는 곳은 반드시 바들이 오름차순으로 정렬되어있지 않을까?
// 오름차순으로 정렬된 부분들만 잘라오자!
// 이제 각각 오름차순으로 정렬된 부분에서 가장 큰 직사각형을 구한다!.
// 1. 가장 앞의 원소 * 길이
// 2. 가장 마지막 원소
// 분할된 곳에서도 하나씩 빼면 더좋은 경우의 수가 나온다..
// 근데 분할된 곳은 정렬되어있기 때문에 앞에서 하나씩 없애가면서 보면됨
// 실패
public class Solution
{
public int LargestRectangleArea(int[] heights)
{
int answer = int.MinValue;
List<List<int>> listSplit = new List<List<int>>();
List<int> temp = new List<int>();
temp.Add(heights[0]);
int min = heights[0];
for (int i =1; i< heights.Length; i++)
{
min = Math.Min(min, heights[i]);
if (heights[i-1] <= heights[i])
{
temp.Add(heights[i]);
}
else
{
listSplit.Add(temp);
temp = new List<int>();
// temp리스트를 새로할당
temp.Add(heights[i]);
}
}
listSplit.Add(temp);
foreach(List<int> list in listSplit)
{
while(list.Count > 0)
{
answer = Math.Max(answer, list[0] * list.Count);
list.RemoveAt(0);
}
}
return Math.Max(answer, min * heights.Length);
}
}
다음 도전도 실패했다 오름차순인것 끼리 잘라서 해봤으나
내림차순이여도 크기가 큰것끼리 뭉쳐있으면 큰 직사각형이 될수 있다는 것을 깨달았다.
// 숫자중에 들어올수 있는거는 1~10000 이니까
// 숫자를 1부터 10000까지 키워가면서
// 최소값이 1이라면 전부다 이어져서 1*길이가 되곘지?
// 2라면 2이상인 부분만 이어져서 거기서 가장 긴길이 2* 길이
public class Solution
{
public int LargestRectangleArea(int[] heights)
{
int pivot = 0;
int answer = 0;
int max = 0;
foreach(int height in heights)
{
max = Math.Max(max, height);
}
// heights 배열에서 최대인 값을 선택
// 1~ 최대인 값 까지 하나씩 지워가면서
// 가장 긴 길이 * pivot
while (pivot++ < max)
{
int count = 0;
List<int> temp = new List<int>();
foreach (int height in heights)
{
if (height >= pivot)
{
temp.Add(height);
}
else
{
count = Math.Max(count, temp.Count);
temp = new List<int>();
}
}
count = Math.Max(count, temp.Count);
answer = Math.Max(answer, count * pivot);
}
return answer;
}
다음으로 시도했던 방법인데 횟수를 줄이기위해서
heights의 최대길이인 100,000에 비해 그래도 범위가 작은 height의 1~10000까지의 범위를 이용해 보는게 어떨까라는
생각이 들어서 밑에서부터 짧은 것을 하나씩 빼가면서 길이를 이어진 직사각형들의 길이를 재서 가장큰 직사각형을
찾아보려는 시도였다.
앞에서는 87/98 테스트 케이스에서 시간초과로 실패했는데 이번에는 90/ 98 까지는 올 수 있었지만
결국에는 시간 초과를 해결하지는 못했고, 튜터님에게 질문을 드려봤는데 자료구조를 활용하는 방법을 좀 더 생각해보라는 방향을 제시해 주셨고 내일 다시 생각해 보려고 한다.
