목록c++/백준 문제 풀이 (17)

어제의 나보다 성장한 오늘의 나

[C++] [BFS / DFS] 백준 2331 번 문제 풀이

문제 DFS / BFS 와 그리디 두 가지 방법으로 풀었는데 DFS / BFS를 사람들이 일반적으로 많이 사용한다. 시간적으로는 DFS / BFS 가 효율적이고 , 메모리 사용량으로 보면 그리디가 좀 더 효율적이다. 첫 번째 풀이 : DFS / BFS A 의 최대는 9999 , P의 최대는 5 나올 수 있는 가장 큰 값은 : 9의 5승 * 4 = 236196 Code // BaekJoon 2331 // Title : 반복 수열 // URL : https://www.acmicpc.net/problem/2331 #include #include using namespace std; #define MAX_NUM 236196 int visit[MAX_NUM]; int P; int answer = 0; void D..
c++/백준 문제 풀이 2022. 8. 19. 18:21
[C++][BFS / DFS] 백준 2606번 문제 풀이

간단한 BFS or DFS 문제 ◎ Data structure는 Deque를 사용함 ◎ adj_list 먼저 만들고 DFS Search로 답을 구함 (BFS 사용해도 됨) ◎ adj_list , check를 전역 변수로 선언 하지 않고 매개변수로 보내줌 ( 동적 할당을 위해 ) Code // BaekJoon 2606 // Title : Virus // URL : https://www.acmicpc.net/problem/2606 #include #include using namespace std; void DFS(deque adj_list[] ,deque &check , int i , int &cnt){ check[i-1] = true; for(int j = 0 ; j < adj_list[i-1].size..
c++/백준 문제 풀이 2022. 8. 19. 15:50
[C++][BFS / DFS] 백준 10451번 문제 풀이

문제 ◎ 저는 이 문제를 adjacent matrix를 만들고 DFS로 탐색하며 문제를 해결하였습니다. Code // BaekJoon 10451 // Title : 순열 사이클 // URL : https://www.acmicpc.net/problem/10451 #include #include using namespace std; // DFS recursion void DFS(vector &arr ,vector &check ,int i){ check[i-1] = true; for(int j = 1 ; j > T; while(T--){ int cnt = 0; // answer cin >> N; vector arr(N , vector(N , false)); // adj matrix vector check ( ..
c++/백준 문제 풀이 2022. 8. 18. 19:43
[C++][자료구조 Stack] 백준 10828번 문제 풀이

백준 10828 문제 자료 구조 Stack 구현 Stack Class를 직접 구현하여 사용하였다. Code // BaekJun 10828 // Title : Stack // URL : https://www.acmicpc.net/problem/10828 /* 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 ..
c++/백준 문제 풀이 2022. 7. 24. 21:14
[C++] 백준 5397번 풀이

백준 5397 문제 시간 제한은 1초 문자열의 길이는 최대 100만 시간 복잡도 O(N^2) 으로는 풀 수 없고 시간 복잡도 O(nlogn) or O(N) 으로 풀어야 한다. Linear 만에 풀기 위해 list + iterator를 사용하였다. Code // BaekJoon 5397 // Title : 키로거 // URL : https://www.acmicpc.net/problem/5397 /* 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀..
c++/백준 문제 풀이 2022. 7. 24. 21:04
[C++][집합 / 자료구조] 백준 1717번 풀이 및 설명

Union - Find 알고리듬을 사용하면 쉽게 해결할 수 있는 문제이다. 다만 이 문제는 시간 초과가 발생하기 때문에 시간을 줄이기 위해 코드를 완성도 있게 짤 필요가 있다. 문제 알고리듬 ① 0 a b 형태로 주어진 경우 union을 통해 집합을 합쳐 주면 된다. ② 1 a b 형태로 주어진 경우 a , b의 find 값이 같다면 YES 출력 다르다면 NO 출력 위의 과정을 모든 입력값에 대하여 시행 하면 된다. 시간 단축 방법 1) stdio 스트림 과의 동기화 취소 cin.tie(NULL);cout.tie(NULL); ios_base::sync_with_stdio(false); 위의 코드를 추가해 주면 cin , cout이 훨씬 빠르게 돌아간다. 자세한 설명은 아래 글 참고..! 2022.07.0..
c++/백준 문제 풀이 2022. 7. 1. 22:07
[C++][Graph] 백준 1197번 문제 풀이 및 설명

백준 1197번 문제는 MST( Minimum - Spanning -Tree )를 구하는 문제이다. 알고리듬으로 Union - Find 를 이용하여 구하면 간단하게 구할 수 있다. 문제 알고리듬 ① 입력 Edge들을 먼저 가중치 기준으로 오름차순 정렬 한다. - 정수 A,B,C 를 tuple 사용하여 묶어서 vector에 저장 - algorithm stl의 sort 함수 사용 (가중치 기준 정렬이므로 cmp 함수 추가) ② 정렬된 Edge들을 하나씩 꺼내며 싸이클이 생기는 지 확인 (Tree 이기 때문에 싸이클이 생기면 안됨) - 정렬된 edge들을 하나씩 꺼내며 정수 A,B의 find 값이 같은 지 확인 - 같다면 Union(A,B) 해주고 다르다면 무시 - 같을 때 Union 해주면서 그 edge의 ..
c++/백준 문제 풀이 2022. 7. 1. 21:57
[C++][코딩테스트] 시간 부족 문제 해결 꿀팁 정리( endl , ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL) )

알고리듬 문제를 풀 때 시간이 굉장히 중요한데요 당연 시간 복잡도가 적게 드는 알고리듬을 선택하는 것이 관건이지요. 하지만 그 외에도 실행 시간을 줄여주는 꿀팁들이 있습니다. 이것 들을 습관화 해서 더 좋은 코드들로 발전 시켜 봅시다. ※ 참고 : C++에서의 팁입니다. 1) endl 대신 \n 사용 cout 을 해줄 때 다들 endl을 많이들 사용하시는데요. endl은 개행 문자 출력 + 버퍼 비우기 를 시행하기 때문에 시간이 더 많이 걸립니다. cout
c++/백준 문제 풀이 2022. 7. 1. 18:54
Prev 1 2 3 Next