영리한 프로그래밍을 위한 알고리즘 강좌

영리한 프로그래밍을 위한 알고리즘 강좌

(17개의 수강평)

13308명의 수강생

무료

권오흠
평생
입문, 초급
56개 수업, 총 28시간 14분
SEONGMOOK LIM 프로필

Python 으로 구현해보았습니다. SEONGMOOK LIM 4달 전

class Maze:
    def findMazePath(self, x, y):
        if (x < 0 or y < 0 | x >= N or y >= N): #지도 범위를 넘어선곳
            return False

        elif (maze[x][y] != PATHWAY_COLOR): # White 0 #벽
            return False

        elif (x == N - 1 & y == N - 1): # 최종 목적지
            maze[x][y] = PATH_COLOR #Green 3
            return True

        else:
            maze[x][y] = PATH_COLOR #Green 3 # 계속 갈 수 있는 길인지, 막힌 길인지 파악이 안된 길. 일단 가보는 길
            if (self.findMazePath(x - 1, y) | self.findMazePath(x, y + 1) | \
                self.findMazePath(x + 1, y) | self.findMazePath(x, y - 1)):
                return True
            maze[x][y] = BLOCKED_COLOR #Red 2 $ 위의 if 구문에서 Return 받아서 가면 안되는 길 
            return False

if __name__ == '__main__':
    N = 8
    maze = [[0, 0, 0, 0, 0, 0, 0, 1],
            [0, 1, 1, 0, 1, 1, 0, 1],
            [0, 0, 0, 0, 0, 0, 0, 1],
            [0, 1, 0, 0, 1, 1, 0, 0],
            [0, 1, 1, 1, 0, 0, 1, 1],
            [0, 1, 0, 0, 0, 1, 0, 1],
            [0, 0, 0, 1, 0, 0, 0, 1],
            [0, 1, 1, 1, 0, 1, 0, 0]]

    PATHWAY_COLOR = 0 # 원래 길
    WALL_COLOR = 1 # 벽
    BLOCKED_COLOR = 2 # 이 길로 계속 가면 가다 도중에 막히는 길
    PATH_COLOR = 3 # 이 길로 계속 가면 끝까지 갈 수 있는 길

    s = Maze()
    print(maze)
    s.findMazePath(0, 0)
    print(maze)

0
킨글 프로필

printMaze()는 어떻게 만들어야 할까요? 킨글 8달 전

Reversion의 응용 - 미로찾기 1을 듣고 있는데요.

printMaze()라는 함수가 강의 내용 중 나오지 않아서 질문드립니다.

혹시 힌트라도 주시면 직접 구현해보려고 하는데 도움 부탁드려요

package test;

public class Recursion_Maze {
    /*
     * 현재 위치에서 출구까지 가는 경로가 있으려면
     * 1) 현재 위치가 출구이거나 혹은
     * 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
     */
    private static int N=8;
    private static int maze[][] = {
            {0, 0, 0, 0, 0, 0, 0, 1},   
            {0, 1, 1, 0, 1, 1, 0, 1},
            {0, 0, 0, 1, 0, 0, 0, 1},
            {0, 1, 0, 0, 1, 1, 0, 0},
            {0, 1, 1, 1, 0, 0, 1, 1},
            {0, 1, 0, 0, 0, 1, 0, 1},
            {0, 0, 0, 1, 0, 0, 0, 1},
            {0, 1, 1, 1, 0, 1, 0, 0}
    };      
    private static final int PATHWAY_COLOUR = 0; // WHITE
    private static final int WALL_COLOUR = 1; // BLUE
    private static final int BLOCKED_COLOUR = 2; // RED
    private static final int PATH_COLOUR = 3; // GREEN

    public static void main(String[] args) {
        printMaze(); // 에러
        findMazePath(0,0);
        printMaze(); // 에러
    }
    public static boolean findMazePath(int x, int y) {
        if (x<0 || y<0 || x>=N || y>=N) // 좌표 내 유효한 범위인가를 체크
            return false;
        else if(maze[x][y] != PATHWAY_COLOUR) 
            return false;
        else if(x==N-1 && y==N-1) {
            maze[x][y] = PATH_COLOUR;
            return true;
        }else {
            maze[x][y] = PATH_COLOUR;
            if(findMazePath(x-1,y) || findMazePath(x, y+1) || findMazePath(x+1, y) || findMazePath(x, y-1)) { // 탐색하기
                return true; 
            }
            maze[x][y] = BLOCKED_COLOUR; // dead end 어떤 방향으로 가도 출구까지 가는 경로가 없다.
            return false;
        }
    }
}

1
Daniel Wiberg 프로필

동서남북 순서 Daniel Wiberg 8달 전

서 -> 북 ->동->남 순서 아닌가요?

0
Hoony 프로필

해당 강좌에 대한 pdf는 다운받지 못하는건가요 ?? Hoony 8달 전

해당 강좌에 대한 pdf는 다운받지 못하는건가요 ??

다이나믹 프로그래밍에 대한 문제 같은것들도 보고싶어서요..ㅠ

0
Hs Kim 프로필

이 강의 ppt 자료는 다운받을 수 없나요? Hs Kim 10달 전

이 강의 ppt 자료는 다운받을 수 없나요?

0
코알못 프로필

C언어로 quicksort 구현 해봤는데 안되네요ㅠㅜ 왜 그런걸까요? 코알못 10달 전

'''#include

int quicksort(int A[], int p, int q);

int partition(int A[], int p, int q);

int main()

{

int num[100]={0,}, n;

scanf("%d", &n);

for(int i=0; i<n; i++) scanf("%d", &num[i]);

quicksort(num, 0, n-1);

for(int i=0; i<n; i++) printf("%d", num[i]);

}

int quicksort(int A[], int p, int q)

{

if(p<q){

int r;

r=partition(A, p, q);

quicksort(A, p, r-1);

quicksort(A, r+1, q);

}

}

int partition(int A[], int p, int q)

{

int i=p-1;

for(int j=p; j<q-1; j++){

if(A[j]<A[q]){

i++;

int tmp=A[i];

A[i]=A[j];

A[j]=tmp;

}

}

int tmp=A[i+1];

A[i+1]=A[q];

A[q]=tmp;

}'''

0
인그니야 프로필

10분 35초에 나오는 식이 잘못된 것 같아요. 인그니야 10달 전

영상에서 나오는

f[n] = f[n-1]+f[n-2];

이 아니라

f[i] = f[i-1]+f[i-2];

이 식이 맞는 것 같은데 아닌가요?

0
Soojin Lee 프로필

넘 재밌었어요.. Soojin Lee 11달 전

프로그래머라면 누구나 미로찾기를 해봤죠

아님말고.. 라니 ㅋㅋㅋ 넘 웃겻습니다 ㅋㅋ

강의도 너무 유익해요 !

0
hello 프로필

Quadratic 코드 관련 질문입니다. hello 2018.05.21

for (int i=0; i<n-1; i++) for (int j=i+1; j<n; j++) if (x[i]==x[j]) return false;

이 부분에서 최악의 경우 실행 횟수가 n(n-1)/2번이라고 했는데, 이 부분이 잘 이해가 안갑니다.

첫번째 for문이 최악으로 n-1번 실행될 수 있고, 두번째 for문이 최악으로 n-1번 실행될 수 있으니까 이때의 최악의 경우 실행 횟수는 (n-1)(n-1)번이 되는 것 아닌가요?

0
김태호 프로필

감사합니다. 김태호 2018.03.18

감사합니다. 열심히 공부하겠습니다.!

0
Young Gyun Park 프로필

강의자료 pdf 파일 얻을수 있을까요? Young Gyun Park 2017.10.07
강의자료 pdf 파일 얻을수 있을까요?

0
Kim Hyun Tae 프로필

정말말 Kim Hyun Tae 2017.08.19
리컬시브가 돌다가 BLOCKED_COLUR가 되어서(길이 더이상 없어서) 돌아나올때 한번 지났던 PATH는 PATH_COLUR이기 때문에 3번 라인 else if(maze[x][y] != PATHWAY_COLOUR) 에서 항상 false를 리턴하면 갇히게

1
고가영 프로필

삽입정렬 코드 관련 내용 고가영 2017.07.19
삽입정렬 코드에서 while (j>=0 && data[j]>data[i]) { data[j+1] = data[j]; j--; } 부분에 문제가 있습니다. data[j+1] = data[j] 문장을 통해 data[i]의 내용이 변경되기 때문에 data[j]와 data[i] 비교가 제대로 이루어지지 않게 되네요. while(j>=0 && data[j]>tmp) { data[j+1] = data[j]; j--; } 로 바꾸었더니 정렬이 잘 이루어집니다.

0
신승윤 프로필

알고리즘 강좌 듣고 있는 중인데 코드가 제대로 작동을 안합니다 신승윤 2016.09.01
컴파일도 잘되고 오류도 안나는데 ... N 이 아무리 커져도 항상 2번째 까지만 실행되고 끝나는데 이유를 모르겠어요;
프로그램을 돌려서 확인해보면 포문을 돌 때 level 이 2로 넘어가는 과정에서 false 가 반환되면 포문안에 있는 그다음 문장이 실행되어야 하는데 그 다음 문장이 실행되지 않고 그냥 포문 밖으로 나가게 되는 것 같은데 확실히는 모르겠습니다. ㅠㅠ

import java.util.Scanner;

public class NQueens{
    public static int N ;
    public static int [] cols;

    public static void printcols(){
      for(int i =1; i<=N; i++){
          System.out.print(cols[i] + " ");
      }
      System.out.print("\n");
    }

    public static boolean promising(int level){
        for(int i =1; i<level ; i++){
            if(cols[i] == cols[level]){
                return false;
            }else if(level-i == Math.abs(cols[level]- cols[i]))
                return false;
        }
        return true;
    }

    public static boolean queens(int level){
        if(!promising(level)){
            return false;
        }
        else if(level == N){
            printcols();
            return true;
        }
        for(int i =1; i<N; i++){
            cols[level+1] = i;
            if(queens(level+1)){
                return true;
            }
        }
        return false;
    }

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        cols = new int [N+1];
        queens(0);
    }
}
a

0
후리지아 프로필

강의자료로 사용한 ppt자료를 받아볼 수는 없는지요? 후리지아 2016.08.24
안녕하세요, 교수님의 좋은 강의 잘 듣고 있습니다. 다시 시작하는 맘으로 듣고 있는데요, 혹시 강의시 사용하시는 자료를 다운로드 받을 수는 없는지해서 문의 드립니다. 언제나 즐거운 하루되세요, 감사합니다.

0