컴공과고씨

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 간단 정리 정점이 주어질 때 시작점이 주어지고 그 시작점으로 부터 각 정점의 최단거리를 출력하는 문제. 문제 해결 방법 다익스트라 알고리즘을 사용하여 쉽게 풀 수 있는 문제이다. 다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 여기서 보고 오시면 쉽게 풀 수 있습니다. 전체 코드 1 2 3 4 5 6 7 8 9 ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 간단 정리 방향성 없는 그래프 주어짐. 1번 부터 n 정점까지 최단 거리로 이동함. 조건은 임의로 주어진 두 정점은 반드시 통과해야함. 그리고 한 번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이용가능. 1번에서 n정점으로 이동할 때 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 길이를 출력하라 경로가 없으면 -1을 출력. 문제 해..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 간단 정리 NxN의 모눈 색종이가 있을때 각 칸에 1 또는 0이 적혀있음. 모든 숫자가 같아 정사각형이 되지 않으면 4등분하여 색종이를 나누어가면서 정사각형이 될 때 까지 나누었을 때 잘려진 흰색 종이와 파란색 종이의 개수를 구하시오. *이 문제는 본문에 있는 그림을 보면 더 쉽게 이해가능. 문제 해결 방법 분할 정복(divide and conquer), 재귀를 써..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 간단 정리 여러 도시가 있고 그 도시를 다닐수 있는 여러 버스가 있다. 시작 도시에서 도착 도시까지 비용을 최소로 하는 비용을 구하여라. 문제 해결 방법 다익스트라 알고리즘을 사용하면 풀 수 있는 문제이다. 다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 여기서 한번 어떤 알고리즘인지 보고 오면 어떤 식으로 이 문제..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 간단 정리 N x N 도시에 집과 치킨집이 있음. 한 집과 치킨 집의 거리는 | 집의 행 - 치킨집의 행 | + | 열 - 열 | 이런식으로 계산됨. 각 집과 가장 가까운 치킨 집 사이의 거리를 모두 합한 거리를 도시의 치킨 거리라고 한다. 문제에 M이 주어지는데 M개 만큼 치킨 집을 폐업했을 때 도시의 치킨 거리 가장 작게 되는 도시의 치킨 거리를 구하시오. 문제 해결..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 간단 정리 n * 3 개의 행렬 칸이 있고 각 칸에는 숫자가 적혀 있음. 맨 위 부터 출발 하여 내려오는데 바로 아래와 한 칸 대각선으로만 이동 가능함. 이 때 얻을 수 있는 최대, 최소 점수를 구하시오. 문제 해결 방법 이 문제 같은 경우 위에서 내려온다는 생각을 하지말고 도착할 칸이 위에서 내려오는 점수를 받는 다고 생각하면 쉽다. 이런식으로 첫번째 칸은 점수를 바로 위와 그 옆에서 밖에 올 수 없기 ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 간단 정리 수빈이는 일직성 상에 n이라는 점에 있고 동생은 k라는 점에 있다. 수빈이는 걷거나 순간이동을 하는데 위치가 x일때 걷는다면 1초 후 x-1 or x+1로 이동하고 순간이동하면 0초 후 2*x 만큼 이동할 때 동생을 찾을 수 있는 가장 빠른 시간을 구해라. 문제 해결 방법 저는 bfs를 통해서 해결해 주었습니다. 수빈이의 점에서 일직성 상 범위 내..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 활용한 문제로 bfs를 이용해도 가능하지만 시간 측면으로 볼때 다익스트라가 더 빠르고 나중에 다른 문제를 풀 때 다익스트라로 풀지않고 bfs로 풀면 시간 초과가 걸리는 문제들이 많기 때문에 최단 경로 문제 같은 경우 다익스트라로 풀어주는게 좋다. 다익스트라 알고리즘는 https://hagisilecoding.tistory.com/134 여기서 살..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 간단 정리 지민이가 여러 개의 파티에 감. 파티마다 참석하는 사람이 주어짐. 지민이가 거짓말을 할 건데 진실을 아는 사람이 주어짐. 진실을 아는 사람에게 거짓말을 하면 안됨. 또한 어느 파티에서는 거짓을 듣고 다른 파티에서 진실을 듣는 것도 안됨. 즉, 거짓말이라는 것을 아무도 알아채지 못하게 거짓말을 많이 할 수 있는 파티의 개수를 구하라. 문제 해결 방법 이 문제 같은 경우 유니온 파인드를 쓰면 쉽..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 간단 정리 이 문제는 말 그대로 nCm을 구해주면 되는 문제이다. nCm 이란 서로 다른 n개 중 m개를 뽑는 방법을 말한다. 구하는 법은 n!/m!(n-m)! 이다. 문제 해결 방법 이런 문제 같은 경우 공식을 구현하기 할 수는 있겠지만 답이 겁나게 크게 나오는 걸 볼 수 있다. 즉, c++에서는 저런 큰 수를 정수로 담을 변수가 없기도 하고 공식 구현 하더라도 일일이 다 곱하는 팩토리얼이 있기 때문에 시간초과가 걸릴 수 밖에 없다. 일단 써봐서 규칙을 찾아보는 것이다. 1C0 1C1 2C0 2C1 2C2..