해당 포스팅은 "코딩 테스트 합격자 되기 C++편" 의 책 및 강의를 보며 포스팅 한 내용입니다.
[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런
dremdeveloper | 코딩 테스트 합격을 위한 C++ 강의, 책 없이도 가능! 저자와 직접 소통 가능한 커뮤니티 제공!, [사진]여기에 문의 하세요https://open.kakao.com/o/gX0WnTCf📘 코딩 테스트 합격자 되기 - C++편
www.inflearn.com
📝내용
그래프(Graph)
1. 정의
노드와 간선을 이용한 비선형 자료구조
- 목적에 따라 간선의 가중치나 방향이 있을 수 있음.
1. 노드 : key와 value가 있음.
2. 가중치 : 노드와 노드 사이를 이어주는 무게
3. 방향 : 노드와 노드 사이의 방향 관계를 표시
4. 사이클 : 노드의 관계가 순환이 되는 현상
- 이차원 배열로 그래프 간의 관계, 가중치, 방향을 표시한다.
- 메모리 낭비가 심하지만, 노드사이의 간선 존재 여부를 한번에 확인할 수 있다(접근 용이)
- 인접리스트는 1개의 배열을 만들어 해당 key값과 관련된 노드들을 리스트로 연결한 것이다.
- 예를 들어 key값 1에 2와 3이 연결되어 있다면 1->2->3 으로 표현할 수 있다.
- 노드를 struct로 만들어 vertex, weight, next를 만들어 관리할 수 있다.
- 간선의 개수를 Node의 개수만큼만 추가되기 때문에 인접리스트는 메모리 낭비가 없다.
- vector<pair<int,int>> 로 구현을 할 수 있다.
- 특점 정점의 간선을 찾아 수정하는 경우는 인접행렬이 좋다.
- 노드의 개수가 많을 떄는 인접리스트를 써야 한다.(공간을 많이 차지하게 되므로)
- 재귀로 구현, visit는 cout 출력을 통해 방문했다고 하고 출력
- 깊이 우선 탐색의 동작원리, stack에 push할 때, 재귀는 함수를 호출하기 전 방문처리, 함수가 종료, 나갈때는 pop
- 루트노드부터 시작해서 엣지로 이어져있는 노드부터 방문하는 탐색으로, queue를 통해서 구현할 수 있다.
- 루트노드인 A를 넣고 B와 C를 바라본다.
- B와 C를 Queue 컨테이너에 넣고, B와 C의 주변노드를 바라본다.
- B와 C를 방문하면서, B의 이웃노드인 D와 E를 Queue 컨테이너에 넣어준다.
- D와 E를 방문하면서 이웃 노드가 있는지 확인하고 컨테이너에 더이상 노드가 없으면 너비우선탐색을 마친다.
- 그림과 같이 노드,엣지,가중치, 방향이 있는 그래프에서 최단경로를 찾는 알고리즘을 배운다.
- 알고리즘은 다익스트라, 벨만-포드가 있다.
- 여기서 우선순위 큐가 쓰인다고 한다.
- A를 시작노드로 잡고, 다음과 같은 변수들을 선언하여 기록하며 다익스트라 알고리즘을 진행한다.
- 시작 노드를 A로 잡는다.
unordered_set<char> visited;
unordered_map<char, pair<int,char>> um;
// um[방문노드].first == 최소비용
// um[방문노드].second == 직전노드
um[A] = {0, 'A'};
- 시작노드 A 와 인접 노드인 B,C,E 노드와 해당 해당 노드간 연결되어 있는 엣지의 가중치를 확인하며 um을 수정한다.
- 그리고, A를 방문했다고 visited 변수에 기록한다. visited.insert('A');
- 그리고 방문하지 않은 BCDE 중에서 가장 낮은 가중치를 가진 노드를 선택한다.
- 해당 노드와 엣지로 연결되어있는 노드 C를 선택한 후에, E->C와 A->C가 어떤 게 더 작은 비용으로 갈 수 있는지 비교한다.
- 현재는 E->C 루트가 더 작은 형태가 되므로 아래와 같이 수정한다.
- 그리고 visited 변수에 E를 추가한다.
- 다익스트라 알고리즘은 음의 가중치를 가지고 있는 그래프는 제대로 동작이 되질 않는다.
- 그럴때는 벨먼-포드 알고리즘을 사용하자.
2. 그래프의 ADT
그래프의 ADT는 자료구조의 형태가 아니기 때문에 생략하지만 나중에 찾아봤을때 알아보기 쉽게
인접리스트와 인접행렬로 표현의 형태만 저장을 해둔다.
- 인접 행렬
vector<vector<int>> adjMat; //가중치가 없을때는 이진법을 이용해서 구현해준다.
//* adjMat[a][b] = c;
// a : 시작 노드
// b : 끝 노드
// c : 가중치
//
// 장점은 쉬운 구현 및 O(1)인효율적인 접근에 있고, 단점은 많은 메모리 낭비에 있다.
- 인접 리스트
unordered_map<int, vector<pair<int,int>> adjList; // 해시맵의 형태(가중치 있는 버전)
unordered_map<int, vector<int>> adjList2; // 가중치가 없을 때에는 pair가 아닌 일반 vector를 쓴다.
//* adjList[a] = b;
// a : 시작 노드
// b.first : 가중치
// c.second : 도착 노드
// 장점은 메모리낭비가 비교적 적다, 단점은 접근의 시간복잡도가 인접행렬보다 좀 더 길다.3. 문제 풀이
1) 깊이 우선 탐색 순회
a. 문제 설명
깊이 우선 탐색으로 모든 그래프의 노드를 순회하는 함수 Solution()을 작성하세요. 시작 노드는 문자형 start로 주어집니다. graph 배열은 [출발 노드, 도착 노드] 쌍들이 들어있는 배열입니다. 반환값은 그래프의 시작 노드부터 모든 노드를 깊이 우선 탐색으로 탐색한 경로가 순서대로 저장된 배열입니다.
ex)
| graph | start | result |
| (A,B),(B,C),(C,D),(D,E) | 1 | (A,B,C,D,E) |
| (A,B),(A,C),(B,D),(B,E),(C,F),(E,F) | 1 | (A,B,D,E,F,C) |
b. 의사 코드
- 우선 주어진 graph를 인접리스트인 unordered_map 에 넣어서 관리하자.
- BFS는 stack(재귀)의 특성을 가졌으니, 재귀함수를 이용하자.
c. 문제 풀이
#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
unordered_set<char> visit;
unordered_set<char> visit2;
void dfs(unordered_map<char, vector<char>>& graph, char start, unordered_set<char>& visit)
{
cout << start << " ";
visit.insert(start);
for (auto& e : graph[start])
{
if (visit.find(e) == visit.end()) dfs(graph, e, visit);
}
}
void solution(vector<pair<char, char>> graph, char start, unordered_set<char>& visit)
{
unordered_map<char, vector<char>> um;
for (auto& e : graph)
{
auto first = e.first;
auto second = e.second;
um[first].push_back(second);
}
dfs(um, start, visit);
}
int main()
{
vector<pair<char, char>> graph = { {'A','B'},{'B','C'},{'C','D'},{'D','E'}};
vector<pair<char, char>> graph2 = { {'A','B'},{'A','C'},{'B','D'},{'B','E'},{'C','F'} ,{'E','F'} };
solution(graph, 'A', visit);
cout << endl;
solution(graph2, 'A', visit2);
}
d. 문제 후기
- DFS의 기본 구현 문제이다. 보기보다 쉬워서 안보고 DFS를 구현할 수 있게 되었다.
2) 너비 우선 탐색 순회
a. 문제 설명
너비 우선 탐색으로 모든 노드를 순회하는 함수 solution()을 작성하세요. 시작 노드는 정수형 start로 주어집니다. graph 배열은 [출발 노드, 도착 노드] 쌍이 들어 있는 배열입니다. 반환값은 그래프의 시작 노드부터 모든 노드를 너비 우선 탐색한 경로가 순서대로 저장된 배열입니다.
ex)
| graph | start | result |
| (1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(4,8),(5,8),(6,9),(7,9) | 1 | (1,2,3,4,5,6,7,8,9) |
| (0,1),(1,2),(2,3),(3,4),(4,5),(5,0) | 1 | (1,2,3,4,5,0) |
b. 의사 코드
- 우선 주어진 graph를 인접리스트인 unordered_map 에 넣어서 관리하자.
- DFS는 Queue의 특성을 가졌으니, Queue를 잘 이용하는데, 방문 시점을 push로 할지 pop으로 할지 잘 구분하자.
c. 문제 풀이
#include <bits/stdc++.h>
using namespace std;
void bfs(unordered_map<int, vector<int>>& um, int start)
{
queue<int> q;
unordered_set<int> visited;
q.push(start);
visited.insert(start);
cout << start << " ";
while (!q.empty())
{
auto front = q.front();
q.pop();
for (const auto& e : um[front])
{
if (visited.find(e) == visited.end())
{
q.push(e);
visited.insert(e);
cout << e << " ";
}
}
}
}
void solution(vector<pair<int, int>>& graph, int start)
{
unordered_map<int, vector<int>> um;
for (const auto& e : graph)
{
int first = e.first;
int second = e.second;
um[first].push_back(second);
}
bfs(um, 1);
}
int main()
{
vector<pair<int, int>> graph = { {1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{4,8},{5,8},{6,9},{7,9} };
vector<pair<int, int>> graph2 = { {0,1},{1,2},{2,3},{3,4},{4,5},{5,0}};
solution(graph, 1);
cout << endl;
solution(graph2, 0);
}
d. 문제 후기
- BFS의 기본 구현 문제이다. 여기서 가중치가 붙게된다면 우선순위 큐(최소 힙)를 이용하여 최단 경로를 구하는 알고리즘을 만들 수 있다.
3) 다익스트라 알고리즘 구현
a. 문제 설명
주어진 그래프와 시작 노드를 이용하여 다익스트라 알고리즘을 구현하는 solution()함수를 작성하세요. 시작 노드 start, 노드의 개수 numNode, [시작 노드, 도착 노드, 가중치] 형태로 간선 정보를 담은 배열 edges가 인수로 주어집니다. edges에 [2,1,9] 가 있다면 시작 노드 2에서 도착 노드 1까지 가중치가 9인 간선이 있다는 뜻입니다. 시작 노드 start 부터 각 노드까지 최소 비용을 담은 벡터를 반환하는 solution() 함수를 구현하세요.
ex)
| start | numNodes | edges | result |
| 0 | 3 | (0,1,9),(0,2,3),(1,0,5),(2,1,1) | (0,4,3) |
| 0 | 4 | (0,1,1),(1,2,5),(2,3,1) | (0,1,6,7) |
b. 의사 코드
- 일단 각 노드를 연결하는 그림을 그려보자.
c. 문제 풀이
#include <vector>
#include <tuple>
using namespace std;
const int INF = 99999;
const int MAX_NODES = 100;
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];
vector<int> solution(int start, int numNodes, const vector<tuple<int, int, int>> edges) {
//❶ 그래프 및 방문 여부 초기화
for (int i = 0; i < MAX_NODES; ++i) {
fill_n(graph[i], MAX_NODES, INF);
visited[i] = false;
}
//❷ 입력받은 간선 정보를 그래프로 표현
for (const auto& [from, to, weight] : edges) {
graph[from][to] = weight;
}
//❸ 시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
vector<int> distances(numNodes, INF);
distances[start] = 0;
for (int i = 0; i < numNodes - 1; ++i) {
int minDistance = INF;
int closestNode = -1;
//❹ 최소 거리 노드 찾기
for (int j = 0; j < numNodes; ++j) {
if (!visited[j] && distances[j] < minDistance) {
minDistance = distances[j];
closestNode = j;
}
}
//❺ 찾은 노드를 방문 처리
visited[closestNode] = true;
//❻ 인접 노드에 대한 거리 업데이트
for (int j = 0; j < numNodes; ++j) {
int newDistance = distances[closestNode] + graph[closestNode][j];
if (!visited[j] && graph[closestNode][j] != INF && newDistance < distances[j]) {
distances[j] = newDistance;
}
}
}
return distances;
}
//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
using namespace std;
void print(vector<int> vec)
{
copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
cout << endl;
}
int main()
{
print(solution(0, 3, {{0, 1, 9},{0, 2, 3},{1, 0, 5},{2, 1, 1}})); //출력값 : 0 4 3
print(solution(0, 4, {{0, 1, 1}, {1, 2, 5}, {2, 3, 1}})); //출력값 : 0 1 6 7
return 0;
}
d. 문제 후기
- BFS/DFS는 자세히 실습해보질 않아서 많이 어려움을 느끼는 것 같다.
4) 미로 탈출 <-- 12.5% 오답 ⭐⭐⭐⭐⭐
a. 문제 설명
문제 참조
b. 의사 코드
- 처음에는 DFS를 이용해 문제를 풀려고 했으나 잘 풀리지 않았다.
- 이후로 BFS로 문제를 풀어볼려고 하였으나 잘 되지 않았다.
c. 문제 풀이
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
unordered_map<int, vector<pair<char, int>>> um;
unordered_map<char, int> um2;
unordered_set<int> visit;
int bfs(int start, int end)
{
int cnt = -1;
queue<int> q;
int stack = 0;
q.push(start);
while(!q.empty())
{
int front = q.front();
q.pop();
visit.insert(front);
cnt++;
if(front == end) break;
int size = um[front].size();
for(int i = 0; i < size; i++)
{
if(visit.find(um[front][i].second) == visit.end())
{
q.push(um[front][i].second);
}
}
}
//visit.clear();
return cnt;
}
int solution(vector<string> maps) {
int answer = 0;
int row = maps.size();
int col = maps[0].size();
for(int i = 0; i < row; i++)
{
for(int j = 0; j <col; j++)
{
if(maps[i][j] == 'X') continue;
int cur = i*row+j;
int up = (i-1)*row+j;
int down = (i+1)*row+j;
int left = i*row + j - 1;
int right = i*row + j + 1;
if(maps[i][j] == 'S') um2['S'] = cur;
if(maps[i][j] == 'L') um2['L'] = cur;
if(maps[i][j] == 'E') um2['E'] = cur;
if(i-1 >= 0 && maps[i-1][j] != 'X') um[cur].push_back({maps[i-1][j],up});
if(i+1 < row && maps[i+1][j] != 'X') um[cur].push_back({maps[i+1][j],down});
if(j-1 >= 0 && maps[i][j-1] != 'X') um[cur].push_back({maps[i][j-1],left});
if(j+1 < col && maps[i][j+1] != 'X') um[cur].push_back({maps[i][j+1],right});
}
}
if(um[um2['S']].empty()) return -1;
answer = bfs(um2['S'], um2['L']) + bfs(um2['L'], um2['E']);
return answer;
}
d. 문제 후기
- 해시맵과 해시셋이 능사가 아니라는 것을 알았다. 그래프 유형의 문제는 약하다는것을 느꼈었고, 고민끝에 정답을 보고 한줄한줄 분석하여 내것으로 암기하여 풀어보려고 한다.
- 정답 풀이
#include <queue>
#include <string>
#include <vector>
using namespace std;
struct Point //S나 L나 E의 특수한 공간의 위치를 반환
{
int y, x, cnt;
};
int dy[4] = { -1,0,1,0 }; // 상하의 증감값을 표현
int dx[4] = { 0, 1, 0, -1 }; // 좌우의 증감값을 표현
int n, m; // row와 col을 표현
bool isWithinRange(int y, int x) { return 0 <= y && y < n && 0 <= x && x < m; }//21. 상하좌우로 이동했을 시, 배열의 range에 들어가는지 검사
Point findStartPoint(char start, vector<string>& maps)
{
for (int i = 0; i < n; i++) // 7.maps의 row만큼 반복
{
for (int j = 0; j < m; j++) // 8.maps의 col 만큼 반복
{
if (maps[i][j] == start) // 9.start를 검출했다면
{
return { i,j,0 }; //10.start의 위치를 반환
}
}
}
}
int bfs(char start, char end, vector<string>& maps)
{
bool visited[101][101] = { false }; // 4. 방문한 곳들을 이력으로 남기는 배열
queue<Point> q; // 5. bfs를 진행하기 위한 queue 선언
q.push(findStartPoint(start, maps)); // 6. queue에 start 위치를 push해주기
while (!q.empty()) //11. q가 다 빌때까지 반복
{
Point current = q.front(); //12. q의 front를 기준으로 최근 포인트를 저장
q.pop(); //13. current로 저장을 했으니 빼주기
if (maps[current.y][current.x] == end) //14. 현재 위치가 도착점이면
{
return current.cnt; //15. 현재 위치의 cnt를 반환
}
for (int i = 0; i < 4; i++) // 16. 4번 반복? 아...! 상하좌우를 for문으로 표현
{
int ny = current.y + dy[i]; // 17. 현재위치의 y좌표와 증분y축의 값을 더해 위와 아래를 ny에 넣기
int nx = current.x + dx[i]; // 18. 현재위치의 x좌표와 증분x축의 값을 더해 좌측과 우측을 nx에 넣기
// 19. i를 순서대로 하면 위, 오른쪽, 아래, 왼쪽
if (isWithinRange(ny, nx) && !visited[ny][nx] && maps[ny][nx] != 'X') // 20. 배열 내부에 들어 있는 값인지, 방문한 적이 없는지, X가 아닌지 다 조건에 적합하다면, q에 푸쉬한다.
{
q.push({ ny,nx,current.cnt + 1 }); // 22. count를 1 증가시킨 채 이동한 좌표를 푸쉬해준다.
visited[ny][nx] = true; // 23. 방문했다는 위치를 갱신
}
}
}
return -1; // 24. E를 찾지 못했다면 마지막 위치 반환
}
int solution(vector<string> maps)
{
n = maps.size(); // 1. row
m = maps[0].size(); // 2. col
int distanceToL = bfs('S', 'L', maps); // 3. Start 부터 End까지 가는 거리를 cnt로 환산했을 때, bfs 함수를 이용
if (distanceToL == -1) return -1; // 25. bfs가 -1이 되어 돌아왔다면, 목표를 찾지 못했다는 뜻이므로 -1을 리턴
int distanceToE = bfs('L', 'E', maps); // 26. bfs 함수를 다시 목표만 바꾸어 호출
return distanceToE == -1 ? -1 : distanceToL + distanceToE; // 27. -1이 돌아왔다면 -1을, 제대로 카운팅 되었다면 두개의 변수를 합침
}
5) 게임 맵 최단거리 <-- 효율성 전체 오답 ⭐⭐⭐⭐⭐
a. 문제 설명
문제 참조
b. 의사 코드
- 처음에 고민했던 경험을 바탕으로 BFS를 사용하여 풀기로 하였다.
c. 문제 풀이
#include <vector>
#include <queue>
using namespace std;
struct Node
{
int x;
int y;
int cnt;
};
int visit[100][100];
int solution(vector<vector<int>> maps)
{
int answer = -1;
int row = maps.size();
int col = maps[0].size();
queue<Node> q;
q.push({0,0,1}); //시작 위치
while(!q.empty())
{
Node cur = q.front();
q.pop();
visit[cur.y][cur.x]++;
if(cur.x == col-1 && cur.y == row-1)
{
answer = cur.cnt;
return cur.cnt;
break;
}
for(int i = 0; i < 4; i++) // 0은 up, 1은 down, 2는 left, 3은 right
{
if(i == 0 && cur.y-1 >= 0 && maps[cur.y-1][cur.x] && visit[cur.y-1][cur.x] == 0) q.push({cur.x,cur.y-1,cur.cnt+1});
if(i == 1 && cur.y+1 < row && maps[cur.y+1][cur.x] && visit[cur.y+1][cur.x] == 0) q.push({cur.x,cur.y+1,cur.cnt+1});
if(i == 2 && cur.x-1 >= 0 && maps[cur.y][cur.x-1] && visit[cur.y][cur.x-1] == 0) q.push({cur.x-1,cur.y,cur.cnt+1});
if(i == 3 && cur.x+1 < col && maps[cur.y][cur.x+1] && visit[cur.y][cur.x+1] == 0) q.push({cur.x+1,cur.y,cur.cnt+1});
}
}
return answer;
}
d. 문제 후기
- 정답은 모두 맞았으나 효율성체크에서 모두 오답이 떴다.
'GroupStudy > [C++]코딩 테스트 합격자 되기' 카테고리의 다른 글
| [코딩 테스트 합격자 되기] 5주차 - 집합 (0) | 2024.08.06 |
|---|---|
| [코딩 테스트 합격자 되기] 4주차 - 트리 (0) | 2024.08.01 |
| [코딩 테스트 합격자 되기] 3주차 - 해시 (0) | 2024.07.25 |
| [코딩 테스트 합격자 되기] 2주차 - 스택/큐 (0) | 2024.07.13 |
| [코딩 테스트 합격자 되기] C++ - 알고리즘 (0) | 2024.07.11 |