algorithm

https://www.acmicpc.net/problem/26217 26217번: 별꽃의 세레나데 (Easy) 화관을 만들기 위해서 필요한 씨앗 개수의 기댓값을 출력한다. 정답과의 절대 오차/상대 오차 중 하나가 $10^{-4}$ 이하라면 정답으로 인정된다. 구체적으로, 제출한 답이 $a$이고 정답이 $b$일 때 $\ www.acmicpc.net 기댓값을 구하는 문제이다. 확률론을 배웠다면 쉽게 풀 수 있는 문제라고 생각한다. N개의 꽃이 모두 피어나기 위한 기댓값은 베르누이 시행에서의 성공 횟수의 기댓값을 묻는 문제이다. E = N(1+1/2+1/3+1/4+...+1/N) 으로 조화수열의 형태로 나온다. 위의 식을 간단히 코드로만 작성해주면 끝이다. 코드는 다음과 같다. #include #include..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이런 유형의 문제를 BFS로 다루는 것을 많이 해봤기 때문에 알고리즘은 바로 떠올렸다. 하지만 뱀이나 사다리에 도착했을 때 바로 이동해야하는데 이동하지 않고 방문여부를 따지는 코드를 짜서 살짝 헤맸다. 뱀이나 사다리에 도착했을 때 바로 이동시키니 문제는 바로 풀렸다. 평범한 BFS문제이다. 코드는 다음과 같다. import sys from collec..

During a recent lecture on Digital Logic Design, my professor surprised us with an unexpected assignment. "If your major is computer science," he announced, "you need to know how to implement a Karnaugh map." Initially, I had been working on an algorithm for a different project, but I paused my work and dove into implementing the K-map. At the outset, it proved to be quite challenging. After muc..

https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 최근 백준 open Contest에서 그리디 + 구현 문제를 만났는데 아이디어는 바로 생각했으나 구현을 못해서 못풀었다. 구현력을 늘리고자 이 문제를 풀었다. 각 행과 열에는 최소 하나 이상의 경비병이 있어야한다. 최소로 경비병을 세우려면 몇명을 더 추가로 배치해야하냐는 문제이다. 필자는 2차원 배열을 받은 후에 전치행렬(행과 열을 바꾼 행렬)을 만들어서 문제를 해결하였다. 처음 원래 ..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 처음 보면 그래프 문제라고는 생각하기 힘들수도 있지만, 범위를 보면 하나씩 다 채울만 하겠다 라는 생각이 든다. 숫자가 0부터 9999까지 밖에 없으므로 이전에 했던 과정을 저장하면서 4가지의 과정을 노가다로 다 저장하면 된다. 처음에는 "" 빈 문자열이고 숫자를 받으면 그에대해서 D, S, L, R을 각각 실행한다. 그럼 실행한 숫자까지 필요한 과정으로 각각 D, S, L, ..

https://www.acmicpc.net/problem/12383 12383번: Diamond Inheritance (Large) The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines fo www.acmicpc.net 구글 Code jam에 출제된 문제이다. 그래프의 한 노드에서 시작해서 다른 노드에 도착하는 경로의 가짓수가 최..