펭로그

문제 링크 : https://boj.kr/7576 이 문제보다 기본 개념의 문제는 BOJ 2178 미로 탐색을 참고 컨셉을 잡는 데에 상당히 어려울 수 있지만 알고보면 기본적인 BFS 문제인 것 같다.map을 int형 컨테이너로 하나 만들어 입력 정보를 받고 이 정보를 visited로 사용하면 된다.현재 탐색하는 위치 정보는 별도의 구조체를 만들어 여기에 x, y 좌표와 BFS 탐색의 몇번째 단계에 해당하는지 level 변수를 추가하였다.입력 받을 때 익은 토마토를 발견하면 그 즉시 바로 큐에 담는다.큐에 담긴 순서대로 BFS를 수행하면 문제가 쉽게 풀리게 된다.BFS를 다 수행한 이후엔 다시 한번 전수조사를 해서 안익은 토마토를 체크했다. 12345678910111213141516171819202122..

문제링크 : https://boj.kr/10026 현재 위치를 기준으로 상, 하, 좌, 우의 4방향을 DFS로 탐색해서 같은 영역인지 여부를 확인한다.같은 영역이 아닐 경우 빠져나오며 단 한번이라도 같은 영역이 나오면 true를 반환한다.시간 복잡도에는 크게 영향이 없을 것 같으나 편의를 위해서 한번 탐색한 'R'은 'G'로 바꿔주도록 했다.dfs 탐색 도중 중간에서 반환하는 false의 경우는 최초 dfs 실행 후 담을 chk 변수가 아닌 이상 딱히 의미는 없다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263// BOJ 10026 적록색약#..

문제링크 : https://boj.kr/11653 어떤 숫자의 소인수들은 소수들의 곱으로 표현할 수 있다.그러기 위해선 입력 숫자의 범위만큼 소수 리스트를 구해서 해당 소수들이 입력 숫자로 나누어 떨어지는지를 계산하고 이를 무한히 반복하여 더이상 나누어 떨어지지 않을 때까지 나누면 된다. 다만, 소수 리스트를 다 구할 필요는 없고 입력 숫자의 제곱근 범위까지만 구하면 된다.제곱근보다 큰 범위의 숫자를 2개 이상 서로 곱하면 입력 숫자를 초과하기 때문에 더 이상 구할 필요가 없다.소수 리스트에 속하지 않은 남은 숫자는 무조건 소수이다. (해당 숫자가 소수 리스트의 곱으로 표현되는 순간 소수가 아니다.) 소수 판별은 에라토스테네스의 체를 이용하여 구하면 더 빠르게 구할 수 있다. 123456789101112..

문제링크 : https://boj.kr/1260 가장 기본적인 DFS, BFS 문제이다.시간초과 때문에 애먹었었는데.. 백준 사이트 자체 채점 시스템은 제약조건이 너무 많은 것 같다.std::cin과 같은 것도 조심해야 하고 for each 구문도 조심해야 하는듯....편하려고 STL을 사용하면 문제 생기는 부분이 좀 있는 것 같다. 1234567891011void dfs(int num){ if(!visited[num]) sort(node[num].begin(), node[num].end()); visited[num] = true; for(int i : node[num]) { if (!visited[i]) { cout

문제링크 : https://boj.kr/2960 시작 숫자부터 해당 숫자만큼의 배수로 탐색하여 답을 찾아가면 된다.단 한번도 특정 숫자로 나누어 떨어지지 않은 숫자는 모두 소수이고 그 소수의 배수들은 소수가 아닌 수가 된다. 소수를 구하는 알고리즘은 다음과 같다.처음으로 지워지는 숫자인 파란색은 소수이고 지워진 수는 소수의 N 배수이다. 배수가 되는 순간 소수가 아니기 때문에 당연히 파란색만 소수가 된다. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2의 배수 제거2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3의 배수 제거2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5의 배수 ..

문제링크 : https://boj.kr/2252 위상정렬을 이용한 문제로 자신을 가리키는 간선이 없는 경우 즉, indegree가 0인 정점을 찾는다.자신을 가리키는 간선(indegree)가 1개 이상 있다는 의미는 자신의 노드가 뒷쪽에 나와야 한다는 것을 의미한다.찾은 정점을 큐에 넣고 간선을 삭제한다.반복 자료 입력 순서가 중요하면 우선순위 큐를 사용하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344// BOJ 2252 줄 세우기// DAG (Directed Acyclic Graph)// 순환을 가지지 않는 방향그래프// 위상정렬 (Toplogical Sort)#include #include #in..

문제링크 : https://boj.kr/1717 시간 제한을 신경써야 하는 문제로 iostream의 std::cin을 쓸 경우 시간 초과가 난다.scanf를 사용하거나 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 를 같이 사용해야 한다.std::endl 도 마찬가지로 시간이 오래 걸리는 키워드로 "\n"을 써주는 편이 훨씬 빠르다고 한다. 그래프 문제로 처음엔 서로소 집합으로 자기 자신을 참조하는 형태로 노드를 표현한다. 연산이 될 때마다 루트노드를 업데이트 시킨다.int find(int node) { if (root[node] == node) return node; else return find(root[node]);}위의 경우 f..

문제링크 : https://www.acmicpc.net/problem/1966 2개의 배열을 선언하여 각각 동일하게 입력받은 후 한 배열은 우선순위 순서대로 정렬하여 순서대로 카운트한다.정렬된 배열은 우선 순위가 가장 큰 숫자가 맨 뒤로 가게되므로 배열을 탐색하는 도중에 해당 숫자가 발견되면 ptr을 줄여가면서 옮겨주는 방식이다.그리고 모든 배열을 다 탐색하였을 경우 다시 원점으로 돌아가야 하기 때문에 % num 모듈러 연산을 하였다. 1234567891011121314151617181920212223242526272829303132333435363738// BOJ 1966 프린터 큐#include using namespace std; int main() { freopen("../input.txt", "..

문제링크 : https://www.acmicpc.net/problem/9012 1. 열린 괄호의 갯수 == 닫힌 괄호의 갯수 가 성립해야한다.2. ( 가 나올때마다 카운트를 증가시키고 ) 이 나올때마다 카운트를 감소시켜 최종 카운트가 0이 되어야 한다.3. 닫힌 괄호가 먼저 나오면 안된다. ())(() 라던지 ))()(( 의 상황이 나오면 안된다는 뜻 (20~21번째 줄 조건시 break) 심화문제로 BOJ 10799번 쇠막대기 문제가 있다. 123456789101112131415161718192021222324252627// BOJ 9012 괄호#include using namespace std; int main() { // freopen("../input.txt", "r", stdin); int T;..

문제링크 : https://koitp.org/problem/SDS_TEST_CALCULATOR [삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 3번 문제]시간초과로 실패했던 문제이다. 1. 일단 정렬한다.2. 앞의 두 숫자(최소값)을 더하고 더한 숫자를 뒷쪽에 끼워놓는다.3. 반복 삭제와 삽입이 빈번하게 일어나기 때문에 STL vector를 사용하면 시간이 매우 오래걸리게 된다.또한, 매 loop 실행시마다 삽입의 적절한 위치를 찾기 위해 for문을 돌리기 때문에 O(N^2)이 되겠다.답은 맞은듯하나 시간초과로 실패하였다. 우선순위 큐를 사용하면 될 것 같기도 한데 아직 이것도 모르겠다.일반 배열과 vector를 제외한 다른 자료구조에 대한 학습이 부족하여 여기까지가 한계인듯하다.추후에 자료..