Doby's Lab

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다리를 잇는 경우가 고등학생 때 배우던 조합론: 콤비네이션을 기억해낼 수 있다면 풀릴 수 있는 문제였다. 시간도 0.5초로 짧아서 탑 다운 DP형식으로 구현을 했고 범위는 30 이전이라 문자열의 합은 구현하지 않아도 될 거 같았다. 콤비네이션에 관한 문제를 예전에 풀고, 포스팅해놓았어서 쉽게 풀렸다. https://draw-code-boy.tistory.com/101 [알고리즘] 백준 2407번:..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 > a >> b; map[a].push_back(b); map[b].push_back(a); } bfs(1); int cnt = 0; int minValue = INT_MAX; for (int i = 1; i

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 바로 직전에 사이클을 문제를 풀어서 그런지 쉽게 재귀를 통해 풀 수 있었다. 방문하지 않았던 노드들을 탐색하기 시작한다. 방문하지 않은 노드로 탐색을 시작하면 바로 해당 노드의 방문을 체크한다. 해당 노드가 가리키는 노드가 방문하지 않았으면 재귀를 통해 다음 노드로 간다. 만약 가리키는 노드가 방문이 되어있으면 사이클이라는 ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이번 문제는 계속 시간 초과가 나서 계속 뜯어고칠수록 코드를 점진적으로 진화시키는 기분이 들었다. 이번 문제의 키워드는 '사이클의 유무 판단'이다. 첫 시도 첫 시도에서는 각 노드마다 for문을 통해 '이 노드는 사이클을 형성하는가?'의 여부를 따졌었다. 그 여부는 백트래킹을 통해 두 개의 인자를 받아들여 코드를 짰다. 하지만, 노드의 최대 개수 100,000개가 주어지고, 100,000개 전체가 하나..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리 순회에는 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 제외하고도 여러 가지 순회 방법이 있다. 이번 문제에서는 3가지 순회만 다룬다. 전위 순회(preorder traversal): [루트] [왼쪽 서브 트리] [오른쪽 서브 트리] 중위 순회(inorder traversal): [왼..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 솔루션 1) 로프가 들어올 수 있는 각 중량을 입력받아 내림차순으로 정렬한다. 2) 배열에 맨 마지막엔 들어 올릴 수 있는 최솟값이 들어있을 것이다. 3) 그 최솟값과 배열의 사이즈를 곱하면 배열에 들어있는 로프들로 들어 올릴 수 있는 최대 중량이 된다. 4) 맨 뒤 원소를 pop 하고, 2~3 과정을 반복한다. 5) 그 과정에서 최댓값(최대 중량)을 구한다. [AC 코드] #includ..

https://www.acmicpc.net/problem/1166 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 이번 문제는 간단히 이분 탐색이라기보다 부가적인 요소로 신경 써야 할 것이 많은 문제였다. 자료형 while을 이용한 이분 탐색이 아닌 for문을 이용해야 함 (혹은 double이 아닌 long double로 선언) 출력은 실수형 솔루션 (+참고 https://vision-ary.tistory.com/2) 1) 자료형 l, w, h가 주어졌을 때 최댓값이 1e27이 되어 long long을 ..

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 2차원 배열을 활용하여 BFS로 풀 수 있었다. int emozi[현재 클립보드][현재 화면에 있는 이모티콘 수]; 이렇게 두고 '현재 화면에 있는 이모티콘 수'가 s가 되면 시간이 얼마큼 흘렀는지 출력하게끔 BFS를 짜주면 된다. 3가지 모든 연산의 가중치가 1이라 가능했다. [AC 코드] 의문점 (틀왜맞?): 주어진 범위는 1000 이하가 맞으나 MAX가 1000 + 1인데 되는 이유가 무엇일까..