전체 글

백준 1456번 자바 ☆

문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 1. 접근 방식 에라토스테네스의 체를 이용해 소수를 구하고 해당 문제 조건에 맞는 값을 구하면 된다. 구현 자체는 어렵지 않았지만 A,B의 범위 값이 너무 크기때문에 long 타입으로도 못담는 숫자가 생긴다. 쉽게 예를 들자면 long의 최대 값이 100이고, B의 값이 81이라고 가정했을 때 소수 7의 3제곱은 343이므로 long의 범위를 넘기에 오버플로우가 발생한다. 엉뚱한 값이 생성되면서 조건을..

백준 1929번 자바

문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1. 소수 구하기 특정 범위의 소수를 구하기 위해선 여러방법이 있겠지만 특히 자주 사용되는 방법이 '에라토스테네스의 체' 이다. 원리는 간단하다 첫번째 소수인 2부터 2의 배수를 삭제한다. 그 다음 삭제 되지 않은 수인 3의 배수를 삭제하고 그 다음부터는 마찬가지다. 상세한 설명 및 예시는 아래에 있다. https://terms.naver.com/entry.naver?docId=1179083&cid=40942&categor..

TIL - 0214

1. 자바 플레이 그라운드 with TDD, 클린코드 람다 사용법 람다 사용이유(간결,중복제거) 익명 클래스 활용 2. 혼자서 공부하는 컴퓨터 구조+운영체제 CPU의 작동원리(ALU, 제어장치, 레지스터) ALU(산술논리장치) : 제어장치로부터 제어신호(수행할 연산)를 전달받고, 레지스터로부터 데이터(피연산자)를 전달 받아 연산을 수행, 결과는 레지스터에 저장 후 메모리로 이동 제어장치 : 명령어 레지스터로부터 명령어를 전달 받아 해석하여 제어신호를 발생시킨다. CPU내부(ALU, 레지스터), CPU외부(메모리, I/O)와 제어버스를 이용해 제어신호를 주고 받는다. 레지스터 : 메모리에서 가져온 명령어, 데이터를 임시저장하기 위한 공간이고 ALU의 연산결과를 저장하기 위한 저장소. 프로그램 카운터의 값을..

백준 1744번 자바 ☆

문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. 접근 방식 그리디 문제를 여러번 풀면서 dp문제들과 마찬가지로 처음 접근 방식이 매우 중요하다고 느꼈다. 해당 문제도 처음 접근 방식이 타당하지 못해 많이 헤맨 문제다. 처음 나의 접근은 모든 수를 우선순위 큐에 삽입 후 분기별로 순차적으로 묶어 나가며 해결을 했다. 또 전체 배열의 길이가 홀수이냐 짝수이냐로 나눠서 두가지 중 큰 값을 선택하게 했다. import java.io.Buf..

백준 11047번 자바

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 1. 접근방식 전형적인 그리디 방식의 문제다. 그리디 문제에서 가장 중요한 점은 매 분기에서 가장 좋은 선택을 하며, 이전 선택의 결과가 이후 선택의 결과에 영향을 미치지 않는다는 것이다. 해당 문제의 경우 임의의 동전의 가치 Ai로 K원을 나눴을 때 몫이 1이상인 경우를 먼저 찾은 뒤 몫 x Ai원을 K원에서 빼준다. 이후엔 ..