분류 전체보기

백준 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형 배열을 만든다고 가..

백준 2343번 자바 ☆

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 접근방식 이전에 풀었던 문제와 마찬가지로 이분탐색으로 접근해야 한다. 다만 문제에 대한 이해도가 떨어져 이분탐색할 범위를 이상하게 잡아 문제 해결에 어려움을 겪었다. 먼저, 블루레이 최소크기가 9이고 최대크기가 45임을 이해해야한다. 최소크기가 9인 이유는 나열된 강의들 중 가장 긴 강의가 9길이의 영상이기 때문이다. 즉, 각 개별의 영상크기가 가장 마지막 영상의 길이인 9보다 작기 때문이다...

백준 1920번 자바

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1. 이진탐색? 이분탐색? 이진, 이분 탐색 둘다 의미는 비슷하기에 크게 구분하지 않아도 된다. 이진 탐색 : 찾으려는 값(a)가 배열(arr)에 존재하는지 찾을 때 arr의 중간값과 비교를 하면서 탐색하는 방법이다. 예를 들어 찾으려는 값(a)이 2라고 할때, 아래 배열(arr)의 중간값(mid)인 4와 비교를 한다. 1 2 3 4 5 6 7..