Son's Warehouse

문제 출처 : https://www.acmicpc.net/problem/2491분류 : 구현 백준 2491 수열가장 긴 단조증가 혹은 단조감소 수열의 길이를 찾아라구현 포인트1) 증가하는 것만 고려해서 찾고, 감소하는 것만 고려해서 최대 길이를 찾는다. 2) 너무 복잡하게 생각하지 말 것(입력이 최대 100,000개이다.) 이 문제에 대한 리뷰가 필요했던 이유는 너무 복잡하게 생각했다는 것이였다.증가인 상태와 감소인 상태, 감소에서 증가로 가는 상태 등등 여러 상태들을 표현하려고 했다.그러다 보니 코드가 길어지고 복잡해 졌다.우선 처음에 구현된 코드는 아래와 같다...매우 가독성이 떨어지는..;; 반성해야 할 것 같다.. 참고로 여기서는 flag로 상태 전이를 이용하여 구현하였다..너무 어렵게 생각했다...

문제 출처 : https://www.acmicpc.net/problem/11403분류 : 그래프 백트래킹 백준 11403 경로찾기각 정점간의 연결 여부를 확인하라구현 포인트1) 정점이 100개 밖에 안되므로 뭘 써도 제한시간 1초안에 가능하다. (BFS, DFS, Flyod-Warshall) 2) 자기 자신간의 연결여부를 확인해야 한다. 자기 자신으로 돌아오는 싸이클의 여부 판단정답률이 높고 쉬운 문제임에도 여기다 적는 이유는 처음에 2번을 고려하지 않았기에..ㅎㅎ;;;구현된 코드는 아래와 같다. (BFS) 1234567891011121314151617181920212223242526272829303132333435#include#include#includeusing namespace std; int m..

문제출처 : https://algospot.com/judge/problem/read/WORDCHAIN 이 문제에서 얻어 갈 수 있는 것은 eulerian curcuit과 eulerian trail을 얻는 방법과 주어진 그래프에서 오일러 회로 및 트레일이 존재할 수 있는 여부를 따지는 방법에 대한 코드이다. 오일러 회로 및 트레일에 대한 설명은 여기서 얻을 수 있다. 구현된 코드는 다음과 같다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293..

안녕하세요. 오늘은 한붓그리기, 오일러 서킷이라 부르는 문제들에 대해 다루어 보겠습니다. ContentsEulerian cirtuit(오일러 서킷)Eulerian trail(오일러 트레일) Eulerian Circuit(오일러 서킷)오일러 서킷이라는 것은 우리들에게 한붓그리기 문제로 더 알려져 있습니다. 오일러 서킷그래프가 주어졌을 때 그래프의 한 시작점으로부터 모든 간선을 한번씩만 지나 다시 시작점으로 돌아오는 경로를 말합니다.이러한 경로가 있으려면 어떠한 조건을 만족해야 할까요?가장 많이 사용되고 있는 방법으로는 단순하게 정점의 degree를 사용하는 것입니다.degree라는 것은 위상정렬 할 때 잠시 살펴보았죠? 그 때는 indegree를 이용하였고, 여기서 degree라는 것은 정점에 연결되어 있..

문제 출처 : https://www.acmicpc.net/problem/1016 분류 : 소수판별법 백준 1016 제곱ㄴㄴ수주어진 범위에서 제곱수로 나누어 떨어지지 않는 숫자의 개수를 구하라구현 포인트1) 일반 정수의 제곱의 배수보다는 소수의 제곱을 고려하는 것이 더 경우의 수가 적어진다. (소수의 제곱의 배수만 고려해도 모든 경우를 커버할 수 있기 때문이다.) 2) 소수의 제곱을 고려해서 배수의 갯수를 뺄 때 중복되는 것이 있음에 주의해야 한다.(ex, 16의 9배 = 9의 16배) 3) 계산과정에서 int범위가 넘어 갈 수 있음에 유의해야 한다. 구현된 코드는 아래와 같다.소수는 에라토스테네스의 체를 이용하였고,중복된 수는 갯수에서 제외하기 위해 check라는 배열을 만들어서 제곱의 배수는 0으로 만..

문제 출처 : https://www.acmicpc.net/problem/1013분류 : 오토마타, 정규표현식 백준 1013 Contact정규표현식 (100+1+|01)+ 을 만족하는 문자열을 찾아라처음에 풀때는 아무 생각없이 state transition graph를 그려서 그래프를 그대로 코드로 옮기려고 하였다.그 결과 나오게 된 코드는 아래와 같다.종결상태와 여러 입력에 대해 state를 바꾸는 오토마타를 만든 것과 다름이 없다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081..

안녕하세요. 오늘은 그래프를 활용한 문제에서 등장하는 위상정렬에 대해서 알아보겠습니다. ContentsDAG(Directed Acyclic graph)Topological sort란?위상정렬의 구현방식(1)-indegree위상정렬의 구현방식(2)-DFS DAG(Directed Acyclic Graph)우선 위상정렬을 공부하기 전에 DAG에 대해서 알아봅시다. Directed Acyclic graph란 말 그대로 간선에 방향이 있고, 싸이클이 없는 그래프를 말합니다.Directed Graph에서 방향을 가지고 있는 간선들의 sequence에 대해 시작점과 끝점이 같아지는 sequence가 있다면 싸이클이 있다고 합니다. DAG는 이런 싸이클이 없는 유향그래프이죠.이전의 그래프의 정의와 함께 말씀드렸듯 DA..

안녕하세요. 오늘은 그래프에 대해서 가장 많이 등장하는 DFS에 관하여 알아보겠습니다.DFS는 매년 여러 곳의 입사시험 및 프로그래밍 대회에서 등장합니다. ContentsDFS(Depth-First search)DFS구현(1) RecursiveDFS구현(2) StackDFS의 time complexity DFS(Depth-First Search)DFS란 무엇일까요? 한국말로 해석해보면 깊이 우선 탐색이라는 말이 됩니다. 그래프에서 특정 정점을 찾을 때 그래프의 깊이를 우선적으로 탐색한다는 말이죠. 이렇게 말하면 솔직히 감이 잘 안옵니다.예를 봅시다! https://steemitimages.com/0x0/https://janav.files.wordpress.com/2014/01/dfs-bfs-differe..