https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 유형은 Dp라고 되어있지만 내가 아직 Dp를 잘 몰라서 그런지 내가 Dp로 풀었는지 잘 모르겠다. 문제를 읽으면 Dp냄새가 술술 나긴 하는데 그냥 문제 읽고 구현했는데 풀렸다. 코드를 보면 배열 앞에서부터 합을 저장해 나가다가 음수로 빠지면 합을 0으로 바꾼다. 그리고 합이 최대값보다 커지면 최대값을 합으로 바꿔준다. 위의 과정을 배열을 한번 훑으면서 진행하면 연속합중에서 가장 큰 합이 나온다. 코드는..

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