알고리즘 (104) 썸네일형 리스트형 [SW Expert Academy] 길찾기 길찾기 SW Expert Academy는 문제 복제가 금지되어 있기 때문에 링크로 대체하겠습니다. 어떻게 풀까? 대표적인 DFS / BFS 문제입니다.저 같은 경우는 그냥 시작점에서 큐를 돌려서 BFS를 이용해서 풀었습니다! 0번 노드에서 시작해서 0번 노드에서 이어지는 노드들을 모두 큐에 넣은 후에 방문 했다는 것을 체크해 둡니다.만약, 99번 노드가 나온다면 바로 연결되어있다는 것으로 끝내주면 됩니다.하지만 큐가 빌 때까지 99번 노드를 찾을 수 없다면, 시작 노드에서 끝 노드로 갈 수 없다는 것이 될 것입니다! 문제를 하나 풀어보겠습니다. 큐에 시작점인 0을 넣고, 0번을 방문 했다고 체크 합니다. 큐의 가장 위에 있는 0번 노드가 시작 노드가 됩니다.0번 노드가 가리키는 1번과 2번 노드를 큐에 .. [알고스팟] 드래곤 커브 문제 링크 드래곤 커브문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)DRAGON2000ms65536kb1009577 (57%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제드래곤 커브(Dragon curve)는 간단한 수학 규칙으로 그릴 수 있는 그림으로, 위 그림같은 형태를 지닙니다. 드래곤 커브는 선분 하나에서 시작해서 간단한 규칙으로 이 선분을 변형해서 만들어지며, 변형이 한 번 이루어져 세대가 변할 때마다 더욱 복잡한 모양으로 진화합니다. 이 도형같이 일부를 확대했을 때 전체와 비슷한 형태로 구성된 도형들을 프랙탈(fractal) 이라고 하지요.드래곤 커브를 그리는 방법을 드래곤 커브 문자열이라고 부릅시다. 드래곤 커브 문자열은 X, Y, F, +, -로.. [알고스팟] k번째 최대 증가 부분 수열 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)KLIS2000ms65536kb2297484 (21%)출제자출처분류JongMan연습문제보기문제어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9의 부분 수열이 아니다.어떤 부분 수열이 _단조 증가_할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 하며, 이 중 가장 긴 것을 최대 증가 부분 수열 (LIS, longest increasing subsequence) 라고 한다. 예를.. [알고스팟] 모스 부호 사전 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)MORSE2000ms65536kb2281641 (28%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 들어 알파벳 J는 모스 부호 o---로 표현되고, M은 --로 표현됩니다.n개의 장점과 m개의 단점으로 구성된 모든 신호들을 담고 있는 사전이 있다고 합시다. 예를 들어 n = m = 2라면 다음과 같은 신호들이 포함되어 있는 것이죠.--oo -o-o -oo- o--o o-o- oo--이 신호들은 사전순서대로 정렬되어 있습니다. -의 아스키 코드.. [알고리즘] 동적 계획법(dynamic programming) - 4 오늘은 알고리즘 동적 계획법 4번째를 설명하도록 하겠습니다!진짜 동적 계획법 엄~~~청 길어서 거의 10까지 할 것 같아요. 이번 동적 계획법에서는 k번째 답을 계산할때 쓰는 방법입니다! 예를 들면, 한 배열에서 LIS들은 한 가지 방법만 있는 것이 아닙니다.가능한 LIS들을 사전순으로 나열한다고 할 때, k번째 LIS를 구하려면 어떻게 해야할까요? 우선, 사전순으로 개수를 세는 알고리즘을 만드는 경우를 생각해 봅시다. 1번째 답으로 올 수 있는 경우가 3개 있다고 합시다. 그럼, 경우 1에서 만들어 질 수 있는 수가 n1개 있을것이고,경우 2에서 만들어질 수 있는 경우의 수가 n2개 있을 것 입니다. 하지만, 만약 경우 1에서 만들어질 수 있는 수가 k개 보다 작으면 어떨까요?그럼, 경우 1의 경로를 .. [SWExpertAcademy] Code Battle (18.8.12 수정) 글이 다 날아갔다... 너무슬프다.. 다시 써야겠따.. SW Expert Academy의 문제는 무단 복제가 금지되어 있으므로 링크로 대체합니다. 4579. 세상의 모든 팰린드롬 2 이 문제는 이전에 왔던 펠린드롬과 비슷하다!하지만 훨씬 쉽다! 왜냐하면 *은 모든 글자를 대체할 수 있기 때문이다!따라서 뒤에서 부터 팰린드롬이 되는지(문자가 같은지)확인하다가 별표를 만나면 어떠한 단어든 팰린드롬이 가능하다는 소리다!(단, 문자를 확인하면서 팰린드롬이 안된다면 그 문자는 무조건 팰린드롬이 안되는 것이다!) 예를들면, a*wflkjwrglakjgla 라는 단어를 생각해보자!뒤에 a가 팰린드롬이니 제외하고 *wflkjwrglakjgl를 보면,*에는 wflkjwrglakjgl가 거꾸로 들어가기만 하면 팰린드롬이 .. [알고스팟] 광학 문자 인식 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)OCR60000ms65536kb1203292 (24%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제알림: 채점 서버 속도 문제로 시간 제한을 60초로 늘리고, 테스트 케이스 수를 20으로 줄입니다.광학 문자 인식(Optical Character Recognition)은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정을 말합니다. OCR 알고리즘들은 대개 수많은 필기 샘플을 통계적으로 분석하고 패턴을 찾아내어 각 단어들을 인식하곤 합니다. 하지만 단순히 각 단어들을 개별적으로 인식하기보다, 단어의 분포나 문법 등을 고려하면 더 나은 결과를 얻을 수 있는 경우가 많습니다... [알고스팟] 여행 짐 싸기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PACKING2000ms65536kb41941145 (27%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.물건노트북 컴퓨터카메라XBOX365커피그라인더아령백과사전부피4264210절박도7106754캐리어의 용량이 정해져 있기 때문에 가져갈.. 이전 1 ··· 7 8 9 10 11 12 13 다음
