본문 바로가기

백준30

백준 15956 숏코딩 (c++) (으아아) 예외처리에 매우 매우 매우 주의해가며 푼다 string s; //원본 문자열vector tokens; //&&단위로 끊은 조건식들map parent; //==로 연결되어있는것들 부모배열vector > diff; //!=로 연결된것들map> group; //==집단들map digit; //상수가 포함된 집단이렇게 사용하여 풀었다 string find_parent(string s){ if (parent[s] == s) return s; else return parent[s] = find_parent(parent[s]);}void union_find(string s1, string s2){ s1 = find_parent(s1); s2 = find_parent(s2); parent[s1] = s2;.. 2025. 4. 28.
백준 2342 Dance Dance Revolution (c++) DP라고 하기에도 애매하고 아니라기에도 애매한.. 애매한 문제 int dp[100010][5][5] = { 0, };vector arr;int calc(int from, int to){ if (from == 0 && to != 0) return 2; if (abs(from - to) == 3) return 3; else if (abs(from - to) == 2) return 4; else if (abs(from - to) == 1) return 3; else if (abs(from - to) == 0) return 1;}먼저 발이 이동할때 얼마나 힘이 드는지 구하는게 꽤나 길어서 함수로 뺐다 dp는 [arr 인덱스][왼발 위치][오른발 위치] = 이 상태의 최소값 int n;int idx = 0;arr.. 2025. 4. 14.
백준 2887 행성 터널 (c++) 행성의 갯수만 10만개간선은 10만의 제곱이므로 일반적인 방법으로는 어떤 최적화를 해도 시간초과다애초에 간선 10만^2개를 만든 시점에서 메모리  초과(50테라라고 함)로 아웃 즉 간선을 만들고 가지치기를 하면 안되고 만들기 전에 경로가 될 가능성이 있는 간선만 만들어야 하는 문제이다 그것은 터널의 비용이 특수하기 때문에 가능하다min(|ax-bx|,|ay-by|,|az-bz|)공간의 세 축 각각의 거리중 가장 작은 값이 비용이다 a -> b -> c 노드가 수직선 상에 존재할때a->b + b->c = a -> c 일 것이다이때 우리가 원하는건 a,b,c 모든 지점을 통과하면서 가장 비용이 적게드는 경로를 찾는 것이므로굳이 인접하지 않은 a -> c 경로는 생각할 필요가 없다는 뜻이다이보다 노드가 많을때.. 2025. 4. 7.
백준 17270 연예인은 힘들어 (c++) 조건이 너무 불합리하다  2번에서 합이 최소인 노드들을 구하고 3번에서 조건을 체크해서 맞는 노드가 없었으면당연히 차선 노드들에서 3번 조건찾기를 진행해야 하는것 아닌가?이 문제는 일단 합이 최단인 노드를 뽑아두고 그것들이 전부 3번 조건을 만족하지 못하면 얄짤없이 -1을 출력해야 하는 문제였던 것이다 말도안돼.. int v, m;int js, ss;vector > > arr;vector jihun;vector sungha;지헌 성훈 각각의 시점에서 다익스트라를 돌려줄 것이므로 체크 배열을 두개 만들어준다 void dijkstra(vector& checker, int start){ checker[start] = 0; priority_queue, vector>>pq; pq.push({ 0,start });.. 2025. 3. 24.
백준 1504 특정한 최단 경로 (c++) 일반적인 다익스트라 알고리즘을 사용하여반드시 들러야 하는 두 정점이 있다는것을 생각해야 한다.주의할 점은 두 정점을 들르는 순서는 관계없다는 점 #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;int n, e;vector >> arr;int v[3] = { 0, };vector dijkstra(int start){ vector visit(n+1, INT_MAX); visit[start] = 0; priority_queue, vector>> pq; pq.push({ 0,start }); while (!pq.empty()) {.. 2025. 3. 17.
백준 1584 게임 (c++) 일반적인 다익스트라인줄 알았는데 0-1 너비우선탐색이라는 기법을 사용해야 했다 #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;int arr[501][501] = { 0, };int n, m;static int mx[4] = { 1,0,-1,0 };static int my[4] = { 0,-1,0,1 };int checker[501][501] = { 0, };int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); for (int i = 0; i > n; f.. 2025. 3. 14.
백준 2352번 반도체 설계 (c++) 꼬임이 없다는 것은 오름차순으로 정렬되어야 한다는것즉 가장 긴 증가하는 부분수열을 구하는 문제이다하지만 n이 40000이나 되기 때문에 일일이 비교하면 시간초과가 되므로 이분탐색 기반 알고리즘을 이용한다 cin >> n;for (int i = 1; i > a; if(arr.empty()) arr.push_back(a); else { int idx = lower_bound(arr.begin(), arr.end(), a) - arr.begin(); if (idx >= arr.size()) arr.push_back(a); else arr[idx] = a; }} 숫자를 받으면서 바로 증가하는 수열을 만들어준다lower_bound는 배열에서 지정한 수보다 크거나 같은 숫자가 몇번째 인덱스에서 처음 나오는지 .. 2025. 2. 26.
백준 14786번 Ax+Bsin(x)=C (c++) 정밀도 때문에 한번 틀렸다 cin >> a >> b >> c;double low = (double)(c - b * 1) / a;double high = (double)(c - b * -1) / a;초기값을 잘 정해야 한다.이분탐색을 돌릴때 사용할 high와 low를 구해야 하는데,Ax+Bsin(x)=C-> sin(x) = (c - Ax)/Bsin(x)는 -1~1 사이의 수일것이므로k -> -1~1k = (c - Ax)/B-> x = (c - Bk)/Ax는 k가 1일때 최소, -1일때 최대가 될 것이다 while (high - low >= 1e-9){ double mid = (high + low) / 2.0; if (sin(mid) > (c - a * mid) / b) { high = mid; } el.. 2025. 2. 25.
백준 2230번 수 고르기 (c++) 오랜만에 투 포인터 문제를 몇개 풀어보기로 하여 맛보기 문제 cin >> n >> m;for (int i = 0; i > a; arr.push_back(a);}sort(arr.begin(), arr.end());먼저 데이터를 받아 정렬해놓는다 int s{ 0 };int e{ 0 };int ans = 2100000000;while (s m) { ans = min(ans, num); s++; } else if (num 포인터 두개, 시작 인덱스와 끝 인덱스를 0으로 설정하고 투포인터를 시작한다 선택된 두 수의 차이가 m보다 작으면 끝 인덱스를 한칸 키워 값을 올려주고,m보다 크면 정답을 갱신하고 혹시 m과 더 가까운 답이 존재할 수 있으므로 시작 인덱스를 한칸 키워 차이를 줄여준다 2025. 2. 22.

티스토리툴바