https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 어제 포스팅 했던 RGB거리 문제와 상당히 비슷한 문제이다. 다이나믹 프로그래밍을 이용하는 문제로 삼각형 위에서부터 최대가 되도록 내려와야한다. 잘못하면 큰수만 따라가면 되는거 아닌가? 라고 생각할 수 있는데 작은 수로 내려가다가 도중에 압도적으로 큰수가 나오면 그 경로가 가장 큰 경우가 되기 때문에 큰수만 따라가면 안된다. 결국 다 해봐야 한다는 뜻이다. Dp == memoization + bruteforce 따라서 완전탐색도 포함되어 있기 때문에 문제를 풀때 DP를..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 가장 최소 비용을 구해야 하므로, 최소~ 하면 그리디나 그래프 탐색이 떠오르지만 앞의 두 알고리즘으로 코드를 짜는게 불가능하다.(가능할 수도 있겠지만 너무 산으로 간다는 뜻) 흔히 DP라고 불리는 다이나믹 프로그래밍이라고 불리는 알고리즘을 사용해야하는 문제로 DP는 그리디나, 수학문제 처럼 정해진 알고리즘을 사용하면 딱 풀리는 알고리즘이 아니라 생각이 필요한 알고리즘이다. D..

1학년 1학기에 노느라 코딩을 하나도 안해서 백준으로 코딩을 작년 9월에 처음 시작했는데 정말 solved.ac의 도움을 많이 받았다. 그 solved에서 오프라인 이벤트를 열어서 고민도 하지 않고 참가했다. 서울 합정역 쪽에 노머글얼리우드 카페에서 했는데, 4월1일~2일 2틀동안 진행했었다. 토요일에 개장할때 바로 가고 싶었지만, 자바 과제를 안해서 2틀차인 일요일에 개장시간에 맞춰서 방문했다. 오픈이 12시였는데 토요일 기준으로 1시간 반만에 하루치 특전이 다 소진되었다는 공지가 올라와서(ㄷㄷ) 다음날에 개장시간에 맞춰서 갔다. 근데...그럼에도 불구하고 줄이 있었다. 그래도 생각보다 짧길래 금방 빠질줄 알았는데....ㅠ 1시간 30분째 입장을 못했다....그리고 거의 내 차례가 다 되었을 때쯤 특전..

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..