백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 17386번: 선분 교차 1 (Python)

접근 수학 문제를 푸는 느낌이었는데 마지막엔 그것이 아니었다. 숫자를 주고 풀어라 하면 너무 쉽게 답을 구할 수 있지만 이를 코딩해라 라고 하니 제대로 구현을 못했다. 정답률이 낮은데에는 이유가 있는 법. 굉장히 오래 해메다가 문제를 해결하였다. 이전 문제에서 사용한 CCW를 체크하는 알고리즘을 이용하여 서로 교차하는지 확인할 수 있었다. CCW 알고리즘: 2021.05.06 - [코딩/백준 (Python)] - 백준 11758번: CCW (Python) 백준 11758번: CCW (Python) 접근 마치 수학문제를 푸는 듯한 느낌을 받았다. 가장 먼저 주어지는 두개의 점이 이루는 직선의 식을 구한 후, 세번째 점이 그 직선보다 위에 있는지, 아래에 있는지, 혹은 직선 위에 있는지 구 ca.ramel...

2021. 5. 6. 21:12
코딩/백준 (Python)

백준 11758번: CCW (Python)

접근 마치 수학문제를 푸는 듯한 느낌을 받았다. 가장 먼저 주어지는 두개의 점이 이루는 직선의 식을 구한 후, 세번째 점이 그 직선보다 위에 있는지, 아래에 있는지, 혹은 직선 위에 있는지 구분하여 시계방향, 반시계 방향을 구분하게 된다. (x1, y1), (x2, y2)를 지나는 직선의 방정식은 아래와 같이 구할 수 있다. $$ y - y_1 = \frac{y_2 - y_1}{x_2 - x_1} * (x - x_1) $$ 이 식의 x 값에 x3을 대입하고 구해지는 y가 y3보다 큰지, 작은지, 같은지에 따라 정답을 출력해주면 된다. 코드 import sys point = [list(map(int, sys.stdin.readline().split())) for _ in range(3)] if (point..

2021. 5. 6. 19:58
코딩/백준 (Python)

백준 2166번: 다각형의 면적 (Python)

접근 이번 문제는 쉬운 문제인데 정답률이 낮아서 조금 의아한 문제였다. 예시로 위와 같은 오각형이 주어졌을 때, 다음과 같은 과정을 통해 면적을 구해줄 수 있다. 위의 오각형은 왼쪽의 세개의 사다리꼴을 더해준 뒤, 오른쪽의 두개의 사다리꼴의 면적을 빼줌으로써 구할 수 있다. 하지만 면적을 더하고 빼기 위해 굳이 무언가 다른 조치를 취해줄 필요는 없다. 사다리꼴의 면적을 구하는 공식을 위의 문제에 적용해보면 다음과 같다. $$ area = \frac{(윗변 + 아랫변) * 높이}{2} = \frac{(y2 + y1) * (x2 - x1)}{2} $$ x2 - x1 은 양수이지만 x5 - x4 는 음수여서 자연적으로 빼주어야 하는 면적에는 음수 기호가 적용되게 된다. 심지어 이는 위 문제와 같이 1사분면 뿐..

2021. 5. 5. 22:07
코딩/백준 (Python)

백준 1949번: 우수 마을 (Python)

접근 이전에 풀었던 트리의 독립집합 문제와 매우 유사한 문제였다. 유사 문제: 2021.05.05 - [코딩/백준 (Python)] - 백준 2213번: 트리의 독립집합 (Python) 백준 2213번: 트리의 독립집합 (Python) 접근 dp[i][0] 을 i를 포함한 부분 집합 가중치의 최대값, 그리고 dp[i][1] 을 i를 포함하지 않은 부분 집합 가중치의 최대값으로 지정하고 dfs로 탐색하면서 dp 값을 갱신해줌으로써 문제를 해결해 줄 ca.ramel.be 가중치가 없고, 각각의 마을들을 출력하지 않아 오히려 코드가 더 심플해졌다. 코드 import sys sys.setrecursionlimit(10 ** 9) n = int(sys.stdin.readline()) population = [0]..

2021. 5. 5. 21:27
코딩/백준 (Python)

백준 2533번: 사회망 서비스(SNS) (Python)

접근 바로 전에 풀었던 트리의 독립집합에서 썼던 방법과 비슷하게 DFS 알고리즘을 사용하여 문제를 풀 수 있다. 유사 문제: 2021.05.05 - [코딩/백준 (Python)] - 백준 2213번: 트리의 독립집합 (Python) 백준 2213번: 트리의 독립집합 (Python) 접근 dp[i][0] 을 i를 포함한 부분 집합 가중치의 최대값, 그리고 dp[i][1] 을 i를 포함하지 않은 부분 집합 가중치의 최대값으로 지정하고 dfs로 탐색하면서 dp 값을 갱신해줌으로써 문제를 해결해 줄 ca.ramel.be 유사하게 dp를 사용하면서 dp[i][0] 에는 i 노드가 얼리어답터일 때의 서브 트리에서 얼리어답터의 최소값, dp[i][1] 에는 i 노드가 얼리어답터가 아닐 때의 서브트리에서 얼리어답터의 ..

2021. 5. 5. 21:18
코딩/백준 (Python)

백준 2213번: 트리의 독립집합 (Python)

접근 dp[i][0] 을 i를 포함한 부분 집합 가중치의 최대값, 그리고 dp[i][1] 을 i를 포함하지 않은 부분 집합 가중치의 최대값으로 지정하고 dfs로 탐색하면서 dp 값을 갱신해줌으로써 문제를 해결해 줄 수 있다. 예를 들어 a 노드의 자식노드 b, c 노드가 있을 때, a 노드를 포함하는 부분 집합 가중치의 최대값 dp[a][0] 에는 b 노드를 포함하지 않는 부분 집합 가중치의 최대값 dp[b][1] 과 c노드를 포함하지 않는 부분집합 가중치의 최대값 dp[c][1] 을 더해줄 수 있다. 독립 집합 S 에 a 를 포함할 경우 그와 인접하는 b, c 는 독립 집합 S 에 포함될 수 없기 때문이다. 임의의 노드 1에서 부터 시작하여 dfs 알고리즘을 이용하여 제일 깊은 곳부터 dp를 채워나가가..

2021. 5. 5. 17:34
반응형