자료구조9 [백준][자료 구조] 1620 나는야 포켓몬 마스터 이다솜 c++구현 목차 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 문제 구현 방향 탐색 시간을 줄이기 위해서 string-int형식은 시간 복잡도가 O(logN)이 나오는 map을 이용해야 한다. int-string형식은 array는 O(1) map은 O(logN)이므로 어떤 것을 써도 크게 시간 차이는 나지 않는다. 문제 구현 시 주의점 ios_base::sync_with_stdio(false); 이것으로 입출력 시간을 .. 2024. 3. 28. [알고리즘] DFS c++ 구현 및 설명 목차 dfs의 정의 및 특징 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다. 그래프의 정점을 발견하는 가장 단순하고 고전적인 방법이다. bfs보다는 비교적 구현이 간단하다. dfs 구현 시 시간 복잡도 인접 리스트: O(V +E) 1 2 3 4 3 4 2 3 4 5 1 이런식으로 각 노드마다 길이가 달라 O(V +E)시간이 걸린다. 희소한 그래프일 시 추천하는 방법이다. 인접 행렬: O(V^2) x 1 2 3 4 5 1 1 1 1 1 1 2 0 1 1 0 1 3 0 0 1 1 0 4 0 1 0 1 1 5 1 0 0 1 1 이런식으로 노드의 관계를 나타내 주어 O(V^2) 시간이 걸린다. 조밀한 그래프일 시 추천하는 방법이다. dfs의 구현 나는 재귀적인 방.. 2024. 2. 7. [백준] 10866 덱 c++ 구현 목차 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 덱의 이해 덱은 스택과 큐를 합쳐놓은 것으로 양방향 연결리스트를 구현해 보았다면 무리없이 구현 할 수 있다. 덱의 ADT 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조라고 이해하면 된다. 아래 코드는 일반적인 헤더파일의 모습이다. //Deque.h #ifndef __DEQUE_H__ #define __DEQUE_H__ #define TRUE 1 #.. 2024. 2. 4. [백준] 2841 외계인의 기타 연주 c++ 구현 목차 https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 www.acmicpc.net 문제 문제 구현 방향 스택에 대해서 공부하는 겸 스택을 구현하고 약간 변형하여 문제를 풀어보았다. 스택 구조 설명 List* ListInit(): 스택의 초기화를 해준다. bool ListisEmpty(): 스택이 비어있으면 true를 반환해준다. void ListPush(int data, int* fingercount): 기존 스택 형태에 finge.. 2024. 1. 27. 이전 1 2 3 다음 728x90
