본문 바로가기

백준154

백준 c++ 1912 "연속합" -PlusUltraCode- https://www.acmicpc.net/problem/1912         [필자 사고]연속합 문제이다.  시간복잡도를 측정하기 위해 문제에서 주어진  N의 크기를 본 결과 N=100000이다. 즉 시간복잡도 n^2 인 형태로 코드를 짜면 안된다. 잠시 고민해본 결과 다이나믹 프로그래밍이 떠올라 해당 코드를 작성했다. 필자는 Dynamic 이라는 배열을 만들었고 Dynamic의 들어가는 숫자는 arr의 숫자들 중  순서대로 합해서 최대가 되는 숫자들만 넣는 형식으로 정의했다. [소스 코드]  #include#include using namespace std;int N;vector arr;vector Dynamic;int maxNum = -111111;void Input() { cin >> N; a.. 2024. 4. 29.
백준 14503 c++ "로봇 청소기" -[PlusUltraCode] https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽www.acmicpc.net [필자 사고]단순 구현 문제이다. 먼저 문제에서 주어진 조건들을 잘 따라오면서 코드를 작성하면 쉽게 풀릴 수 있다. 필자는 로봇이라는 객체를 하나 구현해서 문제를 풀어 나갔다.  [소스 코드]#include#include using namespace std;class Robot {public: int sero; int garo; int see; //.. 2024. 4. 25.
백준 11286 c++ "절댓값 힙" -[PlusUltraCode] https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [필자 사고] 이 문제는 절댓값 힙 문제이다. 힙 관련 알고리즘은 우선순위 큐라고 말할 수 있다. 여기서 중요한 포인트는 양수만 주어지는게 아닌 음수 또한 주어지고 그 중 절댓값이 작은 값으로 정렬해야 된다는 점이다. 만약 절댓값이 같으면 실제 더 작은값을 정렬해야 된다는 점도 있다. 쉽게 말해 우선순위 큐를 이용하여 우선순위 정렬 알고리즘을 직접 작성할 수 있는지 없는지를 .. 2024. 4. 19.
백준 11279 c++ "최대 힙" -[PlusUltraCode] https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [필자 사고] 최대 힙을 구하라는 문제이다. 최대 힙과 가장 연관있는 알고리즘은 우선순위 큐이다. 개발자가 원하는대로 정렬 시스템을 설계하면 이 문제를 쉽게 해결할 수 있따. c++내의 우선순위큐를 선언만 하면 자동으로 큰 값이 우선되게 정렬 되어 있다. 이제 알고리즘을 정했다면 시간복잡도에 어긋나지 않는지 판단해야 된다. N=10000 가 주어진다. 우선순위큐의 시간복잡도.. 2024. 4. 18.

티스토리툴바