아니 학교에서 레포트를 냈는데
시바 장기판 모퉁이에서 임의의 위치 x, y까지 마 로 이동했을때 최소 이동거리와 이동경로를 구하는 알고리즘을 구현하래
근데 내가지금 5시간동안 고민하는데도 도저히 답이 안나온다. 문제의 복잡도가 너무높다 진짜.
형들은 이거 풀수있다고 생각해? 개강 일주일밖에 안됬고 수업도 조또안햇는데?
시바 장기판 모퉁이에서 임의의 위치 x, y까지 마 로 이동했을때 최소 이동거리와 이동경로를 구하는 알고리즘을 구현하래
근데 내가지금 5시간동안 고민하는데도 도저히 답이 안나온다. 문제의 복잡도가 너무높다 진짜.
형들은 이거 풀수있다고 생각해? 개강 일주일밖에 안됬고 수업도 조또안햇는데?
쉽네.
DP돌려 DP느님이 진리다.
우선 이동경로 구하기 알고리즘만 짜면 나머진 걍 다 끝나겄네
힌트좀 주라. 그래프 쓰면되?
DP
디피가 머지 딮페스파인딩 머 깊이우선탐색?
어떤 기물들을 대상으로 할건지 알아야 하지 않을까? 차나 말이나 상은 당연히 포함될테고, 포같은건 당연히 포함이 안되는 것일테고, 차, 말, 상만 대상으로 하는거임? 졸은?
최소신장트리쓰세요 헤헤
이동기물은 말 임 말새킹
DP 뭔지 모름?
ㄴ 마라고 햇자나
이거 말해주면 거의 다 가르쳐주는 꼴인데.
디피가 머임 한번도 들어본적 없는데 -,.= 알고리즘이름임? 검색해도 안뜨네...
ㅋㅋㅋㅋ 아 \'마\' ㅋㅋㅋㅋㅋㅋㅋㅋ 나는 \'바로\'를 오타낸줄 알았음 ㅋㅋ 이거 쉽게 해결 가능함.
가중치가 없는데 최소신장트리써서 머하여
쉽게 설명하자면 서로 다른 방법이 같은 결과물를 낼 때 효율이 낮은 부분을 버리면서 백트래킹하는 기법임
디피
최소신장트리라, 비슷하겠네. 그런데 가중치가 왜 없냐, 이동횟수 최소로해야한다며
ㄴ그가중치가 그가중치가 아닐텐데
a* 같은걸 응용하면 더 빠르게 풀 수 있지 않을까.
ㄴ잠시 내가 알고리즘을 착각했나? 트리부분 대충했더니 가물가물해
아, 최소 신장 트리가 아니라 그거다, 우선 너비탐색
노드로 가는 가중치는 쓸모가 없지 저 문제에선..
이거는 문제 해결 방식을 두 개로 나눠야 함. 일단 도달하려는 최종 목적지를 (x, y)라고 하면 움직여야할 말이 (x-2,y-2), (x+2, y-2) x-2, y+2), (x+2, y+2) 가 나타내는 사각형 안까지 들어가게 하면 됨. 현재 말의 위치에서 (x,y)까지의 최단 거리를 나타내는 다음 지점까지 걍 이동시키면 됨. 이렇게 박스 안에 들어가면 패턴이 나타남. 최종 목적지 (x,y)에서 (x-1, y), (x+1, y)처럼 바로 옆칸에 도달한 경우라든가, 이런 패턴을 추려서 이동시키면 깔끔하게 해결됨.
장기판에다가 너비 탐색하다보면 이미 탐색한곳이 또 검색될거야. 동의해?
ㄴ 기물들의 이동경로만 따로 맵을 만들어 주고 a*로 풀면될듯
너비탐색으로 진행했으면 중복된 곳에 도착했을때, 그 경로는 횟수가 더 많은 상태일꺼야 동의해?
그러면 시간이 오래걸릴듯 하다... 최단경로를 찾아야하는데 이리저리 다방문하면 쓸모가없잖앙
그렇다면 너는 너비탐색을 돌리면서 그 칸에 처음 도착한 칸의 위치를 그 칸에다 기록하면 되겠지?
파워떢밥이넴
그렇게되면 너는 메모리를 장기판 크기 만큼 밖에 안쓸거야.
동의해?
하지만 장기판 위치마다 각 말들이 이동했던 횟수를 메모리에 다기록해야겟지
쓸데없는 계산도 많아질 듯...
그리고 각 칸으로 가는 경로는 8가지인데 각 칸에 한번밖에 안 갈테니 시간복잡도는 O(n), (n은 장기판 크기)겠지?
근데 생물학 말대로 했을때 한번도 안가본 곳을 간다고하면... 만약의 경우에 구석탱이에 갇혀버리는 사태가 일어나지 않을까..?
\'안가본 곳을 골라서\'
컴퓨터가 무한루프에빠질듯
음. 그니까 방금 책뒤지다가 내가 생각한 방법이. 장기판상의 말의 이동경로상의 모든점을 노드로 만들고 이동경로에따라 간선으로 연결하는거지. 그럼 하나의 존나거대한 그래프가 탄생할 텐데. 여기서 너비우선탐색을 써서 최단경로를 알아내는거야. 어때?
우선 너비 탐색 안해보셨나...?
백트래킹한다고했으니까괜찮겟지머
근데 장기판상에서 말이 이동가능한 경로가 존나게 많아지고 연산량이 존나게 늘어날것 같다는게 문제.
으혀랴디// 개념은 잘 잡은듯
연산량 줄이는게 DP
장기판 그래프를 만들고 기물이 이동할 수 있는 경로만 따로 그래프로 만들어와서 그 목적지까지 a*로 가중치 매기면 한방에 풀릴거같은데
아까 말했잖아. 출발지에서 특정 칸으로 갈때 가장 적은 횟수가 가는 방법말고는 필요없으니 생략한다고
하긴 a*가 디피를 응용한거지
아까부터 a*이야기가 나오는데 a*가 뭔지 몰라서 뭐라고 말을 못하겠다... ;ㅅ;
그리고 말이 그래프지 그냥 2차원 배열써도 그만
a*알고리즘이라고 해서.. 이동경로를 최소로 찾아주는 알고리즘이야
생물학 말이랑 비슷한데 이동횟수를 카운트해서 판단하는거지 목적지까지
그리고 우선 너비 탐색하면 목적지에서 도착한 시점에서 연산 종료되니 실제로는 맵 전체를 뒤지진 않음
한 상태마다 갈수있는 위치를 카운팅하는거야
그런데 이렇게 안하고 아놔콘다형처럼 꼽살써도 그만
내가 모르는 늅이라 뭐하시는 분인가 했더니 CV하시는 분이네. 영상처리 만세
응 근데 나도 처음에 아나콘다형처럼 생각했는데 도착하려는 위치가 모퉁이쪽이냐 중앙쪽이냐에 따라서 변수가 너무많이 생기더라. 그거 일일히 구하기 귀찮아서 더 고급스런 방법을 찾고있었엉
예외처리를 해야한다고 말하다니 이 친구 아놔콘다형의 방법을 제대로 활용하지 못하는군
야, 내가 몇살인지 알고 형이라고 그러냐? 앙?
글구 위에 내가 적은거 다시 함 봤더니 버그가 있음.
일단 우선 백트래킹을 먼저 공부해봐야겠군 -,.- 제출까지 얼마안남았는데 으아 ㅠㅠ 죽겟당
일단 짜서 돌려본다음 안되는 부분을 말해봐 도와주겠긔
엉? 그 패턴이란게 무슨말인지 알겠어. 근데 일정범위안에 들어온 목적지로 이동하는 패턴이 여러개가 되잖아. 예를들어 오른족 아래 모퉁이 쪽에서는 마가 오른쪽 아래쪽으로 이동을 못한단 말이야. 그럼 위쪽이나 왼쪽으로 이동하는 패턴을 써야하고 이게 위치에 따라 써야하는 패턴이 많아져. 그럼 그 패턴들 다 구해야 한다는 거지.
아놔콘다//학교에서는 6살 위도 형이라고 부르는 분위기... 그 위로는 만나보지 못했지만 분위기상 10까지는 그냥 형이라 부르는듯하다.
아, 이게 문제가 아니라 횽이라고 안써서 디스거시는건가?
이제부터 횽이라고 쓰겠음. 순간 여기가 DC라는걸 까먹었엉.ㅋㅋㅋ
으혀랴디//혹시 장기판 크기가 바뀌진않지?
ㄴ헐 크기가 바뀔피료가 있엉??
DP 는 Dynamic Programming 약자고요, DP 냄새가 폴폴 나는게 , 1. 한번 움직임이 1개, 가중치나 뭐 이런게 없고 2. 중복이 많은 재귀식으로 쉽게 구현되고,
A* 는 코스트펑션을 짜야되는데 코스트를 알아낼려면 어차피 루트를 찾아봐야하기 때문에 아니고
3. 최소경로 루트도 찾아내란거 보면 , 메모라이즈 하는 DP 인듯
그래프문제는 거의다 리커시브로풀지않나
역시 아싸횽 /ㅂ/
대학원가면 나도 횽처럼 쩔어질수있을까...\'ㅅ\'
아싸횽질문잇는뎅 3번 루트를 찾으라고햇는데 왜 A*쓰면 안대는거얌???
A*는 코스트를 구해야 되는데, 코스트 자체가 루트이고, 단순히 거리로만 해서는 안될것 같아서 흉, 왜냐면 1,1에서 0,0 으로 가야 되면, 세번 걸쳐서 빙 돌아야 되니까
코드 짜보는 중...
그런데 급하게 짤려니까 코드가 좀 병신같이 나온다. ;ㅅ;
ㄴ 아 그럴수도잇구나 올.....
ㄴ아싸형 그러면 그 장기판에 말이 이동할 수 있는 경로만 따로 그래프를 만들어서 a*를 쓰면 안되려나? ㅋ;
코드 올림 ㅅㅂ
타임오버냐? 아니면 벌써 짜서 냈냐?
벡트레킹. 일반적으로 인공지능 난이도라는게 백트레킹 depth를 몇수까지 내다볼건지 설정하는것. 그래서 난이도를 올릴수록 시간이 오래걸리는것.
너도 서울시립대 컴퓨터알고리즘 수업 듣지
그거 오늘까지임 좆됐음 시발