휘발 방지용

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net stl vector에 대해서 더 공부할 수 있던 문제였다. 처음엔 vector v로 선언해서 {X, 순서}를 저장하려고 했는데, 풀다보니까 순서를 굳이 저장할 필요가 없어져서 vector v로 바꾸어 풀었다. 참고로 pair로 선언된 vector를 sort함수로 정렬할때 compare함수를 따로 작성안하면 first 값을 기준으로 정렬 된다고함!!..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법 최대공약수를 구한 방법 두 자연수 A, B의 최대공약수를 구할 땐, 유클리드 호제법을 사용한다. A > B 일때, A를 B로 나눈 나머지를 R이라 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. B > R 이고, A를 R로 나눈 나머지를 R2라 하면, B와 R의 최대공약수는 R과 R2의 최대공약수와 같음을 반복적용한다. 이 과정을 반복하다가, 두 수(C, D(C>D)라 하자)를 나눈 나머지가 0이 되었을 때, 나누는 수 D가 A와 B의..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 다이나믹 프로그래밍(dp)를 이용해서 풀어야 하는 문제이다. 사실 아직 알고리즘 강의를 dp 부분을 안듣긴 했는데 점화식을 쓰는 부분이 마치 대입시절 수리논술을 공부하는 기분이 나서 풀어봤다. 처음 풀이 n번째 계단까지갈려면 아래와 같은 두가지 방법이 있다. n-2번째 계단 점수 + n번째 계단 점수 n-1번째 계단 점수 + n번째 계단 점수 두가지 방법중 max(방법1, 방법2)가 답이 아닐까? 생각했고 그..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 망할 하노이탑을 리뷰할 시간이다. 덕분에 머리에 과부하가 제대로 걸렸다. 백준에서 단계별로 풀어보기를 따라서 풀어보고 있던 터라, 재귀 함수를 이용하는 문제인 줄은 알고 시작했다. 어릴때 모형으로 여러번 가지고 놀았던 기억이 있는데, 도대체 이걸 어떻게 코드로 구현하란건지 막막했다. 그러곤 한창 스트레스 받으며 화장실에 앉아있었는데, 갑자기 머리에 스쳐지나간 생각이 있다. "도대체 이..

https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 아무생각 없이 풀고 제출했다가 50점 받고 뭐지???? 했던 문제이다. int 대신 long 타입을 사용했음에도 불구하고 50점이 나오는데, 그 이유는 31의 제곱수를 계산할때 overflow가 나기 때문이었다. Math.pow()함수를 사용했다면 주의하도록 하자. 이를 해결하기 위해 구글링을 좀 해봤는데 모듈러 연산의 성질 중 분배법칙을 이용하면 overflow를 해결할 수 있다고 한다. 주로..

https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 1번 코드 진짜 무식하게 들이댄 방법이다. 각 숫자 하나마다 일일이 셀프넘버인지 아닌지를 판단하는 코드이다. 최악의 경우(=셀프넘버인 경우) 반복문의 횟수가 최대가 되기 때문에 비효율적인 방법이라 할 수 있다. public class Main { public static boolean is_selfnum(int a) { for(int i = 1; ..

https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 큰 수니까 int가 아니라 long을 쓰면 되겠지?하고 접근했다가 실행시켜보니 답이 음수가 나와 털린 문제이다. 쎄해서 책을 뒤적거려보니, 예제 입력1에서 주어진 두 숫자가 예사롭지 않은 수였다. 9223372036854775807 = 263-1 9223372036854775808 = 263 그리고 long의 저장 가능한 값의 범위는 -263 ~ 263-1 이다. 배열로 직접 노가다 해야하나? 고민하다가 머리에 unsigned long이 스쳐 지나갔는데, 구글링해보니 자바는unsigned를 지원하지 않는다..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net solved.ac에서 브론즈 문제만 건들이다가 맨 처음 건들인 실버 문제이다. 겁도없이 덤볐다가 꽤 고생했다. 시간초과가 떠버려서 내 코드가 틀린건지 맞는건지 알 수도 없는 상황이었다(ㅋㅋㅋ). 어쨌든 채점을 받기 위해선 먼저 시간을 줄여야 했다. 첫번째 시도 : M과 N 사이의 모든 수를 N 이하의 모든 수로 나누어보기 두번째 시도 : M과 N 사이의 모든 수를 N 이하의 모든 소수로 나누어보기 두번째 시도도 시간초과로 채점도..