코딩테스트/백준_골드
-
[문제] 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [문제 풀이] 구슬탈출 1과 비슷한 문제이지만 현재 구슬을 몇번 움직였는지가 추가가 되었다. 해당 부분을 위해서 변수 1개를 추가로 만들어주고 문제를 풀자. bfs를 이용하면 어렵지 않게 풀리는 문제이지만 해당 문제에서는 visited를 안 써도 되어서 빼고 계산했지만 visited를 추가로 넣으면 이번엔 방문을 못해도 다음엔 방문이 가능한 경우가 생기..
[C++][백준 13460] 구슬 탈출 2[문제] 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [문제 풀이] 구슬탈출 1과 비슷한 문제이지만 현재 구슬을 몇번 움직였는지가 추가가 되었다. 해당 부분을 위해서 변수 1개를 추가로 만들어주고 문제를 풀자. bfs를 이용하면 어렵지 않게 풀리는 문제이지만 해당 문제에서는 visited를 안 써도 되어서 빼고 계산했지만 visited를 추가로 넣으면 이번엔 방문을 못해도 다음엔 방문이 가능한 경우가 생기..
2023.04.14 -
[문제] 2056번: 작업 (acmicpc.net) 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [문제 풀이] 위상정렬 알고리즘을 이용하면 바로 풀리는 문제이다. source로부터 이어지는 숫자들이 저장될 vector graph[n]과 가중치가 저장될 cost[n] 그리고 해당 source로부터 이어진 숫자가 몇개인지 파악할 deg[n] 3가지 요소를 이용하면 바로 풀린다. 자세한 사항은 위상정렬 알고리즘 참조. [회고] (2023.04.06) 어디를 고쳐서 해결이 된지 아직 못찾음. 알고리즘 로..
[C++][백준 2056] 작업[문제] 2056번: 작업 (acmicpc.net) 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [문제 풀이] 위상정렬 알고리즘을 이용하면 바로 풀리는 문제이다. source로부터 이어지는 숫자들이 저장될 vector graph[n]과 가중치가 저장될 cost[n] 그리고 해당 source로부터 이어진 숫자가 몇개인지 파악할 deg[n] 3가지 요소를 이용하면 바로 풀린다. 자세한 사항은 위상정렬 알고리즘 참조. [회고] (2023.04.06) 어디를 고쳐서 해결이 된지 아직 못찾음. 알고리즘 로..
2023.04.06 -
[문제] 1922번: 네트워크 연결 (acmicpc.net) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net [문제 풀이] 크루스칼 알고리즘의 기본 스탠다드 문제이다. 크루스칼 알고리즘을 알고 있다면 바로 풀 수 있는 문제. [회고] 특별히 없음. [코드] #include #include #include using namespace std; vector graph; int parent[1011]; int n,m; int answer; int find(int x){ if(parent[x] == x){ return x; } return parent[x] = find(parent[x]); } void m..
[C++][백준 1922] 네트워크 연결[문제] 1922번: 네트워크 연결 (acmicpc.net) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net [문제 풀이] 크루스칼 알고리즘의 기본 스탠다드 문제이다. 크루스칼 알고리즘을 알고 있다면 바로 풀 수 있는 문제. [회고] 특별히 없음. [코드] #include #include #include using namespace std; vector graph; int parent[1011]; int n,m; int answer; int find(int x){ if(parent[x] == x){ return x; } return parent[x] = find(parent[x]); } void m..
2023.04.05 -
[문제] 1647번: 도시 분할 계획 (acmicpc.net) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net [문제 풀이] 크루스칼 알고리즘을 이용해서 쉽게 풀리는 문제이다. 크루스칼 알고리즘을 사용하고 제일 긴 간선의 가중치를 제거하면 완성! [회고] 처음에 틀려서 어디가 이상한가 했는데 알고보니 양방향 그래프라서 m보다 더 많이 진행을 했는데 크루스칼 알고리즘에서 간선만큼 돌려야하는데 m만큼 돌려서 틀렸었다. 사소한것에 주의를 하자. [코드] #include #inc..
[C++] 도시 분할 계획[문제] 1647번: 도시 분할 계획 (acmicpc.net) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net [문제 풀이] 크루스칼 알고리즘을 이용해서 쉽게 풀리는 문제이다. 크루스칼 알고리즘을 사용하고 제일 긴 간선의 가중치를 제거하면 완성! [회고] 처음에 틀려서 어디가 이상한가 했는데 알고보니 양방향 그래프라서 m보다 더 많이 진행을 했는데 크루스칼 알고리즘에서 간선만큼 돌려야하는데 m만큼 돌려서 틀렸었다. 사소한것에 주의를 하자. [코드] #include #inc..
2023.04.05 -
[문제] 10026번: 적록색약 (acmicpc.net) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [문제 풀이] BFS를 돌리는데 적녹색약인 사람은 R와 G을 일치시켜서 본다. 그렇기에 BFS를 2번 돌리는데 한번은 지금 위치가 R나 G이고 다음 사람도 R나 G이면 똑같이 방문이 가능하게 하고 한번은 아니게 접근을 하였다. 틀린 풀이는 아니었지만 결과적으로 코드가 너무 길어져버리는 문제가 발생했다. BFS함수에 char를 인자로 넣어서 어떻게든 할려고도 했으나 생각보다 구현이 쉽지 않았고 이에 다..
[C++][백준 10026] 적록색약[문제] 10026번: 적록색약 (acmicpc.net) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [문제 풀이] BFS를 돌리는데 적녹색약인 사람은 R와 G을 일치시켜서 본다. 그렇기에 BFS를 2번 돌리는데 한번은 지금 위치가 R나 G이고 다음 사람도 R나 G이면 똑같이 방문이 가능하게 하고 한번은 아니게 접근을 하였다. 틀린 풀이는 아니었지만 결과적으로 코드가 너무 길어져버리는 문제가 발생했다. BFS함수에 char를 인자로 넣어서 어떻게든 할려고도 했으나 생각보다 구현이 쉽지 않았고 이에 다..
2023.04.04 -
[문제] 2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net [문제 풀이] 위상정렬을 살짝 응용한 문제이다. 각 PD들은 제일 처음에 N명을 받을것을 입력하고 그 뒤에 가수들을 n 명 입력받고 각 가수들은 해당 순서대로 나오게 되어 있다. 즉, 앞에 있는 가수가 먼저 나와야 뒤에 있는 가수가 나온다. 3 1 4 3 같은 경우에 처음에 입력받은 값은 3이니 뒤에 3명의 가수가 나오고 1번 가수가 나오면 그 뒤에 4번 가수, 그 뒤에 3번 가수가 ..
[C++][백준 2623] 음악프로그램[문제] 2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net [문제 풀이] 위상정렬을 살짝 응용한 문제이다. 각 PD들은 제일 처음에 N명을 받을것을 입력하고 그 뒤에 가수들을 n 명 입력받고 각 가수들은 해당 순서대로 나오게 되어 있다. 즉, 앞에 있는 가수가 먼저 나와야 뒤에 있는 가수가 나온다. 3 1 4 3 같은 경우에 처음에 입력받은 값은 3이니 뒤에 3명의 가수가 나오고 1번 가수가 나오면 그 뒤에 4번 가수, 그 뒤에 3번 가수가 ..
2023.04.04