Algorithm/문제풀이(47)
-
백준 5052번
www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 해당 문제는 크게 어렵지는 않았다. trie의 특성을 이용해서 쉽게해결할 수 있다. 우선 문제를 해결하려면 현재의 온전한 문자를 접두사로 사용하는 곳이 있는지 체크해주어야한다. 트라이의 특성을 이용해 이 값을 다 찾으 다음 다음 후보군 노드 중에 NULL이 아닌 값이 있으면 해당 문자가 접두사로 이용되고 있음을 뜻한다. 아래 그림을 보면 간단할 것이다. 911을 찾을 때 911까지 찾은 ..
2021.01.10 -
백준 1644 소수의 연속합
소수의 값으로만 부분 집합을 구해서 연속합을 구하는 문제이다. 부분 집합의 연속합을 구하는 부분에서 당연히 투포인터가 쓰일 것이고 어떻게 소수 모음을 만들어 내는지가 중요한 포인트이다. 필자는 두달전에 한번 풀었고 다시 복습을 통해 풀었는데 소수를 구하는 방법히 전혀 달랐다. 그래서 안좋은 예와 좋은 예 두 코드를 작성해보겠습니다. 안좋은 예 에스트라네스의 체를 활용했는데 상당히 비효율적으로 코드가 작성되었다. 2부터 400000만까지 소수인지 확인하며 하나씩 추가해줬습니다. 더보기 #include #include int arr[4000002]; int setPrimeNumber(int num); int discoverCount(int N); int main(){ int index = 0, N; for(..
2020.07.19 -
백준 2437 저울
사실 이문제는 다른 사람들의 풀이를 봤다. 답을 보고 어떻게 이런생각을 하지...... 라며 감탄을한 기억이 난다. 여러 개의 추의 합 중 만들 수 없는 가장 작은 합을 구하는 문제이다. 추들을 정렬 후 더하면서 처음으로 합보다 큰 수가 나오면 다음 값을 만들 수 없게된다. 그간 합 + 1이 답이된다. #include #include #include using namespace std; int N; vector input(); int main(){ vector scale = input(); int base = 1; for(auto sc : scale){ if(base < sc) break; else base+=sc; } printf("%d", base); } vector input(){ scanf("%d..
2020.07.18 -
백준 1786 - 찾기
백준 1786-찾기는 문자열 모음에서 하나의 문자열이 몇번 등장하는지 찾는 문제이다. KMP 기본문제라서 KMP를 공부하고나서 쉽게 풀었다. 사실 KMP만 알면 누구나 풀 수 있는 문제이다. 찾았을 때 begin+1을 한 이유는 문자열을 탐색할 때 index는 0부터 시작하지만 문제입장에서는 1번째 문자 부터 검사하기 때문이다. #include #include #include #include using namespace std; vector getPi(string hook); vector KMPSEARCH(string base, string hook); int main(){ string base, hook; getline(cin, base); getline(cin, hook); vector result ..
2020.07.18 -
백준 2580 스도쿠
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 학창시절 아빠 폰 게임으로 많이 한 스도쿠이다. 스도쿠를 생각해보면 두가지 조건이 있다. 조건 1. 가로, 세로 줄에 1 ~ 9까지의 모든..
2020.05.06 -
백준 5639 이진 검색 트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, www.acmicpc.net 이진 검색트리의 순회를 활용하여 문제를 풀어보겠습니다. 이 문제의 입력은 이진 검색 트리를 전위순회한 값으로 주어지고 있습니다. ..
2020.04.17