인프런 커뮤니티 질문&답변
작성한 질문수
논리질문
해결된 질문
작성
·
372
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
주사위 윷놀이 문제 보고서
http://boj.kr/7a485f4fb46842189dc2ce91d1db7c91 이렇게 생각을 했는데, 처음 입력받은 이동 거리를 각 말로 이동해보고, 이동 장소에 가장 높은 숫자가 있는 말을 이동하려는 그런 방식으로 꾸미려 하던 중에 구현을 어떻게 해야할지 잘 떠오르지 않아 강의를 보았는데, 완전 다른 논리로 푸시는 걸 보고, 제가 생각한 방식에 대해 강사님의 생각을 들어보고 싶습니다. (아직 구현을 하다 말아서 코드가 다 있지 않은 점 양해 부탁드립니다..)
답변 1
1
안녕하세요 ㅎㅎ
처음 입력받은 이동 거리를 각 말로 이동해보고, 이동 장소에 가장 높은 숫자가 있는 말을 이동하려는 그런 방식
이거는 그리디한 방식 아닌가요?
이런 그리디한 방식은 반례가 있을 확률이 높아요. 따라서 첨부터 그리디한 방법보다는 모든 경우의 수를 생각하는게 좋습니다.
그리고.. 함수는 하나의 역할만 하는게 좋아요.
check는 해당 부분에 말이 있나 없는지만 확인하는 로직이 좋지 않을까요?
void check(int moving)
{
int _max = -1;
int tmp_width[4] = {};
감사합니다.
http://boj.kr/8a0595cbab5c464e9e8a7963d9faa7eb
당시 해보다가 너무 안 되어서 시간이 지나고 다시 해보았습니다. 강사님 코드 이해하고, 변수만 이해하기 좋게 바꾸려 하는데, 변수가 너무 헷갈려서 어떤 것이 잘못된 것인지, 어디서 꼬였는지 모르겠어요..
안녕하세요 kim님 ㅎㅎ
int mal_tmp_width_idx = move(init_mal_width_idx, a[dice_idx]); // move(기존 말 위치, 이동 가능 횟수)
if (isMal(mal_idx, mal_idx)) continue; 이부분이요.
int mal_tmp_width_idx = move(init_mal_width_idx, a[dice_idx]); // move(기존 말 위치, 이동 가능 횟수)
if (isMal(mal_tmp_width_idx , mal_idx)) continue; 이렇게 되어야 하지 않을까요?
감사합니다. 변수가 너무 많아 헷갈리네요,,
말씀해주신대로 수정 후, 코드를 돌려보니 4%에서 오류가 발생해서 어떤 점이 틀렸는지 확인 차, 강사님 코드를 제가 그대로 따라 입력해봤는데요, 왜 오류가 발생하는 걸까요..?
안녕하세요 ㅎㅎ
add(5,21); add(21,22); add(22,23); add(23,24);
add(15,29); add(29,30); add(30,31); add(31,24);
add(10,27); add(27,28); add(28,24); add(24,25);
add(25,26); add(26,20); add(20,100);
v[1]=2; v[2]=4; v[3]=6; v[4]=8; v[5]=10;
v[6]=12; v[7]=14; v[8]=16; v[9]=18; v[10]=20;
v[11]=22; v[12]=24; v[13]=26; v[14]=28; v[15]=30;
v[16]=32; v[17]=34; v[13]=36; v[19]=38; v[20]=40;
v[21]=13; v[22]=16; v[23]=19; v[24]=25;
v[27]=22; v[28]=24; v[25]=30; v[26]=35;
v[29]=28; v[30]=27; v[31]=26;이부분이요. 다시 확인 부탁드립니다.
이부분외에는 코드 정말 잘 짜셨습니다. :)
또한,
주석 달아놓으신 거 봤는데요.
이부분은 백트래킹이 아닙니다.
방문했다 >> 방문하지 않았다 로 처리하는 부분이지 백트래킹부분이라고는 할 수 없어요.
ret = max(ret, go(here+1) + v[mal_idx]);
mal[i] = temp_idx;백트래킹은 모든 경우의 수를 탐색하는 것이 아니라 "아 이 경우의 수는 탐색하지 않아도 되는 구나" 하면서 해당 경우의 수를 가지치기한 탐색 방법을 의미합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
귀찮으실텐데, 한 문제에 대한 질문을 이렇게까지 받아 주시니 감사합니다. 추가로 개념 부분도 올바르게 조언해 주심에 감사합니다.
알고리즘 문제 푸는 것이 아직 습관이 안 되어서 어렵지만, 남은 방학동안 열심히 해보겠습니다. :)
감사합니다! :)