algorithm

드디어 백준 등급이 플래티넘이 되었다. 이 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은 몇자리 까지 표기할 건지..

https://www.acmicpc.net/problem/25318 25318번: solved.ac 2022 첫 번째 경우에서 첫 번째 의견은 마지막 의견에 비해 약 $834$일 $6$시간$\,\approx 2.286$년 전 의견이므로, 가중평균은 \[X\approx\frac{\max\left( 0.5^{2.286},0.9^1 \right)\times 24+\max\left( 0.5^0,0.9^0 \right)\times 18}{\ www.acmicpc.net 맨처음에 문제를 봤을 때 C++로 "/"와 ":"를 어떻게 나눌까 고민이 많았다. 파이썬에서는 그냥 split을 사용하면 편하게 다룰수 있었는데 확실히 C++은 문자열 다루는 것이 좀더 어렵다. seperator로 분리해서 볼까도 했는데 굳이 그러..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 딱봐도 DP문제이다. 실버DP문제는 꽤 많이 풀어서 그런지 풀이가 한눈에 보인다. 해당 스티커를 선택할 수 있는 경우를 모두 고려해서 최대값을 dp값으로 저장하면 된다. 위의 경우를 점화식으로 작성하기만하면 끝이다. 스티커가 2줄이라 2차원 배열 쓰면 끝. 코드는 다음과 같다. #include #include #include #include #include #include #includ..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복을 이용한 거듭제곱이다. 예제를 봐보자. 10의 11승을 구해야하는데 원래 같았으면 10을 11번 곱해서 구했을 것이다. 하지만 분할정복을 사용하면 4번의 계산으로 구할 수 있다. ans = 10 * 10^2 * 10^83번처럼 보이지만 10^2에서 10^8까지 가는데 반복문이 2번돌기 때문에 4번이라고 하였다.10^11 = 10 * (10^5)^2 = 10 * (10 * (10^2)^2)^2 = 10 * (10 * (10 * 10)^2)^2위와 같이 제..