코딩테스트/백준_골드
-
[문제] https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net [문제 풀이] https://youtu.be/jZwf4OPlhtk 바킹덕님 영상을 보고 참고해서 풀었었다. 처음에는 cctv의 숫자 1,2,3,4,5일때 모두 함수를 다르게 해서 풀려고 했었으나 해당 영상을 보고 하나의 함수를 이용해 1,2,3,4,5일때 함수(방향), 함수(방향 + 1), 함수(방향 + 2) 식으로 해당 cctv에서의 동작을 파악했다. //x,y는 좌표, di..
[C++][백준 15683] 감시[문제] https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net [문제 풀이] https://youtu.be/jZwf4OPlhtk 바킹덕님 영상을 보고 참고해서 풀었었다. 처음에는 cctv의 숫자 1,2,3,4,5일때 모두 함수를 다르게 해서 풀려고 했었으나 해당 영상을 보고 하나의 함수를 이용해 1,2,3,4,5일때 함수(방향), 함수(방향 + 1), 함수(방향 + 2) 식으로 해당 cctv에서의 동작을 파악했다. //x,y는 좌표, di..
2023.03.31 -
[문제] 4485번: 녹색 옷 입은 애가 젤다지? (acmicpc.net) 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net [문제 풀이] 기존의 BFS 방식에 다익스트라를 이용해서 푸는 문제였다. 기존에 썼던 BFS에서 queue(위치) 방식을 다익스트라에서 사용했었던 우선순위 큐(거리, 정점)을 활용해서 풀자. [회고] 1. 이미 방문했던 곳을 체크하지 않으면 런타임 오류가 뜬다. => visited를 꼭 체크하자. 2. 다익스트라 문제이지만 결국 방문 체크를 할때 쓰는 우선순위큐(거리,정..
[C++][백준 4485] 녹색 옷 입은 애가 젤다지?[문제] 4485번: 녹색 옷 입은 애가 젤다지? (acmicpc.net) 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net [문제 풀이] 기존의 BFS 방식에 다익스트라를 이용해서 푸는 문제였다. 기존에 썼던 BFS에서 queue(위치) 방식을 다익스트라에서 사용했었던 우선순위 큐(거리, 정점)을 활용해서 풀자. [회고] 1. 이미 방문했던 곳을 체크하지 않으면 런타임 오류가 뜬다. => visited를 꼭 체크하자. 2. 다익스트라 문제이지만 결국 방문 체크를 할때 쓰는 우선순위큐(거리,정..
2023.03.28 -
[문제] 1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net [문제 풀이] 다익스트라를 이용한 기초적인 문제이다. pair를 사용해서 graph[현재위치].first 는 목표지점, graph[현재위치].second 는 거리로 입력을 받고 풀었다. 다익스트라 알고리즘을 만들때는 우선순위 큐를 이용해서 오름차순으로 (거리,목표지점)을 만들었고 우선순위 큐의 크기가 0 이상일때는 계속해서 실행이 되며 distance 벡터를 고치도록..
[C++][백준 1916] 최소비용 구하기[문제] 1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net [문제 풀이] 다익스트라를 이용한 기초적인 문제이다. pair를 사용해서 graph[현재위치].first 는 목표지점, graph[현재위치].second 는 거리로 입력을 받고 풀었다. 다익스트라 알고리즘을 만들때는 우선순위 큐를 이용해서 오름차순으로 (거리,목표지점)을 만들었고 우선순위 큐의 크기가 0 이상일때는 계속해서 실행이 되며 distance 벡터를 고치도록..
2023.03.28 -
[문제] 1939번: 중량제한 (acmicpc.net) 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net [문제 풀이] 파라메트릭 서치 + bfs를 이용한 문제. * 나중에 다시 풀어보자. 파라메트릭 서치에 다른 알고리즘을 추가하니까 생각보다 구현단계에서 많이 막혔다. 10억과 1을 이용해서 binary search를 해서 몇이 나올 수 있는지 파악하는 문제. 파라메트릭 서치를 5문제 더 풀어보고 다시 풀어보자! [코드] #include #include..
[C++][백준 1939] 중량제한[문제] 1939번: 중량제한 (acmicpc.net) 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net [문제 풀이] 파라메트릭 서치 + bfs를 이용한 문제. * 나중에 다시 풀어보자. 파라메트릭 서치에 다른 알고리즘을 추가하니까 생각보다 구현단계에서 많이 막혔다. 10억과 1을 이용해서 binary search를 해서 몇이 나올 수 있는지 파악하는 문제. 파라메트릭 서치를 5문제 더 풀어보고 다시 풀어보자! [코드] #include #include..
2023.03.25 -
[문제] 1208번: 부분수열의 합 2 (acmicpc.net) 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net [문제 풀이] 백준 1182번에서 풀었던 풀이에서는 2^20으로 끝날 수 있기에 시간초과가 나지 않지만 해당 문제에서는 2^40의 경우가 나오기 때문에 해당 방식으로는 풀면 시간초과가 걸린다. 그렇기에 오른쪽과 왼쪽으로 우선 나눈 다음에 두가지 경우에서 answer이 될 수 있는 경우를 파악하는 것이 초점이다. 그런데 여기서 두가지 경우에서 answer이 될 ..
[C++][백준 1208] 부분수열의 합 2[문제] 1208번: 부분수열의 합 2 (acmicpc.net) 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net [문제 풀이] 백준 1182번에서 풀었던 풀이에서는 2^20으로 끝날 수 있기에 시간초과가 나지 않지만 해당 문제에서는 2^40의 경우가 나오기 때문에 해당 방식으로는 풀면 시간초과가 걸린다. 그렇기에 오른쪽과 왼쪽으로 우선 나눈 다음에 두가지 경우에서 answer이 될 수 있는 경우를 파악하는 것이 초점이다. 그런데 여기서 두가지 경우에서 answer이 될 ..
2023.03.25 -
[문제] 1717번: 집합의 표현 (acmicpc.net) 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net [풀이 방법] 대표적인 유니온 파인드 문제이다. 최대 가능한 수인 1,000,000을 배열로 만들어두고 해당 배열을 find, merge의 두개의 함수를 이용해서 결합을 시키는 과정을 걸친뒤에 isUnion함수를 이용해서 두개의 값이 연결되어있는지 아닌지 확인하면 된다. *첫번째 함수를 find라고 만들었지만 find라는 함수는 c++에 이미 있는 이름이기 때문에 나..
[C++][백준 1717] 집합의 표현[문제] 1717번: 집합의 표현 (acmicpc.net) 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net [풀이 방법] 대표적인 유니온 파인드 문제이다. 최대 가능한 수인 1,000,000을 배열로 만들어두고 해당 배열을 find, merge의 두개의 함수를 이용해서 결합을 시키는 과정을 걸친뒤에 isUnion함수를 이용해서 두개의 값이 연결되어있는지 아닌지 확인하면 된다. *첫번째 함수를 find라고 만들었지만 find라는 함수는 c++에 이미 있는 이름이기 때문에 나..
2023.03.10