본문 바로가기
728x90
반응형

코딩/백준

알고리즘 - Python / 백준 - 2156번 : 포도주 시식 2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 포도주가 잔에 담겨 순서대로 놓여 있을 때 , 3잔을 연속으로 마시지 못한다. 다음 조건에서 최대한 포도주를 많이 먹으려면 어떻게 해야 하는지 출력하는 문제다. 포인트는 3잔 연속 못마시니까 언제 마시는 걸 멈추고 다시 마실까 이다. I 번째 포도주를 마시거나 마시지 않거나 , 마신다면 몇 번 연속으로 마시는지 기록하면서 모든 경우를 확인하면 된다. 따라서 DP 문제로 접근할 수 있다. DP배열은 DP[포도주.. 더보기
알고리즘 - Python / 백준 - 2205번 : 저울 추 만들기 2205번: 저울 추 만들기 (acmicpc.net) 2205번: 저울 추 만들기 질량(또는 무게)가 1, 2, 3, …, n인 납덩어리가 있고, 질량이 1, 2, 3, …, n인 주석덩어리가 있다. 각각의 질량을 갖는 덩어리들은 1개씩밖에 없다. 이제 이 납덩어리와 주석덩어리를 한개씩 녹여 합 www.acmicpc.net 풀이 질량이 1 ~ n 까지 각 무게당 한 개씩 주석과 납 덩어리가 존재한다. 주석과 납 덩어리들을 한개씩 적절하게 섞어 모두 2의 거듭제곱 무게가 되도록 만드는 조합을 출력하는 문제다. 문제에서 예외 처리가 없다는 것에서 약간의 힌트를 얻었다. 만약 n의 경우에 따라 모두 2의 거듭제곱 무게가 되지 못하는 경우가 있었다면 , 문제에 그러한 경우는 -1을 출력하시오 처럼 예외 처리가 .. 더보기
알고리즘 - Python / 백준 - 3273번 : 두 수의 합 3273번: 두 수의 합 (acmicpc.net) 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 수열 중 ai + aj = x 를 만족하는 쌍의 개수를 찾는 문제다. 투 포인터로 풀 수 있는 가장 기본적인 문제다. 수열을 정렬한 후 앞과 뒤 부터 포인터를 출발시켜 , x보다 크다면 뒤쪽을 당겨 합을 줄이고 x보다 작다면 앞쪽을 밀어 합을 늘인다. 두 포인터가 만날 때 , while 문이 종료되도록 하면 모든 범위에 대해 투 포인터들이 합을 검사하고.. 더보기
알고리즘 - Python / 백준 - 2533번 : 사회망 서비스(SNS) 2533번: 사회망 서비스(SNS) (acmicpc.net) 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 알고리즘 설명 트리 구조와 DP를 합친 Tree DP 문제다. DP의 경우 부문제의 최적해가 모여 전체 문제의 최적해가 찾을 수 있는 경우에 사용할 수 있다. 트리 구조의 경우 서브 트리들이 모여 전체 트리를 이루기 때문에 서브 트리의 최적해들을 통해 전체 트리의 최적해를 찾을 수 있다면 트리 구조에도 DP를 사용할 수 있다. 서브 트리들의 경우 구분할 수 있는 가장 .. 더보기
알고리즘 - Python / 백준 - 1092번 : 배 1092번: 배 (acmicpc.net) 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 크레인의 개수와 각각 크레인이 들 수 있는 최대 무게가 주어지고 , 박스 숫자와 박스의 무게가 주어질 때 , 크레인이 모든 박스를 옮기려면 최소 몇 분이 걸리는지 출력하는 문제다. 무거운 박스를 들 수 있는 크레인 일 수록 무거운 박스를 드는 것이 시간을 줄이기에 유리하므로 그리디 스타일의 문제라고 생각했다. 크레인이 들 수 있는 최대 무게와 박스 무게를 저장한 배열을 오름차순으로 정렬하고 크레인 배.. 더보기
알고리즘 - Python / 백준 - 4149번 : 큰 수 소인수분해 4149번: 큰 수 소인수분해 (acmicpc.net) 4149번: 큰 수 소인수분해 입력은 한 줄로 이루어져 있고, 소인수분해 해야 하는 수가 주어진다. 이 수는 1보다 크고, 262보다 작다. www.acmicpc.net 풀이 1 ~ 2^62 사이의 수를 소인수 분해하고 모든 인수를 오름차순으로 출력하는 문제다. 범위가 매우 넓기 때문에 일반적인 소인수 분해로는 해결할 수 없다. 따라서 O(n^(1/2)) 시간 복잡도의 일반적인 소인수 분해 알고리즘이 아닌 O(n^(1/4)) 시간 복잡도를 가지는 폴라드 로 알고리즘을 사용해서 풀어야 한다. 물론 폴라드 로 알고리즘도 모든 수에 대하여 O(n^(1/4)) 시간 안에 모든 인수를 구하는 것이 확률 적으로 추측될 뿐 , 엄밀한 수학적 증명은 아직 이루어지.. 더보기
알고리즘 - Python / 백준 - 14217번 : 그래프 탐색 14217번: 그래프 탐색 (acmicpc.net) 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 풀이 간선을 제거하고 추가하면서 그 상황에서 root 로부터 다른 노드까지의 최단 거리를 구하는 문제다. 그래프 탐색 문제이면서 최단 거리 문제 이므로 단순하게 bfs로 구현하기로 하였다. 평소 스타일 대로 bfs를 사용해 풀었더니 , 시간 초과가 나왔다. ( 해당 코드 첨부 ) 예제는 문제가 없었기에 방문할 노드를 체크할 때 시간이 오래 걸렸나 생각했다. 첫 번째 코드 첫 번째 코드에서는 2차원 배열을 통.. 더보기
알고리즘 - Python / 백준 - 2667번 : 단지번호붙이기 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 2차원 배열 형태의 그래프를 탐색하는 기초적인 그래프 탐색 문제다. 정사각형 모양의 2차원 배열에 집이 있는 곳은 1 , 집이 없는 곳은 0 으로 표시될 때 , 집들이 붙어있다면 단지로 처리한다. 배열 안에 단지가 몇 개인지 , 각 단지 안의 아파트 수는 몇 개 인지 출력하는 문제다. dfs나 bfs를 이용해 단순하게 그래프를 탐색하고 , 탐색한 노드의 경우 -1 로 체크해주면서 탐색했다. 상하좌우 2차원 .. 더보기
반응형

티스토리툴바