rimugi

해결과정처음 생각은 인간의 기초 상식으로 접근하여 각 칸마다 순회를 하며 반드시 특정 숫자여야 되는곳 ex) 가로 세로 square부분을 고려했을때 특정 숫자 만 되는 경우 값을 채우는 형식으로 하였지만 문제 조건에 맞지 않고 그런공간이 없을시 실패하는 당연한 실패였다 두번째 도전은 탐색을 떠나자 라는 식으로 재귀함수를 이용해 탐색을 하였는데 성공했다..솔직히 시간초과를 각오하고 그냥 해본건데 성공해서 찜찜한 문제여서 질문을 남겼다 답변이 돌아온다면 다시 후기에 그 이유를 적어보겠다 #include#include#include#include#include#include#include#include#include#include#include#include#define Fast ios_base::sync_w..

해결과정 - 투포인터왼쪽과 오른쪽을 비교해가며 두 값의 합이 가장 0에 가까운 값을 알아내는 문제라는 것을 파악하였고 한가지 왼쪽을 증가할지 오른쪽을 감소할지를 결정하는 일만 남았다. 결론은 두 값의 절대크기를 비교하여 절대크기가 큰 쪽의 값을 증가시키거나 감소시키는 것다3가지 경우의 수가 있는데1. 왼쪽수는 음수 오른쪽 수는 양수일경우 : 절대크기가 작은쪽을 이동하면 0에서 멀어진다2. 둘다 음수 : 절대크기가 작은쪽을 이동하면 0에서 멀어진다3. 둘다 양수 : 위와 같다 로 나올수 있는 모든 경우의 수에서 절대크기가 큰쪽의 값을 이동해야 된다는 결론이 나왔다 솔직히 감각적으로 알긴했는데 항상 알고리즘은 증명이 필요하다고 개인적으로 생각한다 #include#include#include#include#i..

해결과정문제를 보자마자 이건 신발끈 공식을 사용하는 거라는 생각이 들었고 역시 맛았다. 이 생각이 든 김에 신발끈 공식을 정리해보았는데 두 벡터가 있을때 두벡터의 외적이 두벡터가 이루는 사다리꼴의 넓이라는 것을 수식을 통해 증명한뒤삼각형의 넓이가 1/2 두벡터의 외적크기라는 것을 증명한뒤 다각형을 여러개의 삼각형으로 분리하고 각각의 삼각형의 넓이를 계산하는 방식이 신발끈 공식이였다. 의식의 흐름대로 정리하긴 했지만 방법을 알고 증명을 알면 내가 아는 거니깐 다음번에도 이런문제는 쉽게 풀수있을거같다 #include#include#include#include#include#include#include#include#include#include#include#include#define Fast ios_base..

해결과정 - 단순 구현처음 문제를 본뒤 그냥 단순 구현이구나 라는 생각으로 주어진 대로 문제를 풀었다 하지만 테스트 케이스 중에 2번재 과정이 계속 틀려 곰곰히 생각하던 와중 1 과 N이 연결되있다는 것을 제대로 읽지 않고 N 이상으로 파이어 볼이 나가면 사라지도록 만들어서 틀렸던 것이였다 결과적으로는 그냥 단순 구현문제이면서 파이어볼이 이동할때 범위를 벋어나면 다시 원래 범위로 복귀 시켜주는 문제였다.. #include#include#include#include#include#include#include#include#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);using namespace std;typedef ..

해결과정 - 해 구하기문제는 그리드 알고리즘 으로 1 ~ n-1원까지는 최적의 답을 찾지만 n원에서는 최적의 정답을 찾지 못하는 coin set를 찾아내라는 것이다여기에서 그리드 알고리즘은 coin set이 주어진 경우 가장 금액이 높은 금액을 우선적으로 선택하는 알고리즘인데 예를 들어 n은 6이고 1 , 3, 4가 있을때 1 ~ n-1원 까지는 최적의 해를 계산하지만 6원인 경우 그리드 알고리즘은 4, 1 , 1원 최적의 해는 3, 3원으로 그리드 알고리즘이 최적의 정답을 찾아내지 못하게된다 처음 생각했던 방식은 2를 제외한 모든 수를 출력하는 것이다 이 방식이 해가 되는 이유는 n 일때 1, 3, 4 ... n - 2로 해를 구성하면 위의 예제와 같은 이유로 n 일 경우에만 최적의 정답이 아니게 된다..

해결과정문제는 정말 단순하게 egde의 개수가 k개 라고 하면 1 ~ k의 값을 유일하게 가지면서 vertex의 값도 유일 하게 가지도록  설정하는 것이다전형적인 해 구하기 문제로 해를 모르면 풀수없는 문제였다처음에 나도 문제처럼 삼각형을 이어가며 vertex부터 값을 넣어보았지만 이런문제 특징상 규칙이 있거나 특정한 방식이 있다고 판단하여 여러 규칙들을 적용해 보다 vertex부터가 아닌 edge부터 넣어보자는 생각을 하게되었다 결론으로는 위쪽의 edge와 아래쪽의 edge에 순차적으로 1, 2, 3, 4, 5 ... i 의 값을 넣고 \ 모양 부분부터 i + 1, i + 2.... k 다음으로 /모양에 k + 1, k + 2 ... edge_last 의 값을 넣어주면 된다 이렇게 문제 해결방식을 알게..

핵심요소 - dfs문제는 그래프 상에서 4개의 정점이 서로 연결되어 있는 사이클을 찾는 문제이다처음에 단순히 dfs를 이용하며 각각의 vertex에 깊이를 부여하고 깊이의 차이가 3이면 4개 사이클이라 판단 하는 형식으로 하였다가 좀더 단순하게 풀수 있는 방법을 곰곰히 생각해 보았다 (결론은 위 방식으로도 해결은 가능하였다) 다른 방식은 단순하게 정점마다 4칸 깊이만 움직이며 탐색하는 것이다 i 번째 정점에서 시작하여 4칸째에 i번째에 돌아오는 구간이 있으면 사이클을 증가시켜준다다음으로 i번째 요소는 이미 모든 경우의 수를 확인하였으니 i+1번째 부터는 확인하지 않도록 한다 여기에서 시계방향의 사이클과 반시계방향의 사이클을 문제상에 동일한 사이클로 판단하니 마지막 결과에 2를 나누어 주면 문제가 해결된다..

요즘 따끈따끈한 대회 문제를 푸는 재미에 빠져 거의 하루에 6시간씩 알고리즘 문제를 해결하는 것 같다 핵심요소  문제를 처음 본 뒤 가장 핵심적인 요소는 i 번째 뒤에 있는 요소 즉 i ~ n 까지의 포트중 사용할수 있는 가장 작은 포트를 찾는 것이라는 것을 파악한뒤 세그트리를 이용하여 logn 시간안에 찾으면 되겠다는 생각이 들었다 물론 개인적으로 처음에는 브루드포스로 해결해 보는 경향이 있어 일단 구현 해보았지만 역시 시간 초과가 발생하였다 #include#include#include#include#include#include#include#include#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);using ..

1. 첫번째 아이디어는 가장 긴 문자열의 앞 숫자가 가장 크면 모두 더한 값이 가장 크지 않을까 라는 생각으로 바로 코드를 작성하였다결론부터 말하자면ABBBBBBBBBBBBBB일 경우 내코드를 988 + 88 + 88 + 88 + 88 + 88인데 더 큰 값은 899 + 99 + 99 + 99 + 99 + 99인 경우로 내 이론에 오류가 있었다#define _CRT_SECURE_NO_WARNINGS#include#include#include#define Fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;typedef long long ll; int main() { Fast; int n; short..

#include #include #include #include using namespace std; bool comp(pair a, pair b) { return a.first > n; vector odd_mem; vector even_mem; int odd_result = 200000001; int even_result = 200000001; for (int i = 0; i > tmp; //홀수 if ((tmp & 1) == 1) odd_mem.push_back(tmp); //짝수 ..