1. 프로그래머스 - 입실퇴실
더보기
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> enter, vector<int> leave) {
vector<int> answer(enter.size());
vector<bool> room(enter.size());
int num_people = 0;
int leave_idx = 0;
for(auto entry : enter)
{
//지금 방에있는애들 만남횟수 1증가
int num_left_checked = num_people;
for(size_t i=0 ; i < enter.size() && num_left_checked > 0;++i)
{
if (room[i] == true)
{
++answer[i];
--num_left_checked;
}
}
//신입추가
room[entry - 1] = true;
answer[entry - 1] += num_people;
++num_people;
//내보낼 수 있는만큼 다 내보낸다
for( ;leave_idx < enter.size();++leave_idx)
{
int out = leave[leave_idx] - 1;
if (room[out])
{
room[out] = false;
--num_people;
}
else
break;
}
}
return answer;
}2. 백준 2003 - 수들의 합 2 (투 포인터 알고리즘)
더보기
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
vector<int> nums(N);
for(size_t ni = 0; ni < N ; ++ni)
cin >> nums[ni];
int l= 0, r = 0, sum = 0, ans = 0;
while(true)
{
if (sum > M)
sum -= nums[l++];
else if (M == sum)
{
++ans;
sum -= nums[l++];
}
else
{
if (r == N) break;
sum += nums[r++];
}
}
cout << ans;
return 0;
}3. 백준 3079 - 입국심사 (이분 탐색)
더보기
#include <vector>
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, num;
cin >> N >> num;
vector<int> T(N);
for(int k=0;k<N;++k) cin >> T[k];
long long lo = 1, hi = 1000000000000000000; //10e18
while(lo < hi)
{
const long long mid = (lo + hi) / 2;
long long capability = 0;
for(int k=0;k<N;++k)
{
capability += mid / T[k];
if (capability >= num)
break;
}
if(capability >= num)
hi = mid;
else
lo = mid + 1;
}
cout << hi;
return 0;
}
4. 백준 11657 - 타임머신 (벨만 포드)
더보기
#include <vector>
#include <iostream>
using namespace std;
const long long INF = 1e18;
struct Path
{
int dst;
int time;
Path(int dst, int time) : dst{dst}, time{time} {}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<Path>> paths(N+1);
for(int i=0;i<M;++i)
{
int from, to, cost;
cin >> from >> to >> cost;
paths[from].emplace_back(to, cost);
}
vector<long long> times(N + 1, INF);
times[1] = 0;
for(int cnt=0;cnt<N;++cnt)
for(int i=1;i <= N;++i)
for(const auto &path : paths[i])
if(times[i] != INF)
{
long long newCost = times[i] + path.time;
if(newCost < times[path.dst])
{
times[path.dst] = newCost;
}
}
for (int i = 1; i <= N; ++i)
for (const auto &path : paths[i])
if (times[i] != INF)
{
long long newTime = times[i] + path.time;
if (newTime < times[path.dst])
{
cout << -1;
return 0;
}
}
for(int i=2;i<=N;++i)
{
if (times[i] == INF) cout << "-1\n";
else cout << times[i] << "\n";
}
return 0;
}
5. 백준 2336 - 굉장한 학생 (세그먼트 트리)
더보기
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
constexpr int treeSize = 500001;
constexpr int INF = 987654321;
struct student
{
int x, y, z;
bool operator<(const student& rhs)
{
return x < rhs.x;
}
};
void update(int idx, int val, vector<int> & tree)
{
idx += treeSize;
tree[idx] = min(tree[idx], val);
while (idx > 1) {
idx >>= 1;
tree[idx] = min(tree[idx << 1], tree[idx << 1 | 1]);
}
}
int query(int left, int right, const vector<int> & tree)
{
int ret = INF;
for (left += treeSize, right += treeSize; left <= right; left >>= 1, right >>= 1) {
if (left % 2 == 1) {
ret = min(ret, tree[left++]);
}
if (right % 2 == 0) {
ret = min(ret, tree[right--]);
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N;
cin >> N;
vector<int> tree(treeSize << 1, INF);
vector<student> students(treeSize);
int rank;
for (int i = 1; i <= N; ++i) {
cin >> rank;
students[rank].x = i;
}
for (int i = 1; i <= N; ++i) {
cin >> rank;
students[rank].y = i;
}
for (int i = 1; i <= N; ++i) {
cin >> rank;
students[rank].z = i;
}
sort(students.begin()+1, students.begin() + N + 1);
int num_losers = 0;
for (int i = 1; i <= N; i++) {
int rank3rd = query(0, students[i].y - 1, tree);
if (rank3rd != INF && rank3rd < students[i].z) {
num_losers++;
}
update(students[i].y, students[i].z, tree);
}
cout << N - num_losers << '\n';
return 0;
}
6. 백준 11403 - 경로 찾기 (플로이드 와샬)
더보기
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N;
cin >> N;
vector<vector<bool>> graph(N, vector<bool>(N, false));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
{
int hasPath;
cin >> hasPath;
graph[i][j] = hasPath == 1;
}
for(int k=0;k<N;++k)
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
for(int i=0;i<N;++i)
{
for (int j = 0; j < N; ++j)
cout << (graph[i][j] ? 1 : 0) << ' ';
cout << "\n";
}
return 0;
}
7. 프로그래머스 - 행렬 테두리 회전하기
더보기
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> make_matrix(size_t rows, size_t columns)
{
int cnt = 1;
vector<vector<int>> ret(rows, vector<int>(columns));
for (size_t i = 0; i < rows; ++i)
for (size_t j = 0; j < columns; ++j)
ret[i][j] = cnt++;
return ret;
}
vector<pair<int, int>> get_coords_to_rotate(int x1, int y1, int x2, int y2)
{
vector<pair<int, int>> coords;
const int predicted_size = (x2 - x1 + 1) * 2 + (y2 - y1 + 1) * 2 - 1;
coords.reserve(predicted_size);
for (int x = x1 - 1; x < x2 - 1; ++x)
coords.emplace_back(x, y1 - 1);
for (int y = y1 - 1; y < y2 - 1; ++y)
coords.emplace_back(x2 - 1, y);
for (int x = x2 - 1; x > x1 - 1; --x)
coords.emplace_back(x, y2 - 1);
for (int y = y2 - 1; y > y1 - 1; --y)
coords.emplace_back(x1 - 1, y);
return coords;
}
void rotate(vector<vector<int>> & matrix, const vector<int> & query, vector<int> & result)
{
auto coords = get_coords_to_rotate(query[1], query[0], query[3], query[2]);
int len = coords.size();
int prev = matrix[coords[len-1].second][coords[len - 1].first];
int min = prev;
for(int i=0;i<len;++i)
{
swap(prev, matrix[coords[i].second][coords[i].first]);
if (prev < min)
min = prev;
}
result.emplace_back(min);
}
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
vector<int> answer;
auto mat = make_matrix(rows, columns);
for(auto query : queries)
{
rotate(mat, query, answer);
}
return answer;
}
8. 백준 17412 - 도시 왕복하기1 (네트워크 유량)
더보기
#include <vector>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
constexpr int MAX = 401;
constexpr int SOURCE = 1;
constexpr int SINK = 2;
int c[MAX][MAX];
int f[MAX][MAX];
vector<int> paths[MAX];
int r(int from, int to)
{
return c[from][to] - f[from][to];
}
bool try_flow()
{
vector<int> parent(MAX, -1);
queue<int> q;
q.emplace(SOURCE);
while(false == q.empty())
{
int here = q.front(); q.pop();
if (here == SINK) break;
for(int there : paths[here])
{
if(r(here,there) > 0 && parent[there] == -1)
{
parent[there] = here;
q.emplace(there);
}
}
}
if (parent[SINK] == -1) return false;
for(int to = SINK; to != SOURCE ; to = parent[to])
{
int from = parent[to];
++f[from][to];
--f[to][from];
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
size_t N, P;
cin >> N >> P;
int from, to;
memset(c, 0x00, sizeof(c));
memset(f, 0x00, sizeof(f));
for(size_t cnt=0;cnt < P;++cnt)
{
int from, to;
cin >> from >> to;
c[from][to] = 1;
paths[from].emplace_back(to);
paths[to].emplace_back(from);
}
int ans = 0;
while(try_flow())
++ans;
cout << ans;
return 0;
}
9. 백준 14942 - 개미 (희소 테이블)
더보기
#include <iostream>
#include <vector>
constexpr int MAX = 100001;
using namespace std;
class Solver
{
public :
void solve()
{
read();
calc_answer();
print_answer();
}
private:
void read()
{
cin >> n;
path.resize(n + 1);
energy.resize(n + 1);
answer.resize(n + 1);
for (int i = 1; i <= n; i++)
cin >> energy[i];
for (int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
path[a].emplace_back(b, c);
path[b].emplace_back(a, c);
}
}
void calc_answer()
{
vector<pair<int, int>> costs{ { 0, 0 } };
dfs(1, 0, costs);
answer[1] = 1;
}
void print_answer()
{
for (int i = 1; i <= n; i++)
cout << answer[i] << '\n';
}
int binary_search(vector<pair<int, int>>& costs, int energy)
{
int lastValue = costs.back().second;
int left = 0, right = costs.size() - 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
int idx = mid - 1 >= 0 ? mid - 1 : 0;
int curTarget = lastValue - costs[idx].second;
if (curTarget <= energy)
right = mid;
else
left = mid;
}
int idx = right - 1 >= 0 ? right - 1 : 0;
if (lastValue - costs[idx].second > energy)
return -1;
return right;
}
void dfs(int from, int to, vector<pair<int, int>>& costs)
{
int closest = binary_search(costs, energy[from]);
if (closest == -1)
answer[from] = from;
else
answer[from] = costs[closest].first;
for (auto& adj : path[from]) {
if (adj.first != to) {
costs.emplace_back(from, costs.back().second + adj.second);
dfs(adj.first, from, costs);
costs.pop_back();
}
}
}
private:
int n;
vector<int> answer;
vector<int> energy;
vector<vector<pair<int, int>>> path;
};
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
Solver().solve();
return 0;
}10. 백준 13161 - 분단의 슬픔 (디닉 알고리즘)
더보기
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
constexpr int MAX = 502;
constexpr int SOURCE = 0;
int SINK = -1;
constexpr int NONE = -1;
constexpr int INF = 987654321;
int N;
int C[MAX][MAX];
int F[MAX][MAX];
int group[MAX]; // 1 : A진영, 2: B진영, 0: 상관없음.
constexpr int A = 1, B = 2, DC = 0;
int level[MAX];
void read()
{
cin >> N;
SINK = N + 1;
for (int i = 1; i <= N; ++i)
cin >> group[i];
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
cin >> C[i][j];
group[SINK] = group[SOURCE] = DC;
//source, sink끼리 묶어줌
for (int i = 0; i <= SINK; ++i)
{
int sum_source = 0, sum_sink = 0;
if (group[i] == DC)
{
for (int j = 1; j <= N; ++j)
{
if (group[j] == A)
sum_source += C[i][j];
else if (group[j] == B)
sum_sink += C[i][j];
}
}
C[SOURCE][i] = C[i][SOURCE] = sum_source;
C[i][SINK] = C[SINK][i] = sum_sink;
}
}
int calc_base_cost()
{
int base = 0;
for(int i=1;i<=N;++i)
{
if (group[i] == A)
{
for (int j = 1; j <= N; ++j)
{
if(group[j] == B)
{
base += C[i][j];
}
}
}
}
return base;
}
void TEST_read()
{
for (int i = 1; i <= N; ++i)
{
if (group[i] == DC)
{
cout << "for " << i << " : " << " SOURCE = " << C[SOURCE][i] << " , SINK = " << C[i][SINK] << endl;
}
}
}
void calc_level()
{
//bfs 방식으로 레벨 세팅
queue<int> q;
level[SOURCE] = 0;
level[SINK] = NONE;
for (int i = 1; i <= N; ++i)
level[i] = NONE;
q.emplace(SOURCE);
int cur_level = 0;
while (false == q.empty())
{
++cur_level;
int cur = q.front(); q.pop();
for (int i = 1; i <= SINK; ++i)
{
if (level[i] == NONE && group[i] == DC) //도달한적 없음
{
int res = C[cur][i] - F[cur][i];
if (res > 0) //잔여용량 있음
{
q.emplace(i);
level[i] = cur_level;
}
}
}
}
}
void print_level()
{
cout << "CALC LEVEL : ";
for (int i = SOURCE; i <= SINK; ++i)
{
cout << level[i] << " ";
}
cout << endl;
}
int flow_to_sink(int cur, int cur_flow, vector<int> & last_visited)
{
if (cur == SINK) return cur_flow;
for(int i=last_visited[cur] + 1;i<=SINK;++i)
{
last_visited[cur] = i;
if (group[i] != DC) continue;
if (level[cur] + 1 != level[i]) continue;
int res = C[cur][i] - F[cur][i];
if (res <= 0) continue;
if (cur_flow > res)
cur_flow = res;
int flow_sent = flow_to_sink(i, cur_flow, last_visited);
if(flow_sent > 0)
{
F[cur][i] += flow_sent;
F[i][cur] -= flow_sent;
return flow_sent;
}
}
return 0;
}
vector<bool> calc_is_A_side()
{
vector<bool> visited(MAX, false);
queue<int> q;
visited[SOURCE] = true;
q.emplace(SOURCE);
while(false == q.empty())
{
int cur = q.front(); q.pop();
for(int i=1;i<=N;++i)
{
if (visited[i] || group[i] != DC) continue;
int res = C[cur][i] - F[cur][i];
if(res > 0)
{
visited[i] = true;
q.emplace(i);
}
}
}
for(int i=1;i<=N;++i)
{
if (group[i] == A) visited[i] = true;
else if (group[i] == B) visited[i] == false;
}
return visited;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
read();
int max_flow = calc_base_cost();
while(true)
{
calc_level();
if (level[SINK] == NONE) break;
vector<int> last_visited(SINK, 0);
while(true)
{
int flow_sent = flow_to_sink(SOURCE, INF, last_visited);
if (flow_sent == 0) break;
max_flow += flow_sent;
}
}
cout <<max_flow << "\n";
auto is_A_side = calc_is_A_side();
for(int i=1;i<=N;++i)
if (is_A_side[i]) cout << i << " ";
cout << "\n";
for (int i = 1; i <= N; ++i)
if (false == is_A_side[i]) cout << i << " ";
cout << "\n";
return 0;
}
11. 백준 1298 - 노트북의 주인을 찾아서 (이분 매칭)
더보기
#include <iostream>
#include <vector>
using namespace std;
constexpr int NONE = -1;
int N;
vector<vector<int>> adjs;
vector<int> bMatch;
bool dfs(int a, vector<bool>& visited)
{
if (visited[a]) return false;
visited[a] = true;
for(auto b : adjs[a])
{
if(bMatch[b] == NONE || dfs(bMatch[b], visited))
{
bMatch[b] = a;
return true;
}
}
return false;
}
int main()
{
int M;
cin >> N >> M;
adjs.resize(N+1);
bMatch.resize(N + 1, NONE);
while(M-- > 0)
{
int a, b;
cin >> a >> b;
adjs[a].emplace_back(b);
}
int ans = 0;
for(int i=1;i<=N;++i)
{
vector<bool> visited(N + 1, false);
if(dfs(i, visited))
++ans;
}
cout<<ans;
return 0;
}
12. 백준 11408 - 열혈강호 5 (MCMF (SPFA))
더보기
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> c, f; //capacity, flow
vector<vector<pair<int,int>>> adj; //first = 타겟 정점, second = 비용
constexpr int INF = 987654321;
int src = 0, snk = 0;
int N, M;
int m2idx(int m)
{
return m + N;
}
void read()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> M;
//일(M)은 마지막 직원 다음의 인덱스부터 시작 (예, 직원 5명 일 7개면 첫 번째일의 인덱스는 6, 마지막은 12, 싱크는 13)
snk = N + M + 1;
c.resize(snk + 1, vector<int>(snk + 1, 0));
f.resize(snk + 1, vector<int>(snk + 1, 0));
adj.resize(snk + 1);
for (int u = 1; u <= N; ++u)
{
int num_work;
cin >> num_work;
while (num_work-- > 0)
{
int v, cost;
cin >> v >> cost;
v += N; //일의 인덱스는 마지막 직원의 인덱스 다음부터 시작
adj[u].emplace_back(v, cost);
adj[v].emplace_back(u, -cost); //역방향은 음의 비용
c[u][v] = 1;
}
adj[src].emplace_back(u, 0); //소스->직원 으로 가는 경로 추가
c[src][u] = 1;
}
for(int m = N + 1 ; m < snk ; ++m)
{
adj[m].emplace_back(snk, 0); //일-> 싱크로의 경로 추가
c[m][snk] = 1;
}
}
int flow_once() //SPFA 알고리즘 사용, 벨먼포드도 가능
{
vector<int> parent(snk + 1, -1);
vector<bool> isInQ(snk + 1, false);
vector<int> costs(snk + 1, INF);
queue<int> q;
costs[src] = 0;
isInQ[src] = true;
q.emplace(src);
while(false == q.empty())
{
int u = q.front(); q.pop();
isInQ[u] = false;
for(auto e : adj[u])
{
int v = e.first;
int cost = e.second;
int r = c[u][v] - f[u][v];
if (r <= 0) continue;
int new_cost = costs[u] + cost;
if (new_cost >= costs[v]) continue;
costs[v] = new_cost;
parent[v] = u;
if(false == isInQ[v])
{
q.emplace(v);
isInQ[v] = true;
}
}
}
if (parent[snk] == -1) //더이상 경로 없음
return -1;
//여기서는 snk로 가는 최단경로가 구해져 있어야 한다.
for(int v = snk; v != src; v=parent[v])
{
int u = parent[v];
++f[u][v];
--f[v][u]; //1씩 흘려준다.
}
return costs[snk];
}
int main()
{
read();
int num_work = 0, total_cost = 0;
while(true)
{
int cost = flow_once();
if (cost == -1) break;
++num_work;
total_cost += cost;
}
cout << num_work << "\n" << total_cost;
return 0;
}
13. 백준 11585 - 속타는 저녁 메뉴 (KMP)
더보기
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> get_p(const vector<char> & str)
{
vector<int> p(str.size(), 0);
int j = 0;
for(size_t i = 1; i < str.size();++i)
{
while(j>0 && str[i] != str[j])
j = p[j - 1];
if (str[i] == str[j])
p[i] = ++j;
}
return p;
}
int count_match(const vector<char> & src, const vector<char> & target)
{
int cnt = 0;
auto p = get_p(target);
size_t j = 0;
const size_t len = src.size() * 2 - 1;
for(size_t i = 0;i<len;++i)
{
const auto idx = i % src.size();
while (j > 0 && src[idx] != target[j])
j = p[j - 1];
if(src[idx]==target[j])
{
if (j == target.size() - 1)
{
++cnt;
j = p[j];
}
else
++j;
}
}
return cnt;
}
int get_gcd(int a, int b)
{
if (b == 0) return a;
return get_gcd(b, a%b);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
vector<char> target(N);
vector<char> src(N);
for(int i =0;i<N;++i)
cin >> target[i];
for (int i = 0; i < N; ++i)
cin >> src[i];
int n = 0, d = N;
n = count_match(src, target);
const int gcd = get_gcd(d, n);
n /= gcd;
d /= gcd;
cout << n << '/' << d;
return 0;
}
14. 백준 3736 - System Engineer (호프크로프트-카프 알고리즘)
더보기
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Data
{
public:
Data(int n)
{
N = n;
A.resize(N, -1);
B.resize(N, -1);
a_level.resize(N, -1);
adj.resize(N);
matched.resize(N);
}
int N;
vector<bool> matched;
vector<int> A, B, a_level;
vector<vector<int>> adj;
};
void set_level(Data& data)
{
queue<int> q;
for(int a=0;a<data.N;++a)
{
if (false == data.matched[a])
{
data.a_level[a] = 0;
q.emplace(a);
}
else
data.a_level[a] = -1;
}
while(false == q.empty())
{
int a = q.front(); q.pop();
for(int b : data.adj[a])
{
if(data.B[b] != -1 && data.a_level[data.B[b]] == -1)
{
data.a_level[data.B[b]] = data.a_level[a] + 1;
q.push(data.B[b]);
}
}
}
}
bool set_aug_flow(int a, Data& data)
{
for(int b : data.adj[a])
{
//매칭이 아직 안 됐거나, 증가경로에 포함 가능한 매칭
if(data.B[b] == -1 ||
data.a_level[data.B[b]] == data.a_level[a] + 1 && set_aug_flow(data.B[b], data))
{
data.matched[a] = true;
data.A[a] = b;
data.B[b] = a;
return true;
}
}
return false;
}
int main()
{
int N;
while (scanf("%d", &N) > 0)
{
Data data(N);
for (int i = 0; i < N; i++) {
int job, J;
scanf("%d: (%d)", &job, &J);
for (int j = 0; j < J; j++) {
int server;
scanf("%d", &server);
data.adj[job].push_back(server - N);
}
}
int num_match = 0;
while(true)
{
set_level(data);
int num_aug_flow = 0;
for(int a = 0 ; a < N; ++a)
{
if (false == data.matched[a] && set_aug_flow(a, data))
++num_aug_flow;
}
if (num_aug_flow == 0) break;
num_match += num_aug_flow;
}
printf("%d\n", num_match);
}
return 0;
}