DFS, BFS를 처음 배운 입장에서는 좀 까다로운 문제였다. 이 문제를 보고 처음 접근한 방식은, DFS이다. 실제로 구현 방법이 아직까지는 DFS가 재귀로 짜기 쉽기도하고, 두 가지 방법의 근본적인 차이에 대해서 잘 이해하지 못했기 때문이다. 일단, 이 문제를 DFS로 바라보면 안되는 이유에 대해서 정리하자면, 1. 너무 불필요하게 하나의 케이스를 기준으로 건물 양 끝을 오가게 된다. 정확하게 이 문제를 이해해보면, 올라가는 케이스와 내려가는 케이스를 기준으로 해당하는 칸을 갈 수 있는지를 체크하는 것이 중요하다. 그런데, 만약에 해당하는 칸을 가면 참 좋겠지만 가지 못한다면 잘못하면 무한루프에 빠질 가능성이 존재한다. 위 문제에서 최저값이 1층 최고값이 입력에서 제한되어 있는 상황이므로 계속해서 계..

이 문제의 경우에서 기본적인 접근방법은, 자신을 기준으로 위로 올라가는 방향이든 아래로 내려가는 방향이든 구분하지 않고 이동을 한번 하면 촌수가 1 증가한다는 것을 이용하여 그래프를 활용하여 촌수를 계산할 수 있다는 것을 인지하고 풀면 된다. 처음에는 #include #include #include #include using namespace std; int visited[101] = {0}; int dfs(int start, int end, int (&data_store)[101][101]){ if(start == end) return 0; if(visited[start] == 1) return 0; else{ int count = 0; visited[start] = 1; for(int i = 0; i..

위의 STL 자료는 유명한 자료구조이므로 잘 학습해 두어야 한다. Deque 이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다. 이 자료구조의 특징은 stack의 특징과 queue의 특징을 섞었다는 것이다. 즉, LIFO(Last In First Out)이다. 즉, 나중에 들어온 것이 먼저 나가는 자료구조이다. Deque는 기본적으로 vector container와 매우 유사하나, vector보다는 앞과 뒤의 원소로 삽입이나 삭제가 빈번한 경우에 사용하는 것이 일반적이다. vector의 경우에는 뒤의 자료만 추가하고 삭제가 가능하다. 선언 방법은 "deque 변수이름"이다. 만약 선언하면서 초기화를 시키고 싶은 경우에는 사용방법은 다음과 같다. dq.push_front(va..

이 문제를 보고 set 자료구조를 이용해야되는 것을 인지할 수 있어야 한다. 왜냐하면, 일단 vector나 array처럼 index를 기준으로 찾는 것이 아니라 문자를 기준으로 찾는 것이고 문자열만 판단하면 되므로 set 자료구조를 이용하면 된다. 해당하는 알고리즘을 코드로 구현하면 다음과 같다. #include #include #include #include #include #include #include #include using namespace std; int main(void){ int n, m; cin >> n >> m; set data_store; for(int i = 0; i > temp; data_store.insert(temp); } ..

우선순위 큐 (Priority queue) 이 알고리즘을 활용하기 위해서는 반드시 #include 를 선언해야 한다. 컨셉자체는 Queue와 거의 유사하나 방식이 다르다. 다만, 나오는 순서가 우선순위를 부여하여 해당 우선순위에 해당하는 값이 먼저 pop한 값으로 나오게 된다. (기본적인 default자체는 가장 큰 값이 먼저 빠져나오게 된다.) 선언 방법은 "priority_queue 변수이름"이다. 자료형에는 int, double, class가 들어갈 수 있고, 구현체의 경우는 값을 어떠한 방식으로 저장할지를 설정해주는 것인데 기본적으로는는 vector이다. 비교연산자의 경우 일반적으로는 less을 사용하나 greater을 입력하게 되면 오름차순으로 우선순위큐가 정렬된다. 즉, 낮은 숫자가 우선순위가..

위의 STL 자료는 유명한 자료구조이므로 잘 학습해 두어야 한다. 1.Stack 이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다. 이 자료구조의 특징은 LIFO(Last In First Out)이다. 즉, 나중에 들어온 것이 먼저 나가는 자료구조이다. Stack을 사용하는 경우는 일반적으로 LIFO상황에 맞는 유형일 때 많이 사용된다. 물론 vector나 array를 활용해서 사용할 수도 있으나 컴파일 에러 등의 문제를 걱정하지 않아도 된다는 점에서 Stack STL을 사용하는 것이 유리하다. 선언 방법은 "stack 변수이름"이다. 사용방법은 다음과 같다. s.push(value) : 스택에 원소를 추가 s.pop() : 스택의 마지막 원소를 제거 (LIFO이므로 나가는..

위의 STL 자료구조는 매우 자주 쓰이는 형태이므로 잘 정리해 두어야 한다. Map 이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다. 이 자료구조의 경우는, vector나 배열과는 다르게 index를 활용하여 접근하는 것이 아니라 다른 자료형을 사용할 수 있는 것이다. 이 방법의 경우에는 검색, 삽입, 삭제 등의 속도가 빠른 편에 속한다. 선언 방법은 "map 변수이름"이다. Map을 사용해야 하는 경우는, 단순히 기존에 vector나 배열을 사용하는 방식처럼 index와 숫자를 매칭시킬 수 없는 상황이거나 연관있는 2개의 값을 매개하여 저장해야할 때 사용하게 된다. 사용방법은 다음과 같다. m.size() : m의 원소의 개수 m.empty() : m의 노드의 개수가 0..

이 문제의 경우에는 상황 자체는 쉽게 이해할 수 있으나, 구현이 상당히 까다롭다. 그러한 까닭에 디버깅을 한참 시도하였다..(문제를 잘못읽은 영향이 사실 제일 크다.) 이 문제를 풀기위해서 가장 중요한 조건은 2가지의 작동이 순차적으로 진행된다는 것이다. 미세먼지의 확산을 시키고, 공기청정기에 의한 작용을 살펴주면 된다. 단, 미세먼지의 확산이 동시에 되기 때문에 temp array를 하나 만들어줘서 따로 처리해주어야 한다. 그렇지 않으면 배열이 바뀌면서 확산에 영향을 끼치게 되기 때문에 오류가 나올 수 밖에 없다. 또한, 공기청정기에 의한 확산은 일종에 먼지가 이동하는 작업을 거치게 되는데 이전의 배열에 있는 숫자가 이후로 옮겨지는 양상이므로 그것을 저장해주기 위해서 DP방식을 활용하여 진행해주면 된다..