👨💻📱✍️🎢314 BOJ 14588 - Line Friends (Small) 문제 백준 온라인 저지 - 14588번 풀이 과정 선분의 겹칩 유무를 이용해서 각 선분간의 최소 거리 값을 구하는 문제입니다. 모든 선분간의 최소 거리 정보를 알아야하고 N 이 최대 300 이기 때문에 플로이드 와샬 알고리즘을 활용했습니다. 문제를 해결하고 선분 겹칩 연산과 관련해서 다른 분의 제출 코드를 확인해봤는데 다음과 같은 좋은 방법도 있는 것을 알게 되었습니다. a1, b1 = 선분 1 양 끝점 a2, b2 = 선분 2 양 끝점 if max(a1, a2) pivot[1]: return False elif opponent[1] < pivot[0]: return False return True def make_graph(): dist = [[sys.maxsize] * N for _ in range(.. 2021. 3. 14. BOJ 14925 - 목장 건설하기 문제 백준 온라인 저지 - 14925번 풀이 과정 가장 큰 정사각형을 찾는 동적 계획법 문제입니다. 그냥 완전 탐색 으로 찾으려 할 경우 O(N^4) 이기 때문에 시간 초과가 발생하게 됩니다. dp[x,y] = (x, y)지점을 왼쪽 모서리로 하는 가장 큰 정사각형의 한 변의 길이 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[x][y] = min(dp[x + 1][y], dp[x][y + 1], dp[x + 1][y + 1]) + 1 이때 격자를 벗어나는 위치나 장애물이 있는 경우를 기저 사례로 처리해줍니다. 코드 import sys sys.setrecursionlimit(10**6) M, N = list(map(int, sys.stdin.readline().split())) board.. 2021. 3. 14. BOJ 13164 - 행복 유치원 문제 백준 온라인 저지 - 13164번 풀이 과정 그리디 문제가 항상 그렇듯 풀이는 정말 간단한데 아이디어를 생각하는게 어려운 문제였습니다. K 개의 그룹을 만들어야하고 모든 키 정보는 양수라는 점을 이용해서 처음에는 2명 이상의 그룹의 수를 최소화 하는 방향으로 접근했습니다. 여기서 그룹의 인원수는 무조건 적은게 좋다고 생각해서 2인 그룹 의 수를 최소화 할 수 있는 방향으로 고민했었습니다. 그런데 이렇게 접근하니까 최적해를 고르는 명확한 기준을 잡기가 어려웠고 상황에 따라서는 모순이 생기는 경우도 있었습니다. 결국 다른 방법이 필요했는데 타 블로그의 풀이를 참고해서 문제를 해결할 수 있었습니다. 그룹의 수가 K 일 때 그룹의 경계는 K - 1 개 만큼 존재합니다. 여기서 이 경계 값들을 최대화해서 그.. 2021. 3. 14. BOJ 3109 - 빵집 문제 백준 온라인 저지 - 3109번 풀이 과정 파이프를 연결할 수 있는 세 가지 방법을 이용해서 가장 많은 연결 방법을 찾는 문제입니다. 백트래킹 을 이용해서 모든 경우를 찾을 수 있는데 문제는 중복된 탐색이 많이 존재한다는 것입니다. 여기서 얻을 수 있는 아이디어는 백트래킹 을 통해 한 지점에서 목표 지점에 도달하는 방빕이 있는지 판단하고 있다는 것입니다. 따라서 현재 지점에서 목표 지점에 방문이 가능하지 않더라도 이 지점을 다시 미방문 상태로 바꿔주는 것이 아니라 그냥 방문 처리로 남겨놔도 됩니다. (목표 지점에 도달 가능한 경우는 이 경로에 파이프를 놔야하기 때문에 방문 처리를 합니다.) 왜냐하면 이후에 해당 지점에 다시 방문하더라도 또 다시 목표 지점에 도달 불가능한 것은 자명하기 때문입니다. .. 2021. 3. 14. BOJ 14620 - 꽃길 문제 백준 온라인 저지 - 14620번 풀이 과정 백트래킹 을 이용한 탐색 문제입니다. 총 3개의 씨앗을 심을 수 있으며 특정 씨앗을 심을 경우 문제에서 제시된 인접한 위치에는 씨앗을 심을 수 없습니다. 문제에서 십자 모양으로 꽃이 피기 때문에 (1, 1) 부터 시작해서 (N - 1, N - 1) 까지만 탐색을 수행하면 된다는 것을 알 수 있습니다. 각 격자의 칸들을 이용해서 가능한 모든 조합을 만들어보면 되는데 이때 해당 위치에 씨앗을 심을 수 있는지 판단하는 함수를 하나 정의해서 구현합니다. 탐색할 때 주의할 점은 다음 위치부터 탐색하기 위해 (x, y) 값을 재귀적으로 넘겨주는데, 이때 y 가 끝에 도달할 경우(N - 2) 다시 y 축 탐색 시작 지점을 0으로 초기화 시켜주어야 한다는 점입니다. 코.. 2021. 3. 14. BOJ 2688 - 줄어들지 않아 문제 백준 온라인 저지 - 2688번 풀이 과정 줄어들지 않는 n 자리 수를 구하는 문제입니다. dp(num, digit) = num 보다 크거나 같은 수로 시작하는 digit 자리 수의 개수 라고 정의한다면 다음과 같은 점화식을 도출할 수 있습니다. dp(num, digit) = dp(num, digit - 1) + dp(num + 1, digit - 1) ... 이때 `num` 은 `0 2021. 3. 14. 이전 1 ··· 28 29 30 31 32 33 34 ··· 53 다음
