백준56 [백준 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. [백준 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. [백준 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. 이전 1 2 3 4 5 6 7 다음
