본문 바로가기

알고리즘52

[백준 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.
[백준 1655] 알고리즘 104일차 : 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 C++ 하나의 수를 입력할때 마다 저장된 수들 중 중간값을 출력하는 문제 접근방법 최대힙과 최소힙을 모두 사용한다는 아이디어를 얻었다. 정렬된 수열을 반 잘라 앞부분은 최대힙에, 뒷부분은 최소힙에 저장해서 최소힙의 루트노드와 최대힙의 루트노드만 참조하여 중간값을 구하는 것이다. 물론 진짜로 반으로 나눠서 넣으면 안되고 입력받을 때마다 둘 중 한 곳에 push해야한다. .. 2021. 7. 12.
[백준 12015] 알고리즘 102일차 : 가장 긴 증가하는 부분 수열 2 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) 수열의 크기가 이렇기 때문에. 접근방법 도저히 모르겠어서 서치해서 공부했다. 핵심 개념은 이 두가지라고 생각하는데 증가하는 수열을 리스트로 선언해두고 배열을 하나씩 탐색하면서 수열의 가장 .. 2021. 7. 8.
[백준 17298] 알고리즘 101일차 : 오큰수 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이 될)보다 큰 값들만 들어있어야 한다. 그렇지 않으면.. 2021. 7. 7.
[백준 1475] 알고리즘 93일차 : 방 번호 www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net C++ 구현 오늘은 2020-21 동계 알고리즘 스터디 마지막날 하지만 쉬어갑니다 :) 6과 9를 뒤집어서 이용할 수 있다는 점이 포인트인 문제 접근방법 기본적으로는 모든 숫자들이 필요한 개수를 배열에 저장하고 그 중에 가장 큰 값이 필요한 숫자 세트의 개수이다. 근데 6과 9는 예외적으로 생각해줘야하니까 마지막에 6의 개수를 저장하고 있는 곳에 9의 개수를 더하고 2로 나눈후 올림해준다. 그리고 9의 개수를 저장하고 있는 곳의 값을 0으로 바꿔준다. 그리고 나서 0부터 9까지의 숫자 개수 중 가장 .. 2021. 2. 26.
반응형