휘발 방지용

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

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. (이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...) 바킹독의 실전 알고리즘 0x01강 링크 바킹독의 실전 알고리즘 0x02강 링크 강의내용 복습 시간복잡도와 공간복잡도 시간 제한과 메모리 제한에 대한 내용. 컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있다. 즉, 문제에서 시간제한이 1초라고 한다면, "당신의 프로그램은 3-5억 번의 연산 안에 답을 내고 종료되어야 한다"는 의미! 시간복잡도 입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관관계 연산의 수행 횟수는 입력된 개수(n)에 의해 결정..

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 이하의 모든 소수로 나누어보기 두번째 시도도 시간초과로 채점도..