본문 바로가기

알고리즘/백준22

99클럽 코테 스터디 4일차 TIL (24479: 알고리즘 수업 - 깊이 우선 탐색 1) 문제https://www.acmicpc.net/problem/24479 학습 키워드DFS 시도DFS 풀이각 정점의 출력 순서를 저장해야하기 때문에 각 정점의 순서를 저장하고 있는 visitedOrders와 순서를 기록하는 order를 선언한다.각 정점마다 연결된 간선을 저장하기 위해 map을 선언한다.모든 정점을 map에 추가하고, u와 v를 입력 받아 map에 추가한다. 양방향으로 추가하기 위해 u에 v를, v에 u를 추가한다.통해 모든 정점을 깊이 우선 탐색으로 탐색하면서 visitedOrders에 저장한다.visitedOrders에 저장된 정점의 모든 순서를 출력한다. 이때 방문하지 않은 정점은 초기값인 0으로 저장되어 있기 때문에 문제에서 출력으로 요구하는 '시작 정점에서 방문할 수 없는 경우 0.. 2024. 10. 31.
99클럽 코테 스터디 2일차 TIL (11561번: 징검다리) 문제https://www.acmicpc.net/problem/11561학습 키워드이진 탐색 시도(시간초과) 1부터 차례대로 더하면서 n이 됐을 때, 더한 횟수 구하기완전 탐색?이렇게 구하게 되면 입력값으로 최대 10^16이 들어온다고 할 때, 10^8정도 소요된다. 모든 테스트케이스가 다 성공하는데 시간제한이 1초이므로 최악의 경우 한 개의 테스트만 돌면 끝나기때문에 시간초과가 발생한다.(성공) 등차수열 공식과 이진 탐색을 사용해서 값 구하기이진 탐색을 통해 (n * (n + 1)) / 2가 주어진 징검다리의 마지막 칸 보다 작거나 같은 경우, 밟았다고 판단하고 값을 저장해나가면서 가장 큰 값을 구하면 된다. 풀이import java.util.*;public class Main11561 { private.. 2024. 10. 29.
99클럽 코테 스터디 1일차 TIL (1072번: 게임) 문제https://www.acmicpc.net/problem/1072학습 키워드이진 탐색 시도(시간초과) 지금까지 진행했던 게임만큼 1씩 더해가면서 승률이 바뀔 때까지 계산하기주어진 게임 횟수(x)가 10, 이긴 게임(y)이 8인 경우에는 게임 횟수가 20일 때까지 승률이 변하는지 계산한다.입력으로 주어지는 게임 횟수(x)의 최대값이 1 ≤ X ≤ 1,000,000,000 이기 때문에 최대 10억번 계산하므로 10초가 걸리게 되는데 시간 제한이 2초이므로 시간초과가 된다.(불가능한듯?) 1을 더했을 때 추가되는 소수점을 계산하고 승률이 바뀌는 지점을 찾는다.float와 double은 부동소수점을 사용하기 때문에 소수점의 정밀도가 떨어져서 자세한 값을 찾기가 어렵다.BigDecimal을 사용하는 방법으로도.. 2024. 10. 28.
백준 30461: 낚시 들어가기전이 글의 풀이 방식은 누적합과 구간합을 이용한 방식입니다. 누적합과 구간합을 이미 알고 계신 분들은 쉽게 이해하실 수 있을 겁니다.만약 누적합과 구간합을 모르신다면 공부하고 오시는 걸 추천드립니다. (유튜브 링크)문제 설명문제 바로가기 30461번: 낚시첫째 줄에 일감호의 크기를 나타내는 정수 $N,M$과 건덕이가 낚싯대를 휘두를 횟수 $Q$가 공백으로 구분되어 주어진다. $\left( 1\leq N,M\leq 2\, 000;\ 1\leq Q\leq 300\, 000 \right)$ 둘째 줄부터 $N$개의 줄에 걸www.acmicpc.net문제 이해(a, b)에 미끼가 존재할 경우, (1, b) + (2, b) + (3, b) + ... + (a, b) 의 물고기를 사로잡는다.낚시줄을 한 바퀴 .. 2024. 4. 27.

티스토리툴바