목록c++ (40)

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

[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++] Trie 총정리 / 구현 / 응용 ( Insert , Find )

Trie ◎ 문자열들을 저장하기 위해 사용되는 트리 자료구조 ◎ 각 노드가 26개의 자식 포인터를 가짐 ◎ 빠른 문자열 탐색 속도 1) 작동 원리 문자열들이 저장되어 있는 Trie 의 모습이다. 저장된 문자열 [ rebro , replay , hi , high , algo ] 문자열 한 글자씩 노드에 저장 해두었고 끝나는 지점을 bool finish 변수를 통해 표시 해두었다. ( 빨간색 동그라미 부분 -> finish 변수 true) 문자열 탐색하는 과정 문자열 "High" 를 찾는 다고 가정을 해보겠다. 제일 꼭대기에 있는 Root 노드 에서 High의 첫 글자인 H를 먼저 찾는다. 자식 노드 들 중 H 노드가 존재하기에 H 노드로 이동 할 수 있다. 이동한 뒤 두 번째 글자인 I 를 찾는다. I 노..
c++/data_structure_구현 2022. 7. 23. 18:37
[C++][자료 구조] Map STL 구현 ( RbTree , Template ,Iterator , Operator overloading )

Map STL 구현 우리는 Map STL을 코딩하면서 정말 많이 사용한다. Pair로 저장할 수 있고 , 자동으로 정렬이 되고 , 삽입 / 삭제가 빠르고, … 장점이 되게 많기 때문이다. 오늘은 Map STL을 C++로 구현 해보고 Map에서 사용 된 기능 , 그 구조에 대해서 알아볼 것이다. 한 마디로 Map STL을 완전 뜯어 볼 생각이다. 많은 공부가 될 것이다. Map STL 구현 Full Code Github 주소 : https://github.com/ohinhyuk/MCNL-Study/blob/main/%EA%B3%A0%EC%9C%A4%EB%AF%BC%EA%B5%90%EC%88%98%EB%8B%98%20%EC%8A%A4%ED%84%B0%EB%94%94/week%202/RedBlack%20Tre..
c++/data_structure_구현 2022. 7. 23. 17:35
[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
Prev 1 2 3 4 5 Next