백준 11505 구간 곱 구하기 문제풀이 [11505 구간 곱 구하기] https://www.acmicpc.net/problem/11505 . segment tree를 이용하여 빠르게 구간 곱을 변경하고 출력한다. 문제상황 파악하기. [2042 구간 합 구하기] https://www.acmicpc.net/problem/2042 . 위 ...

코드포스 폭망기념 upsolving Codeforces Round #800 Editorial 개요. 코드포스를 시작하고 그래도 계속 그린 퍼포먼스는 나오길래 답만 보고 넘겼었다. 그런데 이번 코포에서 정말 단 한문제도 못풀었다… 그래서 분노의 업솔빙을 해보려고 한다. ㅠㅠ 백준 플레가 코포 뉴비에서 헤매고 있다니 정말 분하고 부끄럽다. ...

백준 1305 광고 문제풀이 [1305 광고] https://www.acmicpc.net/problem/1305 . KMP알고리즘 base의 failure function을 이용해서 문제의 답을 구한다. 문제상황 파악하기. 광고 문구가 될 수 있는 것중 가장 짧은 광고문구를 찾는 문제이다 . 광고가 될수 있는 문구 1글자, 2글자, 3글...

백준 4386 별자리 만들기 문제풀이 [4386 별자리 만들기] https://www.acmicpc.net/problem/4386 . 간선을 추려서 MST(minimum spanning tree)를 만든다. 문제상황 파악하기. 정점들의 위치가 주어지고 이동은 어디든 할 수 있다 . 이동 할때 그 거리는 점과 점사이의 거리이다. 모...

백준 4803 트리 [4803 트리] https://www.acmicpc.net/problem/4803 . 상호 배타적 집합(disjoint set)을 이용하여 트리인지 아닌지 판단한다. 문제상황 파악하기. 정점을 잇는 간선이 주어진다 . 이 그래프는 서로 떨어져있는 그래프일 수도 있고 사이클이 있을 수도 있다. 즉 떨어져 있는 그래프...

백준 2206 벽 부수고 이동하기 문제풀이 [2206 벽 부수고 이동하기] https://www.acmicpc.net/problem/2206 . BFS로 최단거리를 탐색한다. 문제상황 파악하기. 전형적인 그래프 탐색 문제처럼 보인다. 최단거리를 구해야하므로 DFS가 아닌 * BFS(너비우선 탐색) 으로 풀어야한다. 문제는 벽을 한번만 부술...

백준 2166 다각형의 면적 문제풀이 [2166 다각형의 면적] https://www.acmicpc.net/problem/2166 . 신발끈 공식을 이용하여 다각형의 면적을 구해보자 문제상황 파악하기. 점들로 구성된 다각형의 넓이를 구하는 문제로 신발끈 공식을 이용하여 구할 수 있다. 점의 최대 좌표는 100000이고 그렇다면 면적을 구할 ...

백준 12015 가장 긴 증가하는 부분 수열2 문제풀이 12015 가장 긴 증가하는 부분 수열2. DP의 대표적인 문제인 LIS의 시간 복잡도를 줄여보자 문제상황 파악하기. 이 문제는 가장 긴 증가하는 부분 수열1 보다 N이 1000배 정도 늘어났다. 따라서 같은 방법으로 풀면 TLE(Time Limit Exceeded)를 받게 된다. 그러면 ...

백준 10986 나머지합 문제풀이 굉장히 오랜만에 블로그로 돌아왔다. 폐관수련 중이였다. 백준티어도 골드2정도로 올렸고 여러가지 자료구조들과 알고리즘들을 익혔다. 이제 본격적으로 포스팅도 해가며 공부를 할 계획이다. 이제 백준 플레티넘과 코드포스 블루를 향해 달려보도록 하겠다. 이후에 고수가 된다면 공부방법도 포스팅해봐야지 그 시작...

스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택 #include 헤더 파일을 쓰느 방법도 있지만 문제가 문제인지라 직접 구현을 해보기로했다. # Class로 나의 스택 구현하기 class myStack{ public: int current=-1; int s...