1. Day06
2. 과제 발표
- Day05 Blueprint Level Design 과제 발표
- 다른 사람들의 아이디어와 구현 방식에대해 볼 수 있는 기회
3. 개인공부
- C++ 코딩테스트 완전정복 강의 (2-5, 3-1)
- 효율적인 코드 구현하기
- 백터 vs 덱, 정렬이 필요없는데 정렬하는 경우, 문자열을 결합하는 경우(+연산자 보다 +=, append()가 더 효율적임), autu vs aotu&
- 재귀 함수
- 실버2 11724번 연결 요소의 개수(그래프) 오답
- 방향없는 간선을 단방향이라고 알아들어서 로직을 잘못 짬
// 실버2 11724번 연결 요소의 개수(그래프)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> graph;
vector<bool> visited;
int c = 0;
void DFS(int node)
{
visited[node] = true;
int next = graph[node];
if (!visited[next])
{
DFS(next);
c++;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
graph.resize(M + 1);
visited.resize(N + 1);
for (int i = 1; i <= M; i++)
{
int x, y;
cin >> x >> y;
graph[x] = y;
}
DFS(1);
cout << c << '\n';
return 0;
}
- 실버2 11724번 연결 요소의 개수(그래프) 개선
// 실버2 11724번 연결 요소의 개수(그래프)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 인접 리스트로 그래프 표현 (정점 최대 1000개)
//vector<int> graph[1001];
//미리 할당하기보다 유동적으로 쓰고싶어서 아래로 변경
vector<vector<int> graph;
// 각 정점의 방문 여부
vector<bool> visited;
// 연결 요소 개수
int c = 0;
// DFS: 현재 정점에서 연결된 모든 정점 탐색
void DFS(int node)
{
visited[node] = true;
// 현재 정점과 연결된 모든 정점 확인
for (int i = 0; i < graph[node].size(); i++)
{
int next = graph[node][i];
if (!visited[next])
{
DFS(next);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// N: 정점 개수, M: 간선 개수
int N, M;
cin >> N >> M;
visited.resize(N + 1, false);
graph.resize(N + 1);
// 간선 정보 입력 (무방향 그래프이므로 양방향 저장)
for (int i = 1; i <= M; i++)
{
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
// 모든 정점을 확인하며 연결 요소 탐색
// 방문하지 않은 정점 발견 = 새로운 연결 요소 시작
for (int i = 1; i <= N; i++)
{
if (!visited[i])
{
// 해당 연결 요소의 모든 정점 방문
DFS(i);
// 연결 요소 개수 증가
c++;
}
}
cout << c << '\n';
return 0;
}
- 실버2 18870번 좌표 압축(정렬)
- 처음 시도 → 백터v를 pair를 사용해서 (인덱스, 입력값) 순으로 입력하고 second 기준으로 정렬 및 압축 좌표값을 구한다음 벡터 result의 result[v[i].first]에 구한 압축 좌표값을 입력 하고 출력함
// 실버2 18870번 좌표 압축(정렬)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// pair의 second 기준으로 정렬
bool compare(pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<pair<int, int>> v(N);
vector<int> result(N);
for (int i = 0; i < N; i++)
{
v[i].first = i;
cin >> v[i].second;
}
sort(v.begin(), v.end(), compare);
int answer = 0;
// 압축 좌표값을 result 벡터에 입력
for (int i = 0; i < N; i++)
{
if (i == 0)
{
result[v[i].first] = answer;
}
else
{
if (v[i].second != v[i - 1].second)
{
answer++;
}
result[v[i].first] = answer;
}
}
for (const auto& list : result)
{
cout << list << " ";
}
return 0;
}
- 실버2 18870번 좌표 압축(정렬) 개선
- 일반적 벡터에 값을 입력하고 정렬을 위한 벡터에 복사 한다음 중복 제거 이분탐색(lower_bound())함수를 이용해 원본의 v[i]값이 정렬된 값의 몇번째 인덱스인지 찾은 다음 출력
- 좀더 짧고 보기좋다는 점 외에 효율적인 측면에서는 비슷함 단순 압축 좌표찾기 부분에서는 pair 방식이 O(N)으로 빠르지만 큰 차이는 없음
// 실버2 18870번 좌표 압축(정렬)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++)
{
cin >> v[i];
}
// 원본 복사 후 정렬 + 중복 제거
vector<int> sorted_v = v;
sort(sorted_v.begin(), sorted_v.end());
sorted_v.erase(unique(sorted_v.begin(), sorted_v.end()), sorted_v.end());
// 이분 탐색으로 압축된 좌표 출력
for (int i = 0; i < N; i++)
{
cout << lower_bound(sorted_v.begin(), sorted_v.end(), v[i]) - sorted_v.begin() << " ";
}
return 0;
}
4. 내일 일정 : 라이브 세션 및 개인공부(이분 탐색 조금 더 풀어보기)
