눈물보다 땀을

특징

- 벽이 중간 중간 끊어진 형태라면 길을 찾지 못한다.

- 오른손으로 오른쪽 벽을 짚으면서 길을 찾는다.

- 오른쪽에 짚히는 벽이 없다면 오른쪽으로 간다.

- 순환구조가 아니라면 사용 가능하다.

Flow

샘플 프로젝트

c++

c#

참고

DFS 

-

-

-

-

BFS

-

-

-

-

DFS vs BFS

- 

- 

- 

- 

구현해보기

c++

c#

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 유니티로 만드는 mmorpg 게임 개발 시리즈] part3 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

DFS 

개념

- 깊이 우선 탐색 (Depth First Search)

- 더 이상 정점을 찾지 못할 때까지 정점을 타고 들어가고, 더이상 찾을 정점이 없으면 이전 위치로 복귀해서 또다른 정점을 찾는다.

- 재귀로 구현 가능하다.

리스트를 이용한 구현

        List<int>[] nodes = new List<int>[]
        {
            new List<int>() { 1, 3},
            new List<int>() { 0, 2, 3},
            new List<int>() { 1 },
            new List<int>() { 0, 1},
            new List<int>() { 5 },
            new List<int>() { 4 },
        };

        bool[] visited = new bool[6];
       
        public void DFSByList(int now)
        {
            Console.WriteLine(now);
            visited[now] = true; // 1) 우선 now부터 방문하고.

            foreach (int next in nodes[now])   // 연결되어 있는 정점이 아니면 패스.
            {
                // 방문한 정점이면 패스.
                if (visited[next])
                {
                    continue;
                }

                DFSByList(next);
            }
        }

행렬을 이용한 구현

 		
        int[,] nodes = new int[6, 6]
        {
            {0, 1, 0, 1, 0, 0 },
            {1, 0, 1, 1, 0, 0 },
            {0, 1, 0, 0, 0, 0 },
            {1, 1, 0, 0, 0, 0 },
            {0, 0, 0, 0, 0, 1 },
            {0, 0, 0, 0, 1, 0 },
        };

        bool[] visited = new bool[6];
        // 1)우선 now 부터 방문하고
        // 2)now와 연결된 정점들을 하나씩 확인해서, 아직 미발견 상태라면 방문한다.
        public void DFSByMatrix(int now)
        {
            Console.WriteLine(now);
            visited[now] = true; // 1) 우선 now부터 방문하고.

            for(int next = 0; next < 6; next++)
            {
                // 연결되어 있는 정점이 아니면 패스.
                if(nodes[now, next] == 0)
                {
                    continue;
                }

                // 방문한 정점이면 패스.
                if(visited[next])
                {
                    continue;
                }

                DFSByMatrix(next);
            }
        }

구현시 주의할 점

- 정점이 모두 이어진 경우가 아니라면 dfs 탐색을 1회만으로 불가능 한 경우가 생긴다.

     
     	public void SearchAll()
        {
            visited = new bool[6];

            for(int now = 0; now < 6; now++)
            {
                if(visited[now] == false)
                {
                    DFSByMatrix(now);
                }
            }
        }

BFS

개념

- 너비 우선 탐색 (Breadth First Search)

- 연결된 정점 정보를 저장하고 저장된 순서대로 꺼내서 다음 탐색을 시작한다.

- 순서대로 정점 정보를 사용하기 때문에 queue가 사용된다.

- 주로 길찾기 알고리즘에 사용된다.

리스트를 이용한 구현

 class Graph
    {
        List<int>[] nodes = new List<int>[]
        {
            new List<int>() { 1, 3},
            new List<int>() { 0, 2, 3},
            new List<int>() { 1 },
            new List<int>() { 0, 1, 4},
            new List<int>() { 3, 5 },
            new List<int>() { 4 },
        };

        public void BFSByList(int start)
        {
            bool[] found = new bool[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while (q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                // 인접하지 않으면 패스.
                foreach (int next in nodes[now])
                {
                    // 이미 발견 했으면 스킵.
                    if (found[next])
                    {
                        continue;
                    }

                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }
    }

행렬을 이용한 구현

 class Graph
    {
        int[,] nodes = new int[6, 6]
        {
            {0, 1, 0, 1, 0, 0 },
            {1, 0, 1, 1, 0, 0 },
            {0, 1, 0, 0, 0, 0 },
            {1, 1, 0, 0, 1, 0 },
            {0, 0, 0, 1, 0, 1 },
            {0, 0, 0, 0, 1, 0 },
        };

        public void BFSByMatrix(int start)
        {
            bool[] found = new bool[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while(q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                for(int next = 0; next < 6; next++)
                {
                    // 인접하지 않으면 패스.
                    if(nodes[now, next] == 0)
                    {
                        continue;
                    }

                    // 이미 발견 했으면 스킵.
                    if(found[next])
                    {
                        continue;
                    }

                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }

        public void BFSByList(int start)
        {
            bool[] found = new bool[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;

            while (q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                // 인접하지 않으면 패스.
                foreach (int next in adj2[now])
                {
                    // 이미 발견 했으면 스킵.
                    if (found[next])
                    {
                        continue;
                    }

                    q.Enqueue(next);
                    found[next] = true;
                }
            }
        }
    }

DFS vs BFS

- dfs는 발견과 동시에 방문한다. 다른 루트에 의해서 발견되었다고 해도 내가 먼저 방문하면 장땡.

- bfs는 발견된 정보는 우선 queue에 저장하고 queue 정보를 토대로 순차적으로 방문한다.

logN

전제

- 이진트리의 탐색의 경우

- n : 전체 데이터 갯수

- x : 탐색 횟수(최악의 경우 특정 데이터를 찾기 위해 탐색해야 하는 횟수)

풀이

- The Binary Tree Algorithm

- The Sidewinder Algorithm

- Kruskal Algorithm

- Prim

정의

- 알고리즘의 효율을 표현하기 위한 기준

- 알고리즘의 시간 복잡도를 수치화 하기 위한 수단

계산 방법

- 수행 되는 연산(산술, 비교, 대입 등)의 갯수를 대략적으로 판단

- 가장 영향력이 큰 대표 항목만 남긴다 (ex n^2+1 -> n^2)

- 상수 무시 (ex 2n -> n)

읽는 법

EX) O(n^2)

- order of n 제곱

- 빅오 n 제곱

의의

- N^2

- NLogN (대부분의 정렬 알고리즘 NLogN의 시간 복잡도를 갖는다.)

- N

- LogN

- 1

문제

 We * love = CodelQ

 W = 7 e =4 l =3 o = 8 v =0 C =2 d =1 l =9 Q =6

 74*3804=281496

다음 식을 만족하는 숫자 대입 방법은 몇 가지 있는지 구해 보세요. (단 최상위 문자에 0은 들어가지 않고 다른 문자에는 다른 숫자가 대입됩니다)

READ + WRITE + TALK = SKILL

난이도

IQ 80

목표시간

20분

풀이(c#,VS)

1. 

-

문제정답(사용언어:python)

1.

#풀이1
from itertools import permutations

count =0;
for (r,e,a,d,w,i,t,l,k,s) in permutations(range(10)):
    if r==0 or w==0 or t==0 or s==0:
        continue

    read = r*1000 + e*100 + a*10 +d
    write = w*10000 + r*1000 +i*100 + t*10 + e
    talk = t*1000 + a*100 + l*10 + k
    skill = s*10000 + k*1000 +i*100 + l*10 + l
    if read+write+talk==skill:
        count +=1

print(count)

#풀이2    디버깅이 안된다.. 예제 소스(책 소스랑 좀 다르다) 찾아서 받아서 돌려봤는대도 안된다..
import re
from itertools import permutations
from collections import OrderedDict

count =0

for(e,a,d,t,k,l) in permutations(range(0,10),6):
    if ((a+t==8) or (a+t==9) or (a+t==10)) and\
       ((a+e==8) or (a+e==9) or (a+e==10)) and\
       ((d+e+k)%10==1) and\
       (((a+t+l)*10+d+e+k)%100==l*11):
       
        temp = [item for item in range(0,10) if item not in [k,e,d,l,t,a]]
        for(i,r,s,w) in permutations(temp,4):
            if((r!=0) and (w!=0) and (t!=0)) and\
                ((s==w+1)or(s==w+2)):
                   
                    read = r*1000 + e*100 + a*10 +d
                    write = w*10000 + r*1000 +i*100 + t*10 + e
                    talk = t*1000 + a*100 + l*10 + k
                    skill = s*10000 + k*1000 +i*100 + l*10 + l
                    print("{}+{}+{}={}".format(read,write,talk,skill))
                    if read+write+talk==skill:
                        print("d{}+{}+{}={}".format(read,write,talk,skill))
                        count +=1

print(count)

책 제목 그대로... 코딩 퍼즐? 같은 느낌이다.. 쓰기 위한 코드? 알고리즘이라기 보단 다양한 방법으로 끼워 맞추는 놀이같은 문제다.. ㅜㅜ...

문제

 제곱근을 소수로 나타내었을 때 0~9의 모든 숫자가 가장 빨리 나타나는 최소 정수를 구하시오. 단, 여기서는 양의 제곱근만을 대상으로 합니다. 정수 부분을 포함하는 경우와 소수 부분만 취하는 경우 각각에 대해 모두 구하시오.

난이도

IQ 85

목표시간

20분

풀이(c#,VS)

1. 

using System;
using System.Linq;

namespace _12_SquareRoot
{
    class Program
    {
        static void Main(string[] args)
        {

            //정수포함           
            int targetNum = 2;
            while (true)
            {
                string sTargetNum = Math.Sqrt(targetNum).ToString().Replace(".", "");
                Console.Write(targetNum + "/" + Math.Sqrt(targetNum) + "/" + sTargetNum);
                if (StringDuplicationDelete(sTargetNum).Length == 10)
                {
                    Console.WriteLine(targetNum);
                    break;
                }
                targetNum++;
            }

            //소수포함           
            //int targetNum = 2;
            //while (true)
            //{
            //    string sTargetNum = string.Empty;
            //    try
            //    {
            //        sTargetNum = Math.Sqrt(targetNum).ToString().Split('.')[1];
            //        Console.Write(targetNum +"/" + Math.Sqrt(targetNum) + "/"+ sTargetNum);
            //    }
            //    catch
            //    {
            //        //split 에러
            //    }

            //    if (StringDuplicationDelete(sTargetNum).Length == 10)
            //    {
            //        Console.WriteLine(targetNum);
            //        break;
            //    }
            //    targetNum++;
            //}
        }

        public static string StringDuplicationDelete(string target)
        {
            string newString = string.Empty;

            for (int i=0; i< target.Length; i++)
            {
                if (!newString.Contains(target[i]))
                {
                    newString += target[i];
                }
               
            }

            Console.WriteLine(" /  " + newString);
            return newString;
        }
    }
}

문제정답(사용언어:python)

1.

from math import sqrt

# 정수 부분을 포함하는 경우
i =1
while True:
     i +=1
     # 소수점을 제거하고 왼쪽 10문자 추출
     string = '{:10.10f}'.format(sqrt(i)).replace('.','')[0:10]
     # 중복을 제거해서 10문자라면 종료
     if len(set(string)) == 10 :   
         break

print(i)

# 소수 부분만 계산하는 경우
i =1
while True:
     i +=1
     # 소수점을 분할하여 소수 부분만을 취득
     string = '{:10.10f}'.format(sqrt(i)).split('.')[1]
     # 중복을 제거해서 10문자라면 종료
     if len(set(string)) == 10 :
         break

print(i)

-