코딩테스트/백준_골드
-
[문제] 1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [문제 풀이] 플로이드 워셜을 이용해서 풀도록 하자. 플로이드 워셜 알고리즘을 사용한 뒤에 행렬에서 [i][i]가 존재한다면 자기 자신으로 돌아오는 사이클이 있다는 의미이므로 i,i 를 모두 확인해 준 뒤 min값을 꺼내자. *주의 사항 : 만약 사이클이 없다면 -1을 출력하자. *주의 사항2 : 거리는 10,000 이하이고 마을은 400까지 있으니 4,000,000 까지 갈 ..
[C++][백준 1956] 운동[문제] 1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [문제 풀이] 플로이드 워셜을 이용해서 풀도록 하자. 플로이드 워셜 알고리즘을 사용한 뒤에 행렬에서 [i][i]가 존재한다면 자기 자신으로 돌아오는 사이클이 있다는 의미이므로 i,i 를 모두 확인해 준 뒤 min값을 꺼내자. *주의 사항 : 만약 사이클이 없다면 -1을 출력하자. *주의 사항2 : 거리는 10,000 이하이고 마을은 400까지 있으니 4,000,000 까지 갈 ..
2022.10.29 -
[문제] https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net [문제 풀이] 신발끈 공식을 알면 비교적 쉽게 풀 수가 있던 문제였다. 다각형의 넓이를 구하는 방법은 삼각형을 만든 뒤에 해당 삼각형의 넓이를 모두 더하면 해당 넓이가 된다는 것을 우리들은 배웠다. 사각형의 경우는 삼각형 2개를 합쳐서 만들어진것이고 오각형의 경우에는 삼각형 3개가 합쳐진 경우이다. 즉, 해당 다각형을 구하기 위해서는 꼭지점 1개를 모두 공유하는 삼각형들의 모든 넓이를 더하면 된다. 하지만, 단순히..
[C++][백준 2166] 다각형의 면적[문제] https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net [문제 풀이] 신발끈 공식을 알면 비교적 쉽게 풀 수가 있던 문제였다. 다각형의 넓이를 구하는 방법은 삼각형을 만든 뒤에 해당 삼각형의 넓이를 모두 더하면 해당 넓이가 된다는 것을 우리들은 배웠다. 사각형의 경우는 삼각형 2개를 합쳐서 만들어진것이고 오각형의 경우에는 삼각형 3개가 합쳐진 경우이다. 즉, 해당 다각형을 구하기 위해서는 꼭지점 1개를 모두 공유하는 삼각형들의 모든 넓이를 더하면 된다. 하지만, 단순히..
2022.10.29 -
[문제] 2458번: 키 순서 (acmicpc.net) 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [문제 풀이] 플로이드-워셜을 사용해서 풀어보도록 하자! 플로이드-워셜을 사용해서 만일 갈 수 있는 위치에 있다면 i에서 j로 가는 길을 1로 두자. 그렇다면 i에서 자신을 제외한 나머지 숫자들이 모두 채워져 있다면 자신의 위치를 정확히 알 수가 있고 아니라면 알 수가 없다. [코드] #include #include using namespace std; int n,m; int student[501][501];..
[C++][백준 2458] 키 순서[문제] 2458번: 키 순서 (acmicpc.net) 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [문제 풀이] 플로이드-워셜을 사용해서 풀어보도록 하자! 플로이드-워셜을 사용해서 만일 갈 수 있는 위치에 있다면 i에서 j로 가는 길을 1로 두자. 그렇다면 i에서 자신을 제외한 나머지 숫자들이 모두 채워져 있다면 자신의 위치를 정확히 알 수가 있고 아니라면 알 수가 없다. [코드] #include #include using namespace std; int n,m; int student[501][501];..
2022.10.28 -
[문제] 11403번: 경로 찾기 (acmicpc.net) 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [문제 풀이] 플로이드-워셜 알고리즘을 통해서 풀어보도록 하자! 플로이드-워셜 알고리즘은 이전에 풀었던 플로이드 문제를 통해서 알아보도록 하자. 다만 플로이드 워셜의 경우에는 최소값을 찾지만 해당 문제에서는 경로가 있기만 하면 1로 바꾸도록 하자. [코드] #include using namespace std; const int INF = 1000000; int n; int graph[101][101]; void floid(){ for(int k =..
[C++][백준 11403] 경로 찾기[문제] 11403번: 경로 찾기 (acmicpc.net) 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [문제 풀이] 플로이드-워셜 알고리즘을 통해서 풀어보도록 하자! 플로이드-워셜 알고리즘은 이전에 풀었던 플로이드 문제를 통해서 알아보도록 하자. 다만 플로이드 워셜의 경우에는 최소값을 찾지만 해당 문제에서는 경로가 있기만 하면 1로 바꾸도록 하자. [코드] #include using namespace std; const int INF = 1000000; int n; int graph[101][101]; void floid(){ for(int k =..
2022.10.28 -
[문제] 11404번: 플로이드 (acmicpc.net) [문제 풀이] 플로이드-워셜(플로이드 와샬)에 대해서 알아보도록 하자! 해당 문제를 예시로 플로이드 와샬을 하는 방법에 대해서 알아보자. 문제의 조건에 맞는 행렬을 우선 만들어보자. 2 3 1(2) 10 2 8 1(2) 10(1) 3 7 4 여기에서 가장 짧은 거리를 알아야 하니까 원소에서 중복되는 값은 짧은 값만 남겨주자. 2 3 1 10 2 8 1 1 3 7 4 그러면 이제 i 에서 j 로 한번도 걸치지 않고 바로 가는 그래프에 대해서 알게 되었다. 해당 그래프를 이용해서 n번을 걸쳐서 가는 루트중에 가장 짧은 루트를 알아보자 i, j 에서 1을 통해서 걸쳐가는 루트에 대해서 알아보도록 하자. [i][1] + [1][j]는 곧 i에서 j로 갈 ..
[C++][백준 11404] 플로이드[문제] 11404번: 플로이드 (acmicpc.net) [문제 풀이] 플로이드-워셜(플로이드 와샬)에 대해서 알아보도록 하자! 해당 문제를 예시로 플로이드 와샬을 하는 방법에 대해서 알아보자. 문제의 조건에 맞는 행렬을 우선 만들어보자. 2 3 1(2) 10 2 8 1(2) 10(1) 3 7 4 여기에서 가장 짧은 거리를 알아야 하니까 원소에서 중복되는 값은 짧은 값만 남겨주자. 2 3 1 10 2 8 1 1 3 7 4 그러면 이제 i 에서 j 로 한번도 걸치지 않고 바로 가는 그래프에 대해서 알게 되었다. 해당 그래프를 이용해서 n번을 걸쳐서 가는 루트중에 가장 짧은 루트를 알아보자 i, j 에서 1을 통해서 걸쳐가는 루트에 대해서 알아보도록 하자. [i][1] + [1][j]는 곧 i에서 j로 갈 ..
2022.10.28 -
[문제] 1300번: K번째 수 (acmicpc.net) 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net [문제 풀이] 시간 초과와 메모리 제한으로 어떻게 접근해야 할지 한참을 헤맸다. priority queue를 써서 풀려고 했으나 N * N 으로 모든 원소를 접근할려니 바로 시간초과가 날 수밖에 없었다. 하지만 2가지 정보를 알면 생각보다 쉽게 문제를 풀 수가 있다. 1. k이하의 숫자가 몇개가 있는지 파악을 해보자. 1 2 3 1 1 2 3 2 2 4 6 3 3 4 9 3 ..
[C++][백준 1300] K번째 수[문제] 1300번: K번째 수 (acmicpc.net) 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net [문제 풀이] 시간 초과와 메모리 제한으로 어떻게 접근해야 할지 한참을 헤맸다. priority queue를 써서 풀려고 했으나 N * N 으로 모든 원소를 접근할려니 바로 시간초과가 날 수밖에 없었다. 하지만 2가지 정보를 알면 생각보다 쉽게 문제를 풀 수가 있다. 1. k이하의 숫자가 몇개가 있는지 파악을 해보자. 1 2 3 1 1 2 3 2 2 4 6 3 3 4 9 3 ..
2022.10.24