'적자' 생존

하노이의 탑 하노이의 탑이라는 단어는 뭔가 익숙했는데 문제 내용은 굉장히 생소한 내용이었습니다. 재귀 문제를 설명하는 데 있어서 많이 다룬다고 하는데 비전공자여서 그런가 이런 문제가 낯설기만 합니다.. 그래서 가끔 이런 유명한 문제에 대해서는 포스팅을 하면서 깊게 파야겠습니다. 문제 설명 '하노이의 탑'은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로 다음과 같이 그림으로 표현할 수 있습니다. 이 문제의 목표는 기둥 A에 쌓여 있는 원판을 기둥 C에 옮겨서 다시 쌓는 것이 목표입니다. 하지만 원판을 옮길 시에는 다음과 같은 두 가지 조건을 만족하면서 옮겨져야 합니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 이 조건에서 '최소의 이동횟수로..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net PyPy3으로는 어떻게든 돌아가는 로직이긴 한데 뭔가 오기가 생겨 Python3으로도 돌아가는 코드를 작성해보고 싶은 오기가 생겨서 작업하게 되었다. 일단 PyPy3으로 돌아가는 코드부터 알아보자. 1. PyPy3으로만 돌아가는 코드 기본 아이디어 빙산이 몇 개 연결되어 있는지 계산해주는 함수를 만들어준다. (DFS 순회) 빙산에 대한 정보를 ices 리스트에 넣어둔다. 빙산 목록에서 하나씩..

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 우선 순위 큐라는 내용을 공부해놓고는 활용해보지도 못 하다가 이 문제를 통해서 잃어버린 기억을 되찾게 되었다. 우선 처음 우선 순위 큐를 인식하지 못 하고 푼 기본 아이디어부터~ 기본 아이디어 1 (실패) 보석과 가방에 대한 정보를 받아온다. 보석은 가격에 따라 정렬하고 다음 우선순위로 보석 크기에 따라 정렬한다. 가방은 크기에 따라 정렬한다. 이중 반복문으로 가방을 순회하면서 보석을 순서대로 순회하면..

기본 아이디어 예상 등수를 정렬한 다음에 1등부터 N등까지의 차이를 계속 결괏값에 더해준 것을 반환한다. 코드 N = int(input()) expects = [int(input()) for _ in range(N)] expects.sort() result = 0 for n in range(1, N + 1): result += abs(expects[n - 1] - n) print(result) 느낀 점 언제나 느끼지만 그리디는 문제를 처음보고 영감을 바로 떠올리지 못 하면 시간을 많이 잡아먹는 것 같다. 다른 아이디어를 떠올리면 그에 대한 구현을 하는데 또 한 세월이고 틀릴 가능성 자체가 높다.. 그냥 많은 문제를 풀어서 경험을 축적하는 수밖에..

DP문제는 언제나 백준에 올라와 있는 난이도에 비해 상당히 어렵다. 진짜 아이디어가 생각 안 날라면 끝까지 안 나는거 같다. 그래서 여러 DP 문제를 풀어보고 여러 아이디어를 접해보는 것이 많은 도움이 된다. 그 중에서도 괄호와 관련된 아이디어는 두고두고 쓰일 것 같다는 생각이 들어 정리하려고 한다. 기본 아이디어 일단 괄호를 열고 닫으려면 짝수여야 한다. 위 그림에서 괄호 전체 개수를 n개로 잡고 첫 번째 연 괄호를 닫는 괄호가 i번째라고 한다. 첫 번째 연 괄호와 그 괄호를 닫는 사이의 공간(--------)의 괄호의 개수는 i - 2개가 된다. i번째 이후의 공간 이후(~~~~~~)의 괄호의 개수는 n - (i - 2) + 2라서 n - i 개가 된다. 괄호가 0개일 때는 아무것도 넣지 않는다는 차..

알고리즘은 꾸준히 풀었는데 글 업로드를 안 했다...정말이다..정말 열심히 풀었다.. 어쨌든 낮은 난이도에 비해 배울 점이 많은 문제라서 이렇게 기록을 남기게 되었다. www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 기본 아이디어 두 소수의 합으로 짝수를 이루는 과정에서 각 수에 대해 소수이지 확인하는 절차가 필요하다. 입력이 첫째줄에 테스트 케이스의 수가 주어지고 그 수 만큼 테스트 케이스가 주어지는 구조이다. 각 수에 대해 소수인지 체크한 리스트를 한 번만..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 # 사용자의 위치를 업데이트하는 함수 def setNewPosistionOfUser(cur_pos, move, m_idx): new_y = cur_pos[0] + m_case[move[m_idx]][0] new_x = cur_pos[1] + m_case[move[m_idx]][1] # 범위 안에 들면 위치를 업데이트 하고 if 0

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] def deepcopy(lst): new_lst = [] for y in range(len(l..