코딩테스트/백준_골드
-
[문제] 1766번: 문제집 (acmicpc.net) 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net [문제 풀이] 기존의 위상정렬에서 우선순위 큐를 살짝 응용하면 쉽게 풀리는 문제였다. 숫자가 낮은것이 앞으로 가야하니 우선순위 큐를 오름차순으로 설정하고 처음에 자신으로 오는 노드가 0일때 result 벡터에 넣지 말고 방문을 하면 그때 넣는 것으로 수정을 하면 쉽게 풀린다. [회고] 아이디어는 간단했으나 우선순위 큐를 생각하는 것이 쉽지가 않았다. 질문 게시판을 보다가 어떤 분..
[C++][백준 1766] 문제집[문제] 1766번: 문제집 (acmicpc.net) 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net [문제 풀이] 기존의 위상정렬에서 우선순위 큐를 살짝 응용하면 쉽게 풀리는 문제였다. 숫자가 낮은것이 앞으로 가야하니 우선순위 큐를 오름차순으로 설정하고 처음에 자신으로 오는 노드가 0일때 result 벡터에 넣지 말고 방문을 하면 그때 넣는 것으로 수정을 하면 쉽게 풀린다. [회고] 아이디어는 간단했으나 우선순위 큐를 생각하는 것이 쉽지가 않았다. 질문 게시판을 보다가 어떤 분..
2023.04.03 -
[문제] 1516번: 게임 개발 (acmicpc.net) 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net [문제 풀이] 백준 1005번(ACM CRAFT) 문제와 90% 이상 흡사하다고 보면 된다. 1 -> 2 / 2 -> 4 / 3 -> 4 로 향하는 그래프가 있을때 4번의 완성이 되는 가장 짧은 시간은 1,2,3번이 완성되는 마지막 시간이고 이것은 1,2,3번의 max타임이라고 보면 된다. [회고] max를 넣어두는 곳을 if문 안에 뒀는데 테케가 맞는걸 보고 생각없이 제출했다. 테케가 생각 못..
[C++][백준 1516] 게임 개발[문제] 1516번: 게임 개발 (acmicpc.net) 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net [문제 풀이] 백준 1005번(ACM CRAFT) 문제와 90% 이상 흡사하다고 보면 된다. 1 -> 2 / 2 -> 4 / 3 -> 4 로 향하는 그래프가 있을때 4번의 완성이 되는 가장 짧은 시간은 1,2,3번이 완성되는 마지막 시간이고 이것은 1,2,3번의 max타임이라고 보면 된다. [회고] max를 넣어두는 곳을 if문 안에 뒀는데 테케가 맞는걸 보고 생각없이 제출했다. 테케가 생각 못..
2023.04.03 -
[문제] 7569번: 토마토 (acmicpc.net) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [문제 풀이] 3차원 bfs 문제이다. 2차원에서 했던걸 응용해서 풀면 생각보다 쉽게 풀린다. 우선 모든 토마토를 입력받을 때 0이 하나도 없다면 0을 출력하고 종료해주자. 만약 토마토가 있다면 dx[4],dy[4],dh[2]를 이용해서 여섯방향으로 매번 큐에서 펼쳐져 나가면서 다음칸에 토마토가 있다면 해당 토마토를 익게 해주자. 그렇게 모든 작업이 끝나고 아직 0인 토마토가 있다면 -..
[C++][백준 7569] 토마토[문제] 7569번: 토마토 (acmicpc.net) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [문제 풀이] 3차원 bfs 문제이다. 2차원에서 했던걸 응용해서 풀면 생각보다 쉽게 풀린다. 우선 모든 토마토를 입력받을 때 0이 하나도 없다면 0을 출력하고 종료해주자. 만약 토마토가 있다면 dx[4],dy[4],dh[2]를 이용해서 여섯방향으로 매번 큐에서 펼쳐져 나가면서 다음칸에 토마토가 있다면 해당 토마토를 익게 해주자. 그렇게 모든 작업이 끝나고 아직 0인 토마토가 있다면 -..
2023.04.03 -
[문제] 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [문제 풀이] 위상 정렬을 이용해서 쉽게 접근이 가능한 문제이다. 위상 정렬에서는 아래와 같은 그림이 있다면 1번부터 접근을 해서 2번과 3번의 수치를 1씩 낮춘다. 그렇게 해서 2와 3이 자신한테 오는 간선이 0이 된다면 이를 큐에 집어 넣고 큐의 사이즈가 0이 될때까지 이를 반복한다. 해당 문제에서 요구하는 w가 작업을 하는데 걸리는 시간이란건 반대로 말하면 w를 시작하기까지 가장 오래 걸..
[C++][백준 1005] ACM Craft[문제] 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [문제 풀이] 위상 정렬을 이용해서 쉽게 접근이 가능한 문제이다. 위상 정렬에서는 아래와 같은 그림이 있다면 1번부터 접근을 해서 2번과 3번의 수치를 1씩 낮춘다. 그렇게 해서 2와 3이 자신한테 오는 간선이 0이 된다면 이를 큐에 집어 넣고 큐의 사이즈가 0이 될때까지 이를 반복한다. 해당 문제에서 요구하는 w가 작업을 하는데 걸리는 시간이란건 반대로 말하면 w를 시작하기까지 가장 오래 걸..
2023.04.03 -
[문제] 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [문제 풀이] 냅색 문제의 대표적인 예이다. DP 공부가 부족하였기에 냅색 공부를 하기위해 동영상을 보고 참고해서 풀었다. https://youtu.be/rhda6lR5kyQ 참고한 동영상. 설명이 친절하셔서 도움이 많이 되었습니다. 해당 영상에서도 나오지만 중요한건 dp[배낭의 갯수][무게]를 만들고 //cost는 해당 배낭의 무게 va..
[C++][백준 12865] 평범한 배낭[문제] 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [문제 풀이] 냅색 문제의 대표적인 예이다. DP 공부가 부족하였기에 냅색 공부를 하기위해 동영상을 보고 참고해서 풀었다. https://youtu.be/rhda6lR5kyQ 참고한 동영상. 설명이 친절하셔서 도움이 많이 되었습니다. 해당 영상에서도 나오지만 중요한건 dp[배낭의 갯수][무게]를 만들고 //cost는 해당 배낭의 무게 va..
2023.04.01 -
[문제] 12919번: A와 B 2 (acmicpc.net) 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net [문제 풀이] 처음에는 recursive()함수를 이용해서 S에서 T로 이동하는 방식으로 풀었는데 해당 방식으로는 시간 초과가 일어났다. 이유는 A에서 B로 가는 경우는 계속해서 2씩 추가되면서 T의 길이인 2^50가지의 경우가 생길 수 있기 때문이다. 하지만 반대로, B에서 A로 가는 경우를 보면 매 경우에 2씩 추가되지가 않는다. B가 앞에 없는 경우가 있거나..
[C++][백준 12919] A와 B 2[문제] 12919번: A와 B 2 (acmicpc.net) 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net [문제 풀이] 처음에는 recursive()함수를 이용해서 S에서 T로 이동하는 방식으로 풀었는데 해당 방식으로는 시간 초과가 일어났다. 이유는 A에서 B로 가는 경우는 계속해서 2씩 추가되면서 T의 길이인 2^50가지의 경우가 생길 수 있기 때문이다. 하지만 반대로, B에서 A로 가는 경우를 보면 매 경우에 2씩 추가되지가 않는다. B가 앞에 없는 경우가 있거나..
2023.03.31