본문 바로가기

백준56

[백준 5639] 알고리즘 125일차 : 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net C++ 트리 트리를 전위순회한 결과를 입력받아 동일한 트리를 후위순회한 결과를 출력하는 문제 접근방법 1. 원래의 트리를 재현하여 후위순회를 구하는 방법 2. 전위순회에서 바로 후위순회를 구하는 방법 중에 2번을 선택했다. 전위순회한 결과가 50 30 24 5 28 45 98 52 60 이거라면 여기서 50 | 30 24 5 28 45 | 98 52 60 이렇게 부모노드 | 왼쪽 서브.. 2021. 8. 24.
[백준 1991] 알고리즘 124일차 : 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net C++ 트리 기본 Of 기본 트리 문제 이 문제는 트리의 세가지 순회 방법 전위순회, 중위순회, 후위순회를 다룬 문제입니다. 접근방법 사용한 자료구조 : 배열 (노드의 왼쪽자식과 오른쪽자식 정보를 담고 있는 2차원 배열) 재귀를 사용하여 자식 노드 방문 근데 이거 왜 실버1씩이나 되는거지 소스코드 #include using namespace std; int adj[26][2]; void pr.. 2021. 8. 23.
[백준 9659] 알고리즘 117일차 : 돌 게임 5 https://www.acmicpc.net/problem/9659 9659번: 돌 게임 5 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net C++ 게임이론 재미있는 게임이긴 하다. 돌의 개수가 주어지는 순간 게임이 끝나버리는 그런 게임. 접근방법 짝수와 홀수의 합의 관계에 대해서 생각해보면 한줄이면 끝날 코드이다. 짝수는 짝수끼리의 합 혹은 홀수끼리의 합으로 이루어진다는 것만 알면된다. 실버2 박탈! 소스코드 #include using namespace std; int main(){ long long N; cin >> N; cout 2021. 8. 9.
[백준 2470] 알고리즘 112일차 : 두 용액 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net C++ 투포인터 음수와 양수가 섞여있는 한 배열에서 두 원소의 합의 절댓값이 최소인 (0에 가까운) 두 원소를 찾는 문제 접근방법 처음엔 시간복잡도 때문에 정렬을 쓰면 안될 것 같았는데 퀵소트정렬을 쓰고 N번만 봐도 되면 통과되는 문제였다. 우선 오름차순 정렬 후 시작점과 끝점을 양 끝에 두고 시작한다. 두 원소의 합을 비교하면서 포인터를 이동하는건데 이때 두 원.. 2021. 7. 29.
[백준 2559] 알고리즘 109일차 : 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net C++ 투포인터 구간의 정해진 크기만큼의 합이 최대인 값을 구하는 문제 접근방법 구간이 정해져있어서 s와 e를 한번에 한칸씩 오른쪽으로 옮기면서 최대합을 갱신하면 된다. 처음에 시작할때 s = 0 , e = k-1 구간의 합을 구해서 sum의 초기값으로 대입한다. 그 후에 e가 n-1보다 작을때까지 반복문을 돌면서 최대합 갱신 while문을 나올때 e = n-1 이어야 배열의 마지막 .. 2021. 7. 26.
[백준 11728] 알고리즘 108일차 : 배열 합치기 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net C++ 투포인터 투포인터문제인데 전의 유형들과는 다른 문제 정렬되어 있는 두 배열을 하나의 정렬된 배열로 (정렬 알고리즘을 쓰지 않고) 합치는 문제 이걸 1학년때 프로그래밍 과목 과제로 나왔었다. 정말 똑같음 접근방법 두개의 배열을 합치는데 배열 당 하나씩 포인터를 갖는다. 정렬되어있는 배열이라고 했으므로 앞부터 하나씩 비교해서 작은 값을 결과 배열에 넣으면된다.. 2021. 7. 23.
[백준 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.
[백준 1806] 알고리즘 105일차 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N arr[i]; } //process int sum = arr[0]; int len = N+1; int startPoint, en.. 2021. 7. 19.
[백준 1655] 알고리즘 104일차 : 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 C++ 하나의 수를 입력할때 마다 저장된 수들 중 중간값을 출력하는 문제 접근방법 최대힙과 최소힙을 모두 사용한다는 아이디어를 얻었다. 정렬된 수열을 반 잘라 앞부분은 최대힙에, 뒷부분은 최소힙에 저장해서 최소힙의 루트노드와 최대힙의 루트노드만 참조하여 중간값을 구하는 것이다. 물론 진짜로 반으로 나눠서 넣으면 안되고 입력받을 때마다 둘 중 한 곳에 push해야한다. .. 2021. 7. 12.

티스토리툴바