본문 바로가기

분류 전체보기247

[백준 9251] 알고리즘 111일차 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net C++ DP 최장 공통 부분 수열 두 문자열 ACAYKP CAPCAK가 있으면 공통된 부분수열의 최장길이를 출력하는 문제 ACAYKP CAPCAK의 경우 ACAYKP CAPCAK 로 ACAK이므로 4이다. 접근방법 부분수열이 양 문자열에서 시작하는 위치도 끝나는 위치도 문자열의 처음부터 끝부분까지 고려되어야 하기 때문에 2차원배열을 사용하여 DP로 풀어.. 2021. 7. 28.
[백준 11000] 알고리즘 110일차 : 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net C++ 그리디 알고리즘, 우선순위 큐 강의 시간표 (시작시간, 종료시간)이 주어지고 최소한의 강의실을 배정하여 강의실 개수를 출력하는 문제 접근방법 그리디 문제 중에 이런 문제는 처음 봐서 좀 헤맸다. 처음엔 브루트포스인가 싶어서 이중포문으로 돌렸었는데 역시 시간복잡도 때문에 아니었던 것 같다. 우선순위큐 두개를 사용해서 풀이한다. 하나는 모든 강의 시간표가 시작시간의 오름차순으로 정렬되어있다(시작시간이 같을 경우 종료시간 오름차순) : pq .. 2021. 7. 27.
[백준 2559] 알고리즘 109일차 : 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net C++ 투포인터 구간의 정해진 크기만큼의 합이 최대인 값을 구하는 문제 접근방법 구간이 정해져있어서 s와 e를 한번에 한칸씩 오른쪽으로 옮기면서 최대합을 갱신하면 된다. 처음에 시작할때 s = 0 , e = k-1 구간의 합을 구해서 sum의 초기값으로 대입한다. 그 후에 e가 n-1보다 작을때까지 반복문을 돌면서 최대합 갱신 while문을 나올때 e = n-1 이어야 배열의 마지막 .. 2021. 7. 26.
[백준 11728] 알고리즘 108일차 : 배열 합치기 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net C++ 투포인터 투포인터문제인데 전의 유형들과는 다른 문제 정렬되어 있는 두 배열을 하나의 정렬된 배열로 (정렬 알고리즘을 쓰지 않고) 합치는 문제 이걸 1학년때 프로그래밍 과목 과제로 나왔었다. 정말 똑같음 접근방법 두개의 배열을 합치는데 배열 당 하나씩 포인터를 갖는다. 정렬되어있는 배열이라고 했으므로 앞부터 하나씩 비교해서 작은 값을 결과 배열에 넣으면된다.. 2021. 7. 23.
[백준 1406] 알고리즘 107일차 : 에디터 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 연결리스트 C++ 커서를 좌우로 옮기거나 커서 앞쪽 문자를 지우거나 커서 왼쪽에 문자를 추가하는 명령들을 수행한 후 최종 문자열을 출력하는 문제이다. 접근방법 이중연결리스트를 만들어서 풀었다. 오답노트 1. 문자열 받을때 배열크기 100001로 설정 '\0' 간과함 2. 출력할때 마지막에 "\n"해줘야함. 결과값이 늘 하나라 안해도 되는줄 알았는데 46분동안 헤매던게 결국 이거였음. 진짜 킹받음. .. 2021. 7. 22.
[백준 2003] 알고리즘 106일차 : 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투포인터 C++ 대략 25분 수열의 부분합 중 M을 만족시키는 경우의 수를 출력하는 문제이다 접근방법 투포인터를 사용해서 합이 M보다 작으면 -> end를 오른쪽으로 이동시키고 크면 -> start를 오른쪽으로 이동시킨다. M과 같으면 경우의 수(cnt)를 1증가시키면서 end를 오른쪽으로 이동시킨다. 오답노트 구간의 합이 M보다 큰 경우 중 start와 .. 2021. 7. 21.
[백준 1806] 알고리즘 105일차 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N arr[i]; } //process int sum = arr[0]; int len = N+1; int startPoint, en.. 2021. 7. 19.
[백준 1655] 알고리즘 104일차 : 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 C++ 하나의 수를 입력할때 마다 저장된 수들 중 중간값을 출력하는 문제 접근방법 최대힙과 최소힙을 모두 사용한다는 아이디어를 얻었다. 정렬된 수열을 반 잘라 앞부분은 최대힙에, 뒷부분은 최소힙에 저장해서 최소힙의 루트노드와 최대힙의 루트노드만 참조하여 중간값을 구하는 것이다. 물론 진짜로 반으로 나눠서 넣으면 안되고 입력받을 때마다 둘 중 한 곳에 push해야한다. .. 2021. 7. 12.
[백준 10866] 알고리즘 103일차 : 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 큐, 덱 Java 덱 사용 이해 문제 접근방법 자바에서 ArrayDeque 사용하기 덱의 개념을 익히고 실습하는 문제. (입력 크기가 너무 작아서 비효율적인 구현으로도 통과가 되지만, 가급적이면 연산 당 시간 복잡도가 O(1)이도록 구현해 주세요.) 문제 설명에 이렇게 적혀있어서 덱 구현해서 풀어야 하나 했지만. 모든연산이 O(1)이긴 한걸요. 소스코드 import java.io... 2021. 7. 9.

티스토리툴바