알고리즘/백준 (18) 썸네일형 리스트형 [백준] 12850 - 본대 산책 2 (Java/자바) https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법 어떻게 풀어야 하나 고민하다가 답이 안 나와서 바로 구글링을 했다. 입력이 10^9까지 들어와서 O(N)으로 해도 시간초과가 떠서 O(logN)으로 해결해야 했다. 풀이 방식을 제일 잘 설명해준게 이 블로그다. https://chinpa.tistory.com/149 [백준] 12850 - 본대 산책 2 (G1) https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net.. [백준] 17404 - RGB거리 2 (Java/자바) https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 방법 RGB거리를 풀었을 때는 dp로 간단하게 풀렸는데 이번 문제에서는 1번째 집과 마지막집의 색이 달라야 한다는 조건이 추가돼서 조금 더 복잡해졌다. 처음에는 마지막집까지 dp를 구한 다음 첫번째 집과 마지막 집의 색이 같으면 첫번째 집의 비용을 빼주고 (2번째 집과도 다른) 남은 한가지 색의 비용을 더해줬다. 이러면 첫번째 집과 마지막 집의 비용을 비교하지 않.. [백준] 16946 - 벽 부수고 이동하기 4 (Java/자바) https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 방법 처음에는 칸마다 bfs로 풀었더니 시간초과가 났다. bfs의 시간복잡도가 O(n^2)이고 배열의 개수가 최대 1000*1000이라 시간초과가 발생했다. 그래서 0끼리 붙어있는 공간에 1번부터 번호를 붙여 집합으로 분류할 때만 bfs를 사용하고 이후 이동 가능한 공간을 찾을 때는 사방의 집합 번호만 확인했다. package Graph; import java.io.Bu.. [백준] 2798 - 블랙잭 (Python/파이썬) https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 풀이 방법 자바와 달리 파이썬은 itertools.permutation을 이용하면 순열을 직접 구현하지 않고도 사용할 수 있어서 너무 편하다..! 문제 그대로 받아온 카드 중 3장을 순열로 뽑아 합이 m이 되면 탐색을 멈추고 m보다 작다면 최대값(big)을 갱신하면서 탐색을 진행한다. from itertools import permutations n, m = map.. [백준] 11729 - 하노이 탑 이동 순서 (Python/파이썬) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 방법 n개의 탑을 시작 기둥에서 목표 기둥으로 옮기는 동작을 3단계로 분류하면 (n-1) 개의 탑을 중간 기둥(6-start-end)으로 옮긴다. 맨 아래 원판을 목표 기둥(end)으로 옮긴다. (n-1) 개의 탑을 목표 기둥으로 옮긴다. 이때 목표 기둥의 번호는 2번 아님 3번이 번갈아서 나올 텐데 1,2,3번 기둥만 사용하므로 6-start-end를 하면 시작 기둥과 목표 기.. [백준] 2447 - 별찍기 10 (Python/파이썬) https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 방법 왼쪽 위에서부터 기저모양(n=3^(i-1)일 때의 모양)을 3*3만큼 반복해서 n=9, 27, 81.. 이런식으로 완성시켜나간다. def star(n): global map if n==3: map[0][:3] = map[2][:3] = [1] * 3 map[1][:3] = [1, 0, 1] return a = n//3 star(a) for i in range(.. [백준] 17143 - 낚시왕 (Java/자바) https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 방법 상어의 위치를 바로 알 수 없을까 고민하다가 해답이 떠오르지 않아서 결국 하나씩 움직이는 방법을 택했다. 문제에서 상어의 속도는 1000까지 가능한데 격자판의 크기는 100이 최대이다. 상어가 한 줄에서만 움직이므로 몇 번 이동하고 나면 상어가 다시 원래 위치에, 원래 방향으로 돌아와있다. 이러한 반복되는 움직임을 제거하기 위해 상어의 속도를 바꿔줬다. 상어가 상, .. [백준] 17387 - 선분 교차 2 (Java/자바) https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 풀이 방법 CCW 알고리즘을 이용하여 한 선분에서 다른 선분의 끝점들로의 방향(시계 or 반시계)을 구하고 이를 통해 선분 간의 관계를 파악한다. 직선이라면 방정식이라도 세워보려고 했을텐데 선분이라 어떻게 해결해야 할지 몰라서 구글의 힘을 빌렸다. 아래의 두 블로그를 참고했다. 위에 계신 분이 개념을 설명해주고 이를 좀더 디테일하게 설명한게 아래분의 블로그 같았다. https://hyeo-noo.tistory.com/108 [백준 17387] 선분 교차 2.. 이전 1 2 3 다음