강의 정리
5주차
알고리즘
- 문제를 해결하기 위한 명확한 절차나 방법
- 입력을 받아 원하는 출력을 생성하기 위한 절차
- 입력, 출력, 명확한 단계, 실행 가능성의 특성
- 주어진 입력에 대해 정확하고 일관된 결과를 제공해야함
가능한 한 효율적인 알고리즘을 사용하는 것이 중요함.
- Big O 표기법 - 알고리즘 전투력 측정기
알고리즘의 효율성을 나타내는 표기법
최악의 경우 성능을 나타내므로 효율성을 과장하지 않음
표기법의 예
O(1) : 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간
O(n) : 선형 시간. 입력의 크기에 비례하여 시간이 걸림
O(n^2) : 이차 시간 . 크기의 제곱에 비례
O(log n) : 로그 시간. 크기의 로그에 비례
표기법 계산 (예시 노션 긁)
1. 상수 버리기
2. 최고 차수 항목만 남기기
3. 다항식의 경우 최고 차수 항목만 고려
4. 연산자 상수 무시
-
시간 복잡도
시간복잡도?
코드가 얼마나 빠르게 동작하냐 (입력에 따른 연산 횟수로 측정)
반복문 들어가있으면 n, 중첩이면 n^갯수만큼 -
공간 복잡도
? : 메모리를 측정
메모리 할당되는 부분들 생성되는 갯수만큼
원래 있던 거에서 안늘어나면 1
정렬 알고리즘
주어진 데이터 세트를 특정 순서로 배열하는 방법을 제공
퀵정렬 - 제일 대중적
피벗을 기준으로 작은 요소들을 왼쪽, 큰요소들을 오른쪽
정렬들 전반적으로 코드 보고 분석해보기.
실제로는 정렬 알고리즘을 쓰는 경우는 드물다
왜냐면 C#에서 Sort메서드를 제공함
Array.Sort(numbers);
탐색 알고리즘
이진 탐색 : 중간부터 시작해서 그 값이 더 작으면 왼쪽, 크면 오른쪽으로 찾음 //정렬된 배열에 쓰는 방법
그래프
정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
방향 그래프와 무방향 그래프로 나뉨.
그래프 탐색 방법
1. 깊이 우선 탐색 - 처음부터 해서 버텍스를 더 못만날떄까지 찾아가는거
2. 너비 우선 탐색 - 루트로 잡힌 버텍스부터 사용할수있는 엣지들을 다 체크한 이후에 그 다음에 만난 버텍스의 엣지들을 검색해나간다.
VISUALGO.net Cp3 4.17
한번식은 DFS BFS 해봐야됨. 많이 나오는 문제라고함. 깃에 올려놓음
최단 경로 알고리즘
개인별로 다익스트라 알고리즘을 브레이크포인트로 분석해봤으면 싶다고함
->해보고 정리
동적 프로그래밍
큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식
일반적으로 재귀적인 구조를 가지며, 하향식 / 상향식 두 가지 방법으로 구현
최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결
그리디 알고리즘
각 단계에서 가장 최적인 선택을 하는 알고리즘
지역적인 최적해를 찾는데 초첨을 맞추기 때문에 전체로 봤을때는 최적이 아닐 수 있다.
코드를 짤 때에는 일단 문제를 소분하는게 맞음
분할 정복
큰 문제를 작은 문제로 분할
재귀적인 구조
분할된 부분 문제들은 독립적으로 해결되므로 병렬 처리에 유리
문제를 분할할 때 발생하는 문제들 간의 중복계산이 발생할 수 있음 > 메모이제이션을 통해 성능 향상 가능
문제 해결 전략과 실전 연습
문제해결전략
- 문제 이해
- 예제와 테스트 케이스 - 꼭 문제를 풀 전에 전체적으로 검토
- 알고리즘 설계
- 코드 작성
- 효율성
- 디버깅과 테스트
- 시간 관리
- 연습과 경험
백준 온라인 저지, 프로그래머스, 바킹독, LeetCode
코딩 테스트나 알고리즘 문제의 종류
1.탐색과 정렬
2. 그래프
3. 동적 프로그래밍
4. 그리디 알고리즘
5. 분할 정복
6. 동적 그래프
7. 문자열 처리
8. 기타
Sort에 람다 쓰는거
jobs.Sort((x,y) => x.EndTime.CompareTo(y.EndTime));
x,y를 매개변수로 받아서 EndTime기준으로 정렬하는것
3주차 과제
- 하면서 어려웠던 점, 해결 방법만 기재
Snake game
먼저 혼자 풀기에 아이디어가 안 떠올라 풀이를 몇가지 참고 했음을 알리며, 참고한 부분에 대해 어떤 부분을 참고했고, 어떻게 고쳤는지 적음
Console.KeyAvailable (인터넷 참고)
키를 눌렀을 때 동작하는 것을 감지하기 위해
Console.ReadLine()을 스위치문에 넣어서 썼더니 일단 한번 눌러야 다음 동작이 수행되서 실패했다. 이래저래 검색하다보니 아예 키가 눌렸을 때 bool 값을 반환하는 함수가 있어서 사용했다.
Console.ReadKey(true)도 있는데, 이렇게 하면 키를 눌렀을 때 콘솔이 뜨지 않고 바로 넘어간다. 무슨 키를 눌렀는지 case로 받고싶다면
switch (Console.KeyAvailable)
{
case true:
switch (Console.ReadKey().Key)
{
case ConsoleKey.Enter: //Key뒤에 내가 입력받고싶은 버튼 이름을 넣는다.
break;
}
break;
}Move() (풀이 참고)
처음에는 for문을 뱀의 길이만큼 돌려서 Main()에서 계속 돌아가게끔 만들었는데,
풀이를 참고해보니 List로 List시작점을 꼬리, Last를 머리로 잡고 진행 방향에 맞게 머리의 다음 포지션을 생성해서, 그 위치에 머리 생성, 꼬리 제거 / 하는 방식으로 진행되었다.
이 다음 포지션을 잡고 이동하는 부분이 풀이에서는 2부분으로 나뉘어 있었는데, 하나로 합칠 수 있을 것 같아서 통합해서 진행했다. 그런데 다음 포지션 잡는 부분에서 세부적인 내용을 안보고
겉에 숫자 하나만 보고 진행했엇는데 콘솔창 특성상 수직, 수평 거리가 있어서 수평이동에는 2칸씩
수직 이동에는 1칸씩 해줘야되는데 다 2칸으로 해놔서 문제가 발생했다.
문제
- 음식을 못먹음
- 수직 수평 이동 속도가 다름.
해결
- 음식 문제 해결
이 문제를 해결하기 위해서는 뱀이 모든 칸을 다 다니거나, 음식이 뱀이 다닐 수 있는 칸만 나오거나 둘 중 하나다.
근데 뱀이 모든 칸을 다 다니는 것과 2번의 해결 방법은 상충한다.
왜냐하면 뱀의 수직 이동거리가 수평 이동거리의 두배정도 되기 때문이다.
그러면 음식이 뱀이 지나다닐 수 있는 칸에만 나오는게 제일 합리적이다.
그래서 음식을 생성할 때 위치의 제약을 걸어주었다.
- 음식 문제 해결
public Point CreateFood()
{
Random rand = new Random();
int xPos = 0;
int yPos = 0;
while (true)
{
xPos = rand.Next(1, mapWidth - 1);
yPos = rand.Next(1, mapHeight - 1);
if (xPos % 2 != 0)
break;
}
Point p = new Point(xPos, yPos, sym);
return p;
}수평으로 2칸씩 다니기 때문에 비워지는 부분이 있기때문에, 음식의 위치X값이 홀수일때만 값을 받아오기로 했다.
-2. 수직 수평 이동속도 맞추기
1번에서도 얘기했지만, 수평 속도를 높이면 된다. 이건 2:1 비율로 머리의 다음 지점을 바꾸면서 해결했다.
EatFood() (풀이 약간 참고)
몸이 뒤로 자라느냐, 앞으로 자라느냐라는 고민사항이 있었다.
이상적인 상황은 뒤로 자라는거 같은데, 막상 뒤로 자란다고 생각하니 고민할게 많아졌다.
뒤로 자라는 경우
뒤로 자라는 경우가 생각하기에는 제일 좋은 것 같은데, 코드 짜는 입장에서 생각해보니
뒤로 자랄때의 위치가 애매함.
- 뱀의 진행방향과 몸통이 직선일 때는 값의 추정이 가능하지만, 몸이 길어지면 꼬리가 어느 위치에 있을지, 꼬리에서 이어지는 방향은 어디가 좋을 지, 여기서 꼬리가 생성되면 몸과 부딪히지 않는지 등등 많은 문제가 떠올랐다.
그래서 뒤로 자라는 경우는 패스했다.
앞으로 자라는 경우
앞으로 자라는 경우에는 ------> $ 이런 느낌이라고 치면 먹었을 때 머리랑 생성될 방향이랑 같으니까 머리X값 +2를 해줬었다.
Point head = body.Last();
foodcount++;
Length++;
switch (direction)
{
case Direction.LEFT:
Point growLeft = new Point(head.x - 2, head.y, '*'); //이렇게하면 벽에있는걸 왼쪽방향으로 먹으면 뒤짐
body.Add(growLeft);
break;
case Direction.RIGHT:
Point growRight = new Point(head.x + 2, head.y, '*');
body.Add(growRight);
break;
case Direction.UP:
Point growUp = new Point(head.x, head.y - 1, '*');
body.Add(growUp);
break;
case Direction.DOWN:
Point growDown = new Point(head.x, head.y + 1, '*');
body.Add(growDown);
break;
}
이거 바꾸고나니까 음식먹으면 투명지렁이됨
food.claer가 원인이였ㄷ음대충 이런 코드인데, 이것도 문제가 발생했다.
문제 1. 벽에 박음
벽면에 있는 음식을 먹을 때, 벽면을 따라 올라가면 다음 포인트에 머리(뱀 몸통)이 생겨도 상관없지만, 벽면을 향해서 먹을 경우, 머리가 생성되면서 바로 갖다박고 게임이 끝난다.
그래서 잠시 풀이를 카카시했는데, 음식(Point class)를 바로 body에 집어넣으면 해결되는 일이였다. 이렇게 해도 body.Last()가 되면서 정상적으로 진행된다.
public void EatFood(Point food)
{
foodcount++;
Length++;
Point growup = food;
growup.sym = '*';
body.Add(growup);
}문제 2. 투명뱀이됨
이렇게 한건 좋은데, 자꾸 투명뱀이 됬었다. 이유는 간단했는데, 그 전에 쓰던 방식에서 사용되던
food.Clear();가 문제였다.
Point class의 Clear메소드인데
public void Clear()
{
sym = ' ';
Draw();
}그 위치를 공백으로 만드는 기능이다. 그래서 이게 왜 문제가 됬느냐,
Class = 참조 형태 => 값이 복사가 되는게 아니라 주소를 알려주는 것 / 근데 집이 공백이 되버렸다? 그래서 투명 지렁이가 되었다.
간단하게 지워주고 해결했다.
게임오버 구현하기
이 게임에서 게임오버 조건은 두 가지
- 벽에 박거나
- 몸에 박거나
벽에 박거나
구현하는데 고민을 더 한 파트인데, 처음에는 맵을 Point로 List<>에 다 넣어보려했다.
근데 map을 그릴 때 setcursor하고 그리는데 Point 형식으로 List에 어떻게 저장할 것이며,
벽에 박는 판단을 하기 위해서는 List를 다 뒤져야되는데
그러면 메모리가 낭비된다고 판단해서 폐기하고 심플하게 구현했다.
if (snake.body.Last().x <= 0 || snake.body.Last().y <= 0
|| snake.body.Last().x >= 79 || snake.body.Last().y >= 19)몸에 박거나
이미 List<>형식으로 되어있고, Point이기도 하고, 예제에 먼저 쥐어준 IsHit()라는 Method도 있어서 옳다구나 하고 넣었는데, 실제로 작동도 잘 됬었다. 근데 작동만 잘 되고 문제가 두개 정도 발생했다.
문제 1. 게임이 안끝나요.
for (int i = 0; i < snake.body.Count; i++)
{
if (snake.body.Last().IsHit(snake.body[i]))
{
Console.Clear();
Console.WriteLine($"먹은 음식 : {snake.foodcount}");
Console.WriteLine($"길이 : {snake.Length}");
Console.WriteLine("게임오버");
break;
}
}이게 작성한 지문인데, 지금은 눈에 확 보이는게 break;를 걸어줬다고 해서 전체 While(true)에서 빠져나가는게 아니다. 이 for문만 빠져나가는거라 게임이 안끝나고 Move()가 돌아갔던 거다.
그래서 snake에 IsAlive = true;를, While(snake.IsAlive)로 바꾼 후, 몸에 박았을 때 false가 되도록 해주었다.
문제 2. 음식 먹으면 죽어요 (풀이 참고)
위의 음식 먹는 부분에서 발생한 문제와 같은데, 고치기 전에는 벽에 박고, 고친 후에는 몸통에 박아 죽었다. 그래서 이유를 참고해보니, 머리 생성 = 음식 위치 인데 내 머리 값이 있는 부분에 머리가 새로 등장하니까 '몸이구나'하고 박고 죽는거였다.
for (int i = 0; i < snake.body.Count - 2; i++)그래서 이 구문은 Count-2를 해서, 새로생긴 머리위치, 그전 머리위치는 어차피 박지도 않을 뿐더러 위와 같은 문제가 발생하니 제외시켜주었다.
Map 그리기
테두리 그릴 때 이상한 문제가 발생했다. 똑같은 코드로 다른 프로젝트에서 진행할 때는 잘 그려지는데, 뱀 게임에서는 맨 윗줄 81칸, 맨 밑줄 80칸으로 어디서 한 개가 더 생기더라.
정확한 원인은 파악 못 했지만, 튜터님께 여쭤보기로는
'SetCursor를 하다보니 이리저리 튀어서 그렇다' 라는 얘기를 해주셨다.
그리고 기존에 그리던 방식에 대해서도 조언을 해주셨는데,
for (int j = 0; j < 2; j++) //벽 생성
{
for (int i = 1; i < mapWidth; i++)
{
if (j == 0)
{
Console.SetCursorPosition(i - 1, 0);
Console.Write('#'); //81개 나옴
}
else
{
Console.SetCursorPosition(i - 1, 19); //80개 나옴 뭔 오류지
Console.Write('#');
}
}
for (int i = 0; i < mapHeight; i++)
{
if (j == 0)
{
Console.SetCursorPosition(0, i);
Console.WriteLine('#'); //81개 나옴
}
else
{
Console.SetCursorPosition(79, i); //80개 나옴 뭔 오류지
Console.Write('#');
}
}
}이렇게 for문 안에 for문을 두개 더 써서, 총 3개의 for문을 돌렸는데, 이러면 알고리즘 상으로 좋지 않다고 하시며 새로운 방법을 제시해주셨다. 기본 틀을 주시고 내가 작성했다.
for (int i = 0; i < 20; i++) //높이 { for (int j = 0; j < 80; j++) //너비 { if (i == 0 || i == 19) { Console.SetCursorPosition(j, i); Console.Write("#"); } if (j == 0 || j == 79) { Console.SetCursorPosition(j, i); Console.Write("#"); } } }이렇게 하면 for문 두개에 조건 2개로 그릴 수 있다.
BlackJack game
룰을 정확하게 몰라서 찾아보고 만들었는데, 다 만들고 동작은 되는데
만들고 나니 부품이 남았다. 라는 느낌이다.
그래서 이 게임에 관한 포스팅은, 예시로 쥐어준 걸 뜯어먹어보자. = 길어질 예정
enum Suit, Rank
public enum Suit { Hearts, Diamonds, Clubs, Spades }
public enum Rank { Two = 2, Three, Four, Five, Six, Seven, Eight,
Nine, Ten, Jack, Queen, King, Ace }Rank는 Two = 2 로 지정해 줌으로서 뒤부터 차례대로 ++된다.
Card Class
public class Card
{
public Suit Suit { get; private set; }
public Rank Rank { get; private set; }
public Card(Suit s, Rank r)
{
Suit = s;
Rank = r;
}
public int GetValue()
{
if ((int)Rank <= 10)
{
return (int)Rank;
}
else if ((int)Rank <= 13) // 잭,퀸,킹은 10
{
return 10;
}
else //에이스는 11로 바뀐다.
{
return 11;
}
}
public override string ToString() //문양과 숫자를 반환
{
return $"{Rank} of {Suit}";
}
}개별 카드에 대한 Class로 카드별 Value와 문자열 반환을 담고있다.
Deck class
public class Deck
{
private List<Card> cards; //private로 선언되어있다 = 다른데서 접근 불가
public Deck()
{
cards = new List<Card>();
foreach (Suit s in Enum.GetValues(typeof(Suit))) //2중 foreach로 카드 한벌을 Deck에 넣는 작업.
{
foreach (Rank r in Enum.GetValues(typeof(Rank)))
{
cards.Add(new Card(s, r));
}
}
Shuffle();
}
public void Shuffle() //랜덤함수를 통해 랜덤한 위치의 값과 스왑하여 셔플됨.
{
Random rand = new Random();
for (int i = 0; i < cards.Count; i++)
{
int j = rand.Next(i, cards.Count);
Card temp = cards[i];
cards[i] = cards[j];
cards[j] = temp;
}
}
public Card DrawCard() //맨 첫장 카드를 뽑고, 그 카드를 지운다. 이렇게 할 경우 맨 앞이 비어서 자동으로 Cards리스트가 당겨진다.
{
Card card = cards[0];
cards.RemoveAt(0);
return card;
}
}덱에 카드를 채우고, 섞고, 카드를 뽑을 때 덱에서 일어나야 할 일들을 담고 있다.
Hand class
public class Hand
{
private List<Card> cards; //여기도 private - 외부 접근 불가.
public Hand()
{
cards = new List<Card>();
}
public void AddCard(Card card) //리스트에 카드를 추가함.
{
cards.Add(card);
}
public int GetTotalValue() //리스트에 있는 카드들의 Value 총합을 계산하는 함수
{
int total = 0;
int aceCount = 0; //에이스가 1 or 11 이라서
foreach (Card card in cards)
{
if (card.Rank == Rank.Ace)
{
aceCount++;
}
total += card.GetValue();
}
while (total > 21 && aceCount > 0) //ace카드를 11 > 1로 바꾸는 조건
{
total -= 10;
aceCount--;
}
return total;
}
}플레이어의 핸드 = 가지고 있는 카드들로 전체 Value 계산 및 반환, 손에 카드 추가 같은 기능을 가지고 있는 Class 이다.
Player Class
public class Player
{
public Hand Hand { get; private set; }
public Player()
{
Hand = new Hand();
}
public Card DrawCardFromDeck(Deck deck) //카드를 뽑고 손에 추가하는 작업.
{
Card drawnCard = deck.DrawCard();
Hand.AddCard(drawnCard);
return drawnCard;
}
}그 이후
밑으로는 학습자가 작성해야 되는 내용으로 Class에 넣은 내용과 Main()의 내용을 간단하게 알아보고 정리하려고한다.
밑으로 Dealer 클래스와 Blackjack 클래스가 있는데, 여기에 뭘 더 써야될지 모르겠다.
Main() 함수에 많이 적어넣었는데, 그냥 실행하고, 카드뽑고 그런것들이라 진행하면서
새로 배웠다고 느낀점들을 적어본다.
카드 문양, 숫자 호출하기
위에 보면 Hand의 Cards도 Private로 선언되어 있기때문에 내가 직접 호출할 수가 없다.
근데 Card를 호출 안하면? 문양도 숫자도 호출할 수 없다.
그럼 어떻게 하느냐, 힌트가 위에 있다.
Card class를 보면 Tostring() 함수가 override로 존재한다.
그리고 Deck Class DrawCard()에는 card를 반환하고,
Player Class에서 DrawCardFromDeck에는 Card drawnCard를 반환한다.
그렇다. 우리는 DrawCardFromDeck()을 호출하면 Tostring()의 값을 받을수 있다.
Console.ReadKey()
ReadLine과 다른점 : 버튼 하나만 눌러도 바로 입력이 들어감. (Line은 엔터누르기 전까지의 내용이 다 들어감
정리
오늘은 5주차까지 다 듣고 3주차 과제도 해봤는데 조금 흘깃흘깃 훔쳐보긴 했지만 재밌는 시간이였다.
내일 할일
- 4주차 5주차 과제 해보기
- 동기화 / 비동기화 공부해보기
