Algorithm

백준 16112 5차 전직(그리디)

https://www.acmicpc.net/problem/16112 16112번: 5차 전직 메이플스토리 뉴비 키파가 드디어 레벨 200을 달성하고 5차 전직이라는 시스템을 이용해 캐릭터를 더욱 강력하게 만들려고 합니다. 5차 전직을 하려면 먼저 퀘스트를 통해 아케인스톤이라는 아 www.acmicpc.net 익숙한 메이플 얘기가 나와서 반가웠당 아케인스톤 활성화 시키고 경험치 많이 먹으려고 하는거 같은데 여러개 활성화가 가능하다고 한다(k개 만큼) 가장 경험치를 많이 먹기 위해선 제일 경험치통이 작은 아케인스톤부터 하나씩 활성화 해야한다 3 2 100 300 200 100 활성 (200 + 300) 200 활성 (300) 4 2 100 300 200 400 100 활성 (200 + 300 + 400) 2..

백준 9421 소수상근수(소수)

https://www.acmicpc.net/problem/9421 9421번: 소수상근수 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 = www.acmicpc.net 소수(prime)에 대해서 구현할 줄 알면 쉬운 문제였다. '에라스토테네스의 체'를 이용하여 소수를 구하고 구현해주면 되는 문제였다. 에라스토테네스의 체 연습문제 재밌는점은 각 자리수를 제곱하고 더해주는 기법을 map()으로 표현할 수 있다는 점이다. tmp = sum(map(lambda x: int(x) ** 2, temp)) map(적용시킬함수, 대상변수) 각 자리수에 대해..

백준 2872 우리집엔 도서관이 있어(그리디)

https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 개인적으로 어려웠던 문제였다. 여러 케이스들을 직접 돌려보면서 규칙을 찾는데 애를 먹었다. 여러번 시도 끝에 찾은 규칙은 list를 순차적으로 탐색하면서 std보다 작은 값은 무조껀 앞으로 빼줘야된다는 것이다. ex) 3 1 4 2 5 std = 3 3보다 작은 수는 1,2인데 얘내는 무조껀 앞으로 빼줘야됨. 이런 규칙을 찾고 처음에 list,remove, list 이어붙이기 이런걸 썻지만 ..

Coding Test(Two Pointer)

리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리 아마 투 포인터를 몰랐다면 완전 탐색을 이용해서 O(N^2)만큼 했을텐데 투 포인터를 이용하면 선형 관계에서 해결 가능 n = 5 # 데이터의 개수 N m = 5 # 찾고자 하는 부분합 M data = [1, 2, 3, 2, 5] # 전체 수열 count = 0 interval_sum = 0 end = 0 # start를 차례대로 증가시키며 반복 for start in range(n): # end를 가능한 만큼 이동시키기 while interval_sum < m and end < n: interval_sum += data[end] end += 1 # 부분합이 m일 때 카운트 증가 if interval_sum == m: count +=..

Coding Test(Sliding Window)

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이요해 문제를 풀이하는 알고리즘 ● Brute Force - list slicing 을 이용한 방법 for i in range(len(nums)-k+1): r.append(max(nums[i:i+k])) ● queue을 이용한 방법 (Fast) for i, v in enumerate(nums): window.append(v) if i

백준 16926 배열 돌리기 1(구현) ★

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net ● 배열을 돌리기 위한 다양한 방법 중에 deque.rotate()를 사용하는 방법을 택했다. ● 2차원의 배열을 1차원으로 바꿔준다음에 rotate()를 돌리면 된다. ● 반시계 방향이기때문에 순서에 유의하며 1차원으로 바꿔주고 몇번 회전을 시킬껀지 rotate(r) 해준다. ● 똑같은 순서에 맞춰서 ..