rimugi

해결과정 - 사이클 찾기단순 사이클 찾기 문제라는 것을 깨닳고 재귀를 사용하려고 했으나 비슷한 유형의 문제를 너무 많이 풀어봐서 이번에는 반복문으로 해결해 보고 싶다는 생각이 들었다. 그래서 배열 담는 용도인 arr, 방문체크 목적인 visited, 사이클의 원소 수를 체크하기 위한 depth 배열을 구성하였다. 여기에서 visited의 값으로 현재 순환중인 노드의 첫번째 값 예를들어 1번째 노드부터 시작하여 순환하고 있으면 1번째 노드의 값을 넣어줌으로 써 다음번 순회를 돌경우 방문한 곳이 사이클로인해 방문한 곳인지 아님 전에 방문하여 못가는 곳인지 체크하도록 하였다 #include #include #include #include #define FAST ios::sync_with_stdio(0), ci..

해결과정처음 생각은 인간의 기초 상식으로 접근하여 각 칸마다 순회를 하며 반드시 특정 숫자여야 되는곳 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..