전체 글 검색 결과

해당 글 130건

백준 12015 - 가장 긴 증가하는 부분 수열 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 고려사항 dp를 활용한 lis 알고리즘을 사용하면 정답은 구할 수 있다. ( 백준 11053 문제 글 15 - 23 라인 참조) 이러한 2중 for문을 수열의 길이만큼 100만번씩 돌리면 당연히 시간초과. 자신보다 작으면서, 부분 수열의 길이가 제일 긴 memo값을 찾는 for문을 이분탐색 아니면 세그먼트 트리로 구하면 시간단축가능! 그런데 더 간단한 방법을 발견 ( 구글링... ) lo..
BOJ 백준/기타 2020. 11. 10. 18:34

백준 01717 - 집합의 표현

출처 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 www.acmicpc.net 고려사항 유니온-파인드 알고리즘(서로소) 사용 부모 정보가 담기는 배열을 n+1개 선언 두 집합을 합칠 때에는 루트 번호가 작은것이 새로운 루트가 되도록 구현 재귀를 활용한 findNum 구현. 집합을 합칠 때마다, 매번 집합 원소들의 부모를 전부 업뎃해줄 수는 없으니, 집합의 루트였던 원소의 부모 정보를 자기 자신에서 새로운 루트로 업데이트 후, 나중에 ..
BOJ 백준/기타 2020. 11. 9. 18:13

백준 01992 - 쿼드트리

출처 : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 고려사항 2630 번 문제와 유사 압축이 안되어서 4분할을 할 시에는 앞, 뒤에 ( ) 추가 2630 번 처럼 n == 1 인 상황 예외 처리 x 2630 은 비교 대상이 인자로 넘겨 받은 값이라 n이 1이어도 isComplete 아닐 수 있지만, 위 문제는 비교 대상이 n이 1이라면 그 원소 자체이기 때문에 무조건 isComplete 이다! #include #include ..
BOJ 백준/Divide & Conquer 2020. 11. 8. 01:49

백준 02630 - 색종이 만들기

출처 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 고려사항 - 분할정복 기법 사용. - 통일되지 않은 n * n 색종이라면 시작점을 구분지어 n / 2 크기로 분할 후 재검사 ( 25 - 29 라인 ) - color 값을 넘겨 주어 일치여부 판별 - n == 1 일때, 조사중인 색상과 다르다면, 25 - 29 라인 진입 않고, return 0 #include using namespace std; int divi..
BOJ 백준/Divide & Conquer 2020. 11. 8. 00:09

백준 05670 - 휴대폰 자판

출처 : https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 고려사항 - 트라이 자료구조 사용 - 매 테스트 케이스마다 다른 사전 구성이니 꼭 delete root 로 메모리 관리하기. - 단어의 첫 글자를 추론하지 않는다 => 2번째 테스트 케이스처럼 모든 단어가 한 알파벳으로 시작하면 코드의 로직은 총 버튼 클릭수를 정답보다 n 번만큼 뺀 만큼 구한다. root의 nextCnt 가 1이라 +1을 안해주기 때문! 따라서 root->nextCnt == ..
BOJ 백준/문자열 2020. 11. 7. 01:04

백준 14425 - 문자열 집합

출처 : https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 고려사항 - 트라이 자료구조 활용 #include using namespace std; struct trie{ bool term; trie *next[26]; trie(){ term = false; for(int i=0;ifind(str+1); } } } }; int main() { trie *root = new trie(); int n, m, ans = ..
BOJ 백준/문자열 2020. 11. 7. 00:19

백준 05430 - AC

출처 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 고려사항 - string으로 수 배열을 받아서 파싱하는 작업이 복잡! ( 79 - 89 라인) - 빈배열([ ]) 이라면 파싱을 안거치기 위해 예외처리! ( 74 - 77 라인) - 처음에는 덱을 활용하여, R이 나타나면 불리언 flag를 설정하여 pop_front, pop_back 할 지를 결정할라 했지만 www.acmicpc.net/board/view/25456 를 참조하여 직접 큐를 구현했을 때처럼 front, back 인덱스를 관리해주기..
BOJ 백준/기타 2020. 11. 5. 20:16

백준 01021 - 회전하는 큐

출처 : https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 고려사항 - 개념은 덱이지만, 큐를 사용하는 것이 간단하다. - m번 째 수라고 명시하지만, 사실상 1 ~ n 의 수이다. 즉, 특정 수를 뽑았다 해서 몇 번째 수인지 다시 계산 안해도 됨. - 덱으로 구현해서 앞으로 옮길지, 뒤로 옮기지를 계산하려면 앞 서 뽑아 사라진 수들도 고려해야 하기 때문이다. - 일반 큐를 사용하여 front == target 이 될 때까지 ++num, pu..
BOJ 백준/기타 2020. 11. 5. 17:43