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) 느낀 점 언제나 느끼지만 그리디는 문제를 처음보고 영감을 바로 떠올리지 못 하면 시간을 많이 잡아먹는 것 같다. 다른 아이디어를 떠올리면 그에 대한 구현을 하는데 또 한 세월이고 틀릴 가능성 자체가 높다.. 그냥 많은 문제를 풀어서 경험을 축적하는 수밖에..
[python] boj 10422 괄호
DP문제는 언제나 백준에 올라와 있는 난이도에 비해 상당히 어렵다. 진짜 아이디어가 생각 안 날라면 끝까지 안 나는거 같다. 그래서 여러 DP 문제를 풀어보고 여러 아이디어를 접해보는 것이 많은 도움이 된다. 그 중에서도 괄호와 관련된 아이디어는 두고두고 쓰일 것 같다는 생각이 들어 정리하려고 한다. 기본 아이디어 일단 괄호를 열고 닫으려면 짝수여야 한다. 위 그림에서 괄호 전체 개수를 n개로 잡고 첫 번째 연 괄호를 닫는 괄호가 i번째라고 한다. 첫 번째 연 괄호와 그 괄호를 닫는 사이의 공간(--------)의 괄호의 개수는 i - 2개가 된다. i번째 이후의 공간 이후(~~~~~~)의 괄호의 개수는 n - (i - 2) + 2라서 n - i 개가 된다. 괄호가 0개일 때는 아무것도 넣지 않는다는 차..
[python] boj 17103 골드바흐 파티션
알고리즘은 꾸준히 풀었는데 글 업로드를 안 했다...정말이다..정말 열심히 풀었다.. 어쨌든 낮은 난이도에 비해 배울 점이 많은 문제라서 이렇게 기록을 남기게 되었다. www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 기본 아이디어 두 소수의 합으로 짝수를 이루는 과정에서 각 수에 대해 소수이지 확인하는 절차가 필요하다. 입력이 첫째줄에 테스트 케이스의 수가 주어지고 그 수 만큼 테스트 케이스가 주어지는 구조이다. 각 수에 대해 소수인지 체크한 리스트를 한 번만..
본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!! https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 기본 아이디어 기본적인 아이디어는 전에 올린 7576 토마토에서 z축 방향의 코드를 추가한 것에 불과하다 하지만, 그보다 더 큰 위협이 있었으니... import s..
본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!! https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 기본 아이디어 날이 지날 때마다 익은 토마토에서 안 익은 토마토로 번져나가는 구도가 BFS에 가깝다고 생각하여 BFS로 구현하였다. 큐(Queue)에는 익은 토마토의 x좌표..
본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!! https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 기본 아이디어 DFS를 활용 한 번 방문한 곳을 visited에다가 기록 import sys sys.stdin = open('input_1012.txt', 'r') sys.setrecursionlimi..