알고리즘 (43) 썸네일형 리스트형 algospot :: MORSE 모스 부호 사전 문제 : https://algospot.com/judge/problem/read/MORSE알고리즘 문제 해결 전략 1권 p.293 [알고리즘 STEP. 1]일단 '-' 와 'o'를 이용해서 만들수 있는 모든 조합을 모두 찾아서 해당 순서 k에 해당하는 문자열만 출력했다.n개의 o와 m개의 -로 모스부호를 만들며, 사전순이므로 -가 o보다 앞에 나와야 한다. * void play(int n, int m, string ret)ret이라는 주어진 문자열에 n개의 o와 m개의 -로 만든 모스부호를 이어붙이는 함수이다. n==0, m==0이라면 주어진 문자를 모두 사용하여 하나의 문자열을 완성한 것이다. 하나의 문자열을 완성할 때 마다 k를 하나씩 줄여가면, k==1일 때 원하는 타겟 문자열을 출력할 수 있다. .. algospot :: PACKING 여행 짐 싸기 문제 : https://algospot.com/judge/problem/read/PACKING 알고리즘 문제해결전략 1권 p.281 가능한 물건의 조합을 하나하나 검사해서, 정해진 무게 제한 안에서 최대 절박도를 내는 물건의 조합을 찾아내는 문제다. [내가 헤맨 부분] - 최대 절박도를 찾는것 까지는 동적 계획법으로 쉽게 떠올릴 수 있는데, 물건들의 이름을 출력하는 부분에서 막혔다. - memset함수를 잘못 이용해서 몇번이나 틀렸다. 값을 직접 계산해서 3번째 인자에 넣고 있었는데, 그냥 sizeof를 이용하는게 정확하다. memset(target, value, sizeof(target)) [알고리즘] * 물건들의 index를 동적계획법에 이용하면 문제가 간단해진다. * int play(int inde.. algospot :: TICTACTOE 틱택토 알고리즘 문제해결전략 책을 바탕으로 코드를 작성함 1) 캐시 3*3 보드이고, 각 칸에는 x, o, . 3가지 케이스가 있으므로 이를 9자리의 3진수 정수로 표현할 수 있음. => int cache[MAX]; 보드판을 받아서 그에 대응하는 9자리의 3진수 정수로 변환해주는 함수(int bijection()) 를 활용하여 캐시를 채워줌. 캐시에는 현재 보드판에서 다음 턴(x 또는 o) 사람의 최선이 이기는것, 지는것, 비기는 것 중 어느것인지를 저장. 2) 재귀함수 보드판에서 이번에 둘 사람에게 일어날 수 있는 최대를 저장한다고 하자. 예를들어 이번에 어디에 두느냐에 따라 이길수도, 질수도, 비길수도 있다면 '이긴다'를 저장하고지거나 비긴다면 '비긴다'를질수밖에 없다면 '진다'를 저장한다. 이긴다는 1, .. 이전 1 ··· 3 4 5 6 다음
