본문 바로가기

전체 글279

[백준 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.
[백준 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.
[백준 5430] 알고리즘 10^2일차 : AC 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.. 2021. 7. 6.
[백준 1966] 알고리즘 99일차 : 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 구현 Java 흠 단순히 큐 문제라기엔 변수를 좀 고려해야하는 문제였다. 우선순위대로 출력하는데 우선순위가 높은 문서가 올때까지 계속 뒤로 넘기는. 근데 또 포인터로 따라가면서 지정한 문서가 언제 출력되는지 출력하는 문제다. 접근방법 stream.anyMatch써서 뒤에 나보다 우선순위가 높은 문서가 있으면 뒤로 넘기고 아니면 pop했다. 매번 조건이 두가지로 나뉘는데 1. 우선순위가 높은문서가 뒤에.. 2021. 7. 5.
[백준 11656] 알고리즘 98일차 : 접미사 배열 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문자열 Java 자바로 문제 푸는거 진짜 오랜만인 것 같다. 적응하려고 문자열 풀었다. :) 접근방법 문자열 길이만큼 반복문 돌면서 substring 하면서 list에 추가하고 Collections.sort로 리스트 정렬해줬다. 출력 끝 소스코드 import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class S11656 { p.. 2021. 7. 2.
[백준 11286] 알고리즘 97일차 : 절댓값 힙 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐 이번엔 비교로직을 구현해야하는 문제 operator 오버로딩해서 절댓값으로 비교하게 하면 된다. 소스코드 #include #include #include #include using namespace std; struct cmp{ bool operator()(int a, int b){ if( abs(a) == abs(b) ) return a > b; else ret.. 2021. 7. 1.
[백준 1927] 알고리즘 96일차 : 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐 최소 힙이라 비교로직만 바꿔주면 된다. less 대신 greater로 이번엔 greater자리에 비교연산만 구현해서 넣어봤다. 오름차순이라 a b 였다.. 소스코드 #include #include #include using namespace std; struct cmp{ bool operator()(int a, int b){ r.. 2021. 6. 30.
[백준 11279] 알고리즘 95일차 : 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 우선순위 큐 시간제한이 칼같길래..힙 구현해서 풀어야하는줄알고 오랜만에 힙을 다시 공부했는데 STL로 그냥 풀리는 문제였다..기왕한거 최대힙을 구현해서 풀어봤다. 오답노트 시간초과가 한번 났는데 cin tie 끊고 sync_with_stdio false로 하니 풀렸다. 소스코드 priority_queue STL version (AC) #include #include #inclu.. 2021. 6. 29.
[백준 11066] 알고리즘 94일차 : 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 동적계획법 핵심 로직 dp[i][j] = dp[i][mid]+dp[mid+1][j] + 누적합(최상위 노드값) 3중 for문을 도는데 첫번째 반복문은 gap 그러니까 범위다 start~end 범위 크기를 1부터 chapter수인 K-1개까지 반복한다. (그럼 마지막 반복문을 돌면 0~K-1까지를 구할 수 있음) 두번째 반복문은 start~end범위 내에서 start의 위치를 한칸씩 뒤로 .. 2021. 6. 28.
[프로그래머스] 튜플 programmers.co.kr/learn/courses/30/lessons/64065?language=cpp 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 휴 잘풀었다 뿌듯 설명은 나중에,, github.com/sio2whocodes/Programmers/blob/main/Programmers/%EC%88%98%EC%8B%9D%EC%B5%9C%EB%8C%80%ED%99%94.cpp sio2whocodes/Programmers 프로그래머스 문제 풀이. Co.. 2021. 5. 7.
728x90

티스토리툴바