본문 바로가기

백준51

[백준 14500] #129 : 테트로미노 (C++) https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net C++ 구현, 브루트포스 사진에 보이는 5개의 테트로미노를 회전, 대칭 시켜서 점수가 적혀있는 판에 놓았을 때 테트로미노가 놓여진 칸들의 점수의 합의 최대값을 구하는 문제이다. 접근방법 브루트포스로 풀었다. 나올 수 있는 모든 도형의 모양을 구하고 (0,0) 기준으로 좌표를 구한다음 모든 도형에 대해 일일이 어디에 두면 가장 큰 값이 나오고, 그 중에 어떤 도형이 가장 큰 값을 내는지 찾았다. 도.. 2021. 10. 11.
[백준 9660] 알고리즘 128일차 : 돌게임 6 https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net C++ 게임이론 돌게임 3에서 N의 범위만 (1 ≤ N ≤ 1,000,000,000,000) 이렇게 커진 문제 돌게임3를 DP로 풀고 돌게임6를 규칙을 찾아푸는걸 의도한것 같지만 돌게임3를 이미 규칙을 찾아 풀어서 이것도 똑같이 풀었다. 1 -> SK 2 -> CY 3 -> SK 4 -> SK 5 -> SK 6 -> SK 7 -> CY 이 반복됨 소스코드 #include using namespace std; int main(){ //input long long N; cin >> N; //process & out.. 2021. 8. 31.
[백준 2467] 알고리즘 NCT???일차 : 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net C++ 투포인터 산성도가 오름차순으로 정렬된 배열에서 두 용액의 산성도를 합했을때 가장 0에 가까운 두 용액을 찾는 문제 2470번 문제와 아주 유사하지만 정렬된 배열이라는 점이 다르다. 접근방법 양 끝 점에서 시작하여 두 수의 합이 0보다 크면 현재 값보다 더 작아져야 하므로 end 점을 1감소시키고 두 수의 합이 0보다 작으면 현재 값보다 더 커져야 하므로 start점을 1증가시킨다. 소.. 2021. 8. 30.
[백준 1068] 알고리즘 126일차 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net C++ 트리 트리에서 어느 한 노드를 루트노드로하는 서브트리를 모두 삭제할때 리프노드 개수를 구하는 문제 접근방법 벡터로 인접리스트를 구현하고, 부모노드 정보를 담고 있는 1차원 배열을 생성한다. 인접리스트를 탐색하면서 기존 트리에서의 리프노드 개수를 카운팅한다. 지울 노드를 큐에 넣고 그 하위의 노드들도 큐에 넣어 삭제해주면서 지우는 노드가 리프노드인 경우 기존 리프노드 개수 - 1 한다... 2021. 8. 26.
[백준 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.
반응형