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 이어야 배열의 마지막 ..
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학년때 프로그래밍 과목 과제로 나왔었다. 정말 똑같음 접근방법 두개의 배열을 합치는데 배열 당 하나씩 포인터를 갖는다. 정렬되어있는 배열이라고 했으므로 앞부터 하나씩 비교해서 작은 값을 결과 배열에 넣으면된다..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 연결리스트 C++ 커서를 좌우로 옮기거나 커서 앞쪽 문자를 지우거나 커서 왼쪽에 문자를 추가하는 명령들을 수행한 후 최종 문자열을 출력하는 문제이다. 접근방법 이중연결리스트를 만들어서 풀었다. 오답노트 1. 문자열 받을때 배열크기 100001로 설정 '\0' 간과함 2. 출력할때 마지막에 "\n"해줘야함. 결과값이 늘 하나라 안해도 되는줄 알았는데 46분동안 헤매던게 결국 이거였음. 진짜 킹받음. ..
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와 ..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 C++ 하나의 수를 입력할때 마다 저장된 수들 중 중간값을 출력하는 문제 접근방법 최대힙과 최소힙을 모두 사용한다는 아이디어를 얻었다. 정렬된 수열을 반 잘라 앞부분은 최대힙에, 뒷부분은 최소힙에 저장해서 최소힙의 루트노드와 최대힙의 루트노드만 참조하여 중간값을 구하는 것이다. 물론 진짜로 반으로 나눠서 넣으면 안되고 입력받을 때마다 둘 중 한 곳에 push해야한다. ..
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...
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이분탐색 Java (C++로 하려다가 xcode 맛가서 다시 java로 함..) 가장 긴 증가하는 부분 수열 2는 1과 달리 dp로 구하면 안되고 이분탐색으로 구해야한다. N (1 ≤ N ≤ 1,000,000) 수열의 크기가 이렇기 때문에. 접근방법 도저히 모르겠어서 서치해서 공부했다. 핵심 개념은 이 두가지라고 생각하는데 증가하는 수열을 리스트로 선언해두고 배열을 하나씩 탐색하면서 수열의 가장 ..
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택 Java 주어진 수열에서 각 원소마다 본인의 오른쪽에서 가장 가까운 본인보다 큰 수를 출력하는 문제 접근방법 이 문제의 포인트는 바로 스택에 오큰수가 될 수 있는 후보들을 저장하고 있다고 생각하고 스택에서 위에 있는 수가 아래에 있는 수보다 항상 커야한다는 점을 생각해야한다! 따라서 스택의 top이 본인보다 작다면 pop해줘야 한다. 스택에는 나(top이 될)보다 큰 값들만 들어있어야 한다. 그렇지 않으면..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문자열 Java R(순서 뒤집기)과 D(맨 앞 원소 제거)로 이루어진 일련의 명령을 입력받아 최종배열상태 혹은 error를 출력하는 문제 (어머 나 문제 요약 완전 잘해) *error는 배열이 비어있는데 D를 수행할때 발생 접근방법 이 문제의 포인트는 선영이가 주말에 할 일이 없어서 새로운 언어 AC를 만들었다는 것. 은 아니고 R명령이 들어올 때마다 reverse같은 STL을 사용하면 안된다는 것. -> O(n) Deque로 풀어야 합니다. boole..
- Total
- Today
- Yesterday
- 동적계획법
- 다이나믹프로그래밍
- 자바
- 웹크롤링
- 토마토
- 트리
- dfs
- 백트래킹
- 파이썬
- 프로그래머스
- 우선순위큐
- 백준
- 이분탐색
- 스택
- 수학
- 가장 큰 수 프로그래머스
- 브루트포스
- c++
- 최단경로
- 알고리즘
- 투포인터
- Swift
- 게임이론
- 최소힙
- 가장 큰 수 Swift
- 최대힙
- 그리디알고리즘
- dp
- 정렬
- BFS
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |