분류 전체보기 (171) 썸네일형 리스트형 [알고스팟] 외발 뛰기 문제링크 외발 뛰기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)JUMPGAME3000ms65536kb86743140 (36%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문.. [알고리즘] 동적 계획법(dynamic programming) - 1 오늘은 동적 계획법에 대해서 설명하겠습니다.동적 계획법은 분할 정복과 유사합니다.동적 계획법 또한, 문제를 더 작게 나눈 다음에 각 조각의 답을 구한 뒤에 이 답들로부터 원래 문제에 대한 답을 계산하기 때문입니다.다만, 동적 게획법의 부분 문제는 두 개 이상의 부분 문제를 푸는데 사용될 수 있습니다!따라서, 해당 부분 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 다시 사용해서 속도의 향상을 가져올 수 있습니다.이를 위해서, 각 부분 문제의 답을 메모리에 저장하는 방식을 취합니다!!이를 메모이제이션 (memoization) 이라고 합니다. 여담이지만, 메모이제이션을 메모리제이션과 햇갈리는 경우가 굉장히 많습니다! 실은 저도 최근에서야 메모리제이션이 아니라 메모이제이션인걸 알았습니다.... 2018.6.11 (월) 강남에 갔다. 오늘은 강남을 갔다. 이전에 같이 스터디를 했던 형과 만나기로 한 날이기 때문이다.이 스터디는 알고리즘 스터디었고, 오픈 카톡방에서 만난 사람들이었다.정말 이번 상반기는 항상 이 사람들과 함께 했던 것 같다.삼성 상담회도 가고, 면접 스터디도 하고, 소프트웨어 역량 테스트도 함께 봤다.항상 힘내자고 서로 격려했고, 확실히 알고리즘 부분에서도 굉장한 성장을 이루었다.특히, 굉장히 다들 좋은 사람들이어서 상반기를 준비하면서 큰 힘이 되주어서 정말로 고마웠다. 이 형은 카톡 아이디가 '빵천'이었다. 처음엔 무슨 의미일까? 했는데.. 나중에 의미를 알고보니 정말 간단했다. ㅋㅋ처음에 만나자고 한 것은 합격 후기를 듣기 위해서라는 명목이었지만, 면접도 오래 전에 끝났고,이전에 이미 충분히 들었기 때문에 그냥 이런.. [분할정복/카라츠바 알고리즘] 곱셈 최적화! 카라츠바 알고리즘에 대해 알아보자 기본 단계 카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다. x와 y를 B진법의 n자리수라고 하자. n보다 작은 양수 m에 대해 다음과 같이 x, y를 쪼갤 수 있다. x = x1Bm + x0 y = y1Bm + y0 (단, x0과 y0는 Bm보다 작다.) z2 = x1y1 z1 = x1y0 + x0y1 z0 = x0y0 라고 할 때, x와 y의 곱은 xy = (x1Bm + x0)(y1Bm + y0) = z2 B2m + z1 Bm + z0 이 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다. z2 = x1y1 라 하자. z0 = x0y.. [알고스팟] 팬 미팅 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)FANMEETING15000ms65536kb4020560 (13%)출제자출처분류YongrokRUN Programming Contest, Fall 2009보기문제가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍.. [알고스팟] 울타리 잘라내기 문제 링크 울타리 잘라내기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)FENCE3000ms131072kb94872890 (30%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비.. [알고스팟] 쿼드 트리 뒤집기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)QUADTREE10000ms65536kb57762760 (47%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N× 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.이.. [분할 정복] 분할 정복에 대해서 알아보자 분할 정복은 이름 그대로 문제를 작은 부분으로 쪼개어서 해답을 찾은 뒤에 작은 조각들을 합치면서 다시 해답을 찾아내가는 방식입니다. 대표적인 분할 정복 방식으로는 병합 정렬이 있습니다. 위 그림에서 보듯이 병합 정렬은 배열을 반씩 쪼개서 가장 작은 단위로 쪼갠 다음에 정렬하고, 이 정렬된 배열을 점차적으로 정렬하는 방식입니다. 분할 정복을 할 때 가장 중요하게 고려해야 할 점이 있습니다. 바로 조그만 조각에서 나온 최적해를 이용해서 구해나간 답이 결국 최종 해답과 일치해야 한다는 것입니다. 작은 조각에서 나온 답이 결국 더 큰 조각에서는 쓸모가 없어진다면 의미없는 일을 한 것이겠죠... 또 다른 예로는 행렬의 거듭제곱을 구하는 코드가 있습니다. 보통의 방법으로 행렬의 m 제곱을 구하게 되면, n x n의.. 이전 1 ··· 17 18 19 20 21 22 다음
