728x90 문제/백준43 c++ 백준_11054_"가장 긴 바이토닉 부분 수열" https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 입력 크기가 크지 않아서 N^2 복잡도가 걸리는 DP 방식을 사용해 각 요소 마다 가장 긴 부분 수열의 길이를 저장했다. 올라갔다가 감소하는 형태니까 결국에는 한번은 앞에서 증가하는 부분 수열을 찾고 한번은 뒤에서 증가하는 부분 수열을 찾으면 되었다. 그래서 구한 각각의 가장 긴 부분 수열의 길이가 저장된 배열 2개의 같은 index끼리의 합이 가장 큰 것을 반환하였다. 그리고 가장 긴 부분 수열이 중첩돼.. 2023. 6. 9. c++ 백준_12852_"1로 만들기 2" https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net BFS를 사용하였다. 각 node에 vector를 넣어 해당하는 요소들을 pushback pop 해주니까 시간초과가 났다 그래서 전역으로 배열로 접근해서 각 number에 해당하는 index에 최소 count(연산 최소 횟수)가 되냐 안되냐를 체크하며 진행했다. 그리고 들어간 요소 체크는 새로운 node를 queue에 넣을 때마다 index 배열에 따로 그 번호를 넣어 backtrace해줬다. ** 10^6을 계속 10만으로 잘못 생각해서 왜 자꾸 out of bound가 어디서 뜨지 하.. 2023. 6. 9. c++ 백준_1987_"알파벳" https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS를 활용하였다. 알파벳 확인 배열(bool)을 하나 만들어 체크해주며 한번 지나온 알파벳은 지나오지 않도록 했다. ** 처음에는 vector 을 사용해서 재귀 함수 인자로 계속 넘겨줬다. 계속 시간초과가 나오길래 대체 어디서 나오지 했는데 bool 을 전역 배열로 두고 진행하니 시간 초과가 뜨지않았다. vector 접근하고 값 복사하고 하고, 재귀로 계속 부르고 하는게 시간.. 2023. 6. 9. c++ 백준_1806_"부분합" https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투포인터 (?) 방식으로 하였다. left right 지점을 잡아 사용하였다. 처음 left = 0 에 두고 길이를 +1 하며 right 로 이동하며 값을 더한다. 현재 계속 더한 값이 S 이상이 되면 right를 그 위치에 고정시키고, left를 right 방향으로 이동하고 길이를 -1시키며 현재 값에서 left 위치에 저장된 값을 뺀다. 그러면서 현재 값이 S 이상.. 2023. 6. 9. c++ 백준_4386_"별자리 만들기" https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net Kruskal 알고리즘을 사용하였다. n개의 노드들을 최단 비용으로 이어버리면 된다. 각 노드에서 각 노드를 향하는 거리를 계산하여 우선수위큐에 넣어 주어 진행하였다. #include #include #include #include using namespace std; int n; pair coord[100]; int parent[100]; typedef struct { int u, v; dou.. 2023. 6. 9. c++ 백준_1007_"벡터 매칭" https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 처음에 하나하나 좌표를 구해서 모든 경우를 다 보았다. 이차원 배열을 쓰니 뭐하니 뭐하니 하다가 시간초과 노이로제만 걸린 거 같다. ㅎ 그러다 문득 생각이 든게 ( 3시간 뒤에) 최대 20개 중 반은 출발점, 반은 도착점이다. 벡터 길이 계산은 도착 - 출발이니까 N/2 개의 출발점만 구하면 각 좌표가 출발점이냐 아니냐만 체크하면 더하고 빼고를 할 수 있었다. ** 코드.. 2023. 6. 9. 이전 1 ··· 4 5 6 7 8 다음 728x90
