백준4 [LCA] 백준 13116번 30번 (Swift 풀이) 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net [문제] 혹시 2007학년도 대학수학능력시험 수리영역 가형 이산수학 30번 문제를 아는가? 여러분은 수능을 치는 수험생의 마음으로 이 문제를 해결해야만 한다. 하지만 우리는 저작권 위반으로 판사님을 뵙고 싶지 않았기 때문에 이 문제를 직접 수록할 수는 없었다. 아래 링크 중 하나를 클릭해서 pdf 파일을 내려받아 가장 마지막 페이지를 보면, 위의 그림과 아주 유사한 문제가 하나 있을 것이다. 여러분은 바로 그 문제를 해결해야만 한다... 2021. 4. 21. [DP] 백준 2156번 포도주 시식 (Java 풀이) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [문제] 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해.. 2021. 4. 14. 투 포인터 (+ 백준 2003) 오늘은 투 포인터라는 개념을 알아보겠습니다! 투 포인터는 알고리즘.. 이라기보다는 개념이라고 하는게 더 맞는 표현인 것 같아요. 1차원 배열을 두고 start, end 라는 두 개의 인덱스를 사용해서 답을 구하기 때문에 Two Pointer (투 포인터) 라는 이름이 붙었습니다. 사실상 두 개의 인덱스 (포인터) 를 사용한다는 것 외에 특별히 설명할 수 있는게 없어서 오늘은 백준 2003번: 수들의 합 2 를 예시로 투 포인터를 설명해보려 합니다. 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤.. 2021. 2. 25. [플로이드와샬] 백준 11404번 플로이드 (Java) 백준 11404 : https://www.acmicpc.net/problem/11404 정말 기본 플로이드 와샬 알고리즘 그대로 사용하는 문제이다. 그래서 플로이드 와샬 알고리즘을 공부하면서 풀어보았다. 플로이드 와샬은 다대다 최단거리를 계산할 때 사용한다. 그만큼 속도가 느리지만, 모든 노드 사이의 최단 거리를 알아야 하는 문제에 사용한다. 그럼 어떻게 푸는지 한 번 살펴보자. 기본 세팅 N : 노드 개수 dp[N][N] : 모든 노드 사이의 최단 거리를 저장하는 배열 INF = 최대 거리(나는 N*maxlength로 두었다.) dp 초기화 자기 자신으로 가는 거리는 0 그대로 두고, 나머지는 INF로 설정한다. 예시) 간선 입력 간선을 입력받을 때, 기존 dp값과의 min값으로 저장합니다. 플로이드 .. 2020. 8. 28. 이전 1 다음
