728x90 전체 글86 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. c++ 백준_2166_"다각형의 면적" https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 처음 접근한 방법은 그래픽스 시간에 배운 모든 도형은 삼각형 근사가 가능하다는 것에서 시작했다. 그래서 다각형을 삼각형으로 나눠 나온 모든 삼각형의 넓이를 계산하려했다. 처음 삼각형 넓이를 구하려고 했는 방법은 그냥 다 때려박았다. 두점 사이의 좌표로 기울기를 구할 수 있으니 방정식을 구해서 그에 수직인 방정식을 구해 ..여차저차 넓이를 구할 수 있었다. 그래서 좌표가 주어지면 index 번호로 보았을 때, 0 .. 2023. 6. 9. 이전 1 ··· 11 12 13 14 15 다음 728x90
