백준

백준 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..

백준 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원에서 빼준다. 이후엔 ..

백준 1715번 자바 ☆

문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 우선순위 큐 우선순위 큐를 알기전에 큐라는 자료구조를 먼저 알아야한다. 큐는 선입선출(FIFO) 형태의 자료구조이다. 먼저 들어오면 먼저 나간다. 음료를 먹을 때 빨대를 생각하면 쉽다. 먼저 빨아들인 음료가 내 입속으로 먼저 온다. 그럼 우선순위 큐가 뭔지 짐작이 간다. 큐는 큐지만 우선순위가 있는 큐다. 그냥 구현을 하게 되면 오름차순으로 정렬이 된다. 해당 문제에 그대..

백준 1300번 자바 ☆

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 1. 시간복잡도와 공간복잡도 시간복잡도 : 해당 문제에서 N의 최대 값이 100,000이다. 시간 복잡도의 경우 2초의 시간이 주어지는데, 약 2억번의 연산이 가능한 시간이다. 그러므로 O(N2)의 시간복잡도를 가지는 알고리즘을 쓰면 시간초과이다. 공간복잡도 : 배열A는 2차원 배열로 N*N의 크기를 갖고 배열B의 길이는 N*N이다. int형 배열을 만든다고 가..