전체 글

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 배낭 문제랑 똑같은 문제이다. 배낭문제는 2차원 Dp를 이용해서 Buttom-up으로 풀었었는데 배낭문제는 1차원 Dp를 이용하면서 Top-down으로 풀어주는게 더 효율적이다. 배낭문제를 풀어본 사람이라면 알다시피 2차원 배열에서 굳이 값을 채우지 않아도 되는 배열까지 값을 채우기 때문에 메모리와 시간이 Top-down에 비해 오래걸린다. 주어진 시간..

https://www.acmicpc.net/problem/9764 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 중복된 자연수를 사용할 수 없기 때문에 우리가 흔히 아는 동전 문제와 비슷하게 생각할 수 있지만 살짝 다르다. 동전 문제는 button up으로 간단하게 해결 할 수 있다. 하지만 이 문제는 buttom up 보다는 top down이 더 효율적이고 풀이도 간단한 문제이다. 두 풀이를 모두 올리니 공부할 때 참고 하면 되겠다. 먼저 Dp 이므로 큰 문제(우리의 목표)를 작은 문제로 나눠야 한다. 동전 문제에서는 2000원이 되는 경우를 1원이 되..

https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net DP문제로 아주 유명한 문제이다. DP가 큰 문제를 작은 문제로 나눠 생각해서 작은 문제를 통해 큰 문제를 해결하는 방식이므로 문제를 쪼개야한다. 예를 들어 1000원을 만드는 방법의 수를 구해야 한다면, 주어진 동전으로 1원을 만드는 경우의 수, 2원을 만드는 경우의 수, 3원을 만드는 경우의 수... 계속 나아가서 1000원까지 도달하는 방식으로 DP를 구성해 주면 된다...

드디어 백준 등급이 플래티넘이 되었다. 이 solved.ac로 코딩을 처음 시작하고 브론즈 문제를 풀때가 떠오른다. 진짜 아무것도 아는거 없이 가장 입문하기 쉽다는 파이썬으로 시작해서 머리 박치기로 여기까지 왔다. 그때는 코딩에 딱히 관심도 없었고, 컴공으로 진로를 정할지도 몰랐는데 이 솔브닥 사이트 하나가 인생을 바꿨다. 남들 팀플할때 난 알고리즘만 공부했다. 딱히 특별한 이유는 아니고 그냥 알고리즘 푸는게 더 재밌어서 그랬다. 골드1~플래5 구간이 레이팅200을 채워야 해서 정말 폐사구간인데 세그트리 덕분에 잘 넘겼다. 세그트리 안쓰고 풀라 했지만 남은 레이팅 25를 앞두고 군대에서 호국훈련을 한다길래 그냥 세그트리로 밀었다. 플래에 왔으니 이제 내실을 다질 차례이다. 골랜디를 하면서 내실을 다지고(..

https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 문제는 자신의 카드로 상대방의 카드를 나누어 떨어뜨릴 수 있으면 자신이 포인트를 1점 획득하고, 상대방이 내 카드를 나누어 떨어뜨리면 나는 1점을 잃는다. 그 이외의 상황에서는 점수 변화가 없다. 문제는 N이 최대 100,000이라는 것인데 2중 포문으로 모든 플레이어와 한번씩 대결한 결과를 비교하면 시간초과가 난다. (C++은 1초에 10억개 정도의 연산을 수행한다) 그래서 에라토스테네스의 체와 비슷한..

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제는 간단하다, 그냥 2차원 평면에 다각형이 주어졌을 때 넓이를 구하면 된다. 처음 문제를 보면 어떻게 구할지 이리저리 고민할 수도 있지만, 고등학교 수학시간에 신발끈 공식이라고 들어봤을 것이다. 신발끈 공식을 이용하면 무난하게 문제를 풀어 낼 수 있다. 라고 생각했지만 부동소수점을 조심해야한다. C++에서 소수점을 다루기 위해 fixed와 precision함수를 사용했다.우선 precision은 몇자리 까지 표기할 건지..