빅맥좋아요

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 11403번 경로 찾기를 풀었다. 플로이드 와샬 알고리즘을 처음 사용해봤다. 플로이드 와샬 알고리즘은 모든 노드 사이의 최단 경로를 구할 수 있는 알고리즘이다. 2차원 인접 행렬이 주어졌을 때, 삼중 반복문을 사용해서 경로를 계산하기 때문에 시간복잡도는 O(n^3)이다. 인접 행렬의 값을 이용해서 dist배열을 초기화 시킨 후에 반복문을 수행하면 된다. dist[i][j] 는 i 노드에서 출발해서 j 노드에 도착하는 최단 거리이다. ..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 백준 3020번 개똥벌레를 풀었다. 석순과 종유석을 따로 입력받아서 정렬시킨다. 그 다음 이분탐색을 통해 높이에 따라 부딪히는 횟수를 구하고 min값과 비교한다. 최솟값이 갱신되면 카운트값을 1로 바꾼 후 반복문을 진행하고 최솟값과 똑같은 횟수라면 카운트값을 증가시킨다. 그러면 석순과 종유석을 부딪히는 횟수의 최솟값과 그런 구간의 개수를 구할 수 있다. 아래는 전체 코드입니다. #include #in..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준 11660번 구간 합 구하기 5를 풀었다. 2차원 배열에서 구간 합을 구하는 문제다. 행 별로 누적 합을 구한 뒤에 각 행마다 구간 합 연산을 해주면 된다. 1 2 3 4 1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7 처음 입력 받은 배열이다. 0번째 index는 생략했다. 행 별로 누적 합 연산을 해보면 아래 표처럼 바뀐다..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 백준 11659번 구간 합 구하기 4를 풀었다. 입력으로 받은 배열을 그대로 사용해서 구간 i부터 j까지의 합을 구하려고 하면 시간 초과가 나온다. 최악의 경우 10만개의 수를 10만번 더해야 해서 시간복잡도가 O(N^2)으로 예상된다. 따라서 누적 합을 사용해서 풀었다. 입력 받은 배열 index 0 1 2 3 4 value 5 4 3 2 1 누적 합으로 바꾼 배열 ind..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 백준 9251번 LCS를 풀었다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 처음엔 모든 경우의 수를 찾으려 했는데 안될 것 같아서 고민하다가 다른 사람들..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 백준 2565번 전깃줄 문제를 풀었다. 처음에 그리디 방식으로 가장 많이 겹치게 되는 전깃줄을 지우려 했는데 실패하고 다른 사람의 코드를 찾아봤다. 이 문제는 가장 긴 증가하는 부분 수열로 풀 수 있는 문제였다. 입력으로 받은 전깃줄을 A에 대해 오름차순으로 정렬한 뒤에 B를 보면 된다. 문제의 예제를 기준으로 B는 { 8, 2, 9, 1, 4, 6, 7, 10 } 이 된다. 여기서 없애지 않아도 되는 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 백준 12865번 평범한 배낭 문제를 풀었습니다. 0-1 냅색 문제입니다. arr[i][j]는 배낭 용량이 j일 때, 첫 번째 물건부터 i번째 물건까지 넣어본 최댓값을 가지고 있습니다. i번째 물건의 무게가 j보다 크다면 가방에 물건을 넣을 수 없으므로 arr[i][j]는 arr[i-1][j]이 됩니다. i번째 물건의 무게가 j보다..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 백준 1904번 01타일을 풀었습니다. 간단한 DP문제입니다. 피보나치 수열같이 규칙을 찾고 점화식을 만들면 됩니다. 아래는 전체 코드입니다. #include #include #include using namespace std; #define MOD 15746 int N; int arr[1000000]; int DP(int n) { if (arr[n] != 0) return arr[n]; if (n =..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 백준 2579번 계단 오르기를 풀어봤습니다. DP문제이고 점화식과 base condition을 잘 설정하면 됩니다. 아래는 전체 코드입니다. #include #include #include using namespace std; int N; int stair[300]; int score[300]; int dp(int n) { if (n < 0) return 0; if (score[n] != 0) return s..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 1912번 연속합 문제를 풀어봤습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; int n; int sequence[100000]; int sum[100000]; void dp(int n) { sum[0] = sequence[0]; int result = sum[0]; for (int i = 1; i < n; i++) { sum[i]..