알고Lee즘 스터디
주제: BFS
목표: BFS 7문제 해결
다음 스터디: 22. 1. 6.(목)
다음 스터디 목표: BFS 7문제 해결
이번에 진행하는 강의가 BFS라 약간 긴장했는데,
트리나 그래프에 대한 내용 없이 2차원 평면 내에서 좌표로 BFS를 사용하는 것,
1차원 선에서 값의 변화에 따라 BFS로 추적하는 것 등 새로운 방식으로 문제에 접근 할 수 있게 되어서 재미있었다.
다른 스터디원들보다 푸는데 시간을 많이 투자해서 계속 이렇게 해도 되나 싶지만, 가능한 내에서 기초를 잘 닦아보자
BFS 3문제
| 7569 | 토마토 |
|---|---|
| 7562 | 나이트의 이동 |
| 5427 | 불 |
- 토마토 기존에 풀었던 토마토와 동일한 문제이지만, 3차원 배열을 사용하여 푸는 문제이다.
- 2차원 배열에서는 STL에서 제공하는 pair를 통해 해결했지만,
3차원 위치를 표현하기 위해서 tuple을 사용했다.// pair의 경우(pair는 2개의 값만 가질 수 있다.) queue<pair<int, int> > q; // pair을 가지는 큐를 선언 q.push({1, 2}); // C++11 이상에서 지원하는 중괄호를 통해 페어 제공 pair<int, int> cur = q.front(); // queue 맨 앞 값을 cur에 저장 printf("%d / %d", cur.first, cur.second) // "1 / 2" 출력 // pair 내의 값을 사용하기 위해서는 first, second를 통해 값에 접근한다. //----------------------------------------------------------- // tuple의 경우(tuple은 선언 시에 작성한 자료형의 개수만큼 값을 가질 수 있다.) queue<tuple<int, int, int> > q; // pair와 선언방식은 같다. q.push({1, 2, 3}); // 값을 추가하는 방식도 pair와 유사하게 사용할 수 있다. tuple<int, int, int> cur = q.front(); printf("%d / %d / %d", get<0>(cur), get<1>(cur), get<2>(cur)); // tuple은 값을 가져올 때, std::get<n>(tuple) 함수를 사용한다. - 2차원 배열에서 상하좌우를 접근하는 것과 달리,
3차원 배열은 상하좌우/위 아래 총 6방향을 접근해야 한다.int dx[6] = {1, -1, 0, 0, 0, 0}; // 각 6방향 좌표 설정 int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; int board[101][101][101]; queue<tuple<int, int, int> > q; void BFS() { while (!q.empty()) { tuple<int, int, int> cur = q.front(); q.pop(); for (int i = 0; i < 6; i++) { int nx = get<2>(cur) + dx[i]; // 현재 좌표 + 상/하/좌/우/위/아래 좌표 int ny = get<1>(cur) + dy[i]; // (순서대로) int nz = get<0>(cur) + dz[i]; if (nx < 0 || ny < 0 || nz < 0) continue; if (nx >= x || ny >= y || nz >= z) continue; if (board[nz][ny][nx] == 0) { board[nz][ny][nx] = board[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1; q.push({nz, ny, nx}); } } } }
- 2차원 배열에서는 STL에서 제공하는 pair를 통해 해결했지만,
- 나이트의 이동
- 2차원 평면에서 상하좌우로 이동하는 것과 달리,
나이트의 위치를 중심으로 나이트가 갈 수 있는 모든 방향 확인#define X first #define Y second int board[301][301]; queue<pair<int, int> > q; int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}; int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2}; int BFS() { while (!q.empty()) { pair<int, int> cur = q.front(); q.pop(); if (cur.X == x && cur.Y == y) return board[cur.X][cur.Y]; for (int i = 0; i < 8; i++) { int nx = cur.X + dx[i]; int ny = cur.Y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (board[nx][ny] != -1) continue; board[nx][ny] = board[cur.X][cur.Y] + 1; q.push({nx, ny}); } } return -1; }
- 2차원 평면에서 상하좌우로 이동하는 것과 달리,
- 불: 기존 ‘불!’ 문제에서 테스트 케이스 추가한 버전으로 새로 공부한 내용은 없음
[Go]Mocking
-
Mocking이란?
모의 객체란 주로 객체 지향 프로그래밍으로 개발한 프로그램을 테스트 할 경우 테스트를 수행할 모듈과 연결되는 외부의 다른 서비스나 모듈들을 실제 사용하는 모듈을 사용하지 않고 실제의 모듈을 "흉내"내는 "가짜" 모듈을 작성하여 테스트의 효용성을 높이는데 사용하는 객체이다.
(출처: 위키백과)즉, 테스트를 위한 가짜 객체이다!
-
Mocking을 만드는 이유
위 내용에서 모두 설명이 되지만, 직접적인 예시를 들어보면 내 프로그램에 Countdown이라는 함수가 있고, 해당 함수를 실행하면 5초간 카운트 다운을 한다고 생각하자.
매 테스트마다 해당 함수가 실행되면 멍때리고 기다리는 수 밖에 없는데, 이러한 상황을 만들지 않기 위해 Mocking을 통해 테스트한다.
(테스트 코드에서는 Mocking을 통해 Countdown으로 넘기는 매개변수를 바꿔서 실행이 잘 되는 지 체크만 한다.)(위 예시는 아주 간단하게 설명한 것으로, 큰 프로그램에서는 모킹과 달리 실제 실행 시 더 많은 행위가 발생될 수 있다.)
-
TDD란? (Test-Driven-Development)
테스트 주도 개발은 매우 짧은 개발 사이클을 반복하는 소프트웨어 개발 프로세스 중 하나이다. 개발자는 먼저 요구사항을 검증하는 자동화된 테스트 케이스를 작성한다. 그런 후에, 그 테스트 케이스를 통과하기 위한 최소한의 코드를 생성한다.
(출처: 위키백과)
-
TDD를 하는 이유
TDD는 개발을 번거롭게 하는 방식처럼 보이지만, 아니다.
테스트를 하지 않는 코드는 나쁜 디자인을 가지고,
문제가 생겼을 때 어디가 문제인지 찾기 힘들다.하지만, 자주 테스트된 코드는 더 좋은 디자인을 가지고,
더 좋은 디자인은 테스트를 쉽게 만든다.
-
Mocking을 통해 Test를 할 때, Mocking이 너무 커지는 걸 주의해야 한다.
Mocking을 만드는데, Mocking이 너무 커지는 경우 내 코드가 다른 객체에 대한 의존성이 크다는 걸 뜻한다.
의존성이 많은 코드는 테스트하기도, 에러를 처리하기도 어려움으로 이는 리팩토링을 해야한다는 신호가 된다.
Mocking에 대한 내용은 중요한 것 같은데, 영어라서... 시간이 될 때 돌아와서 다시 공부해야겠다.
