1일 1알고리즘 실천
이번주에는 에라토스테네스의 체, GCD, LCM 부분을 맡았다.
정수론 문제를 평소에 많이 안풀어봤어서 유클리드나 확장된 유클리드 호제법과 같은 개념들을 복습할 좋은 기회였다.
다음주는 자신있는 dp라서 더 즐겁게 할 수 있을것 같다.
이제는 취업 준비에 올인을 해야할 것 같다.
싸피 수료도 했고, 코치도 탈락해버렸으니.. ㅎㅎ
뭐.. 면접 때 첫 질문 듣고 나서부터 난 탈락이구나 싶었다.
아쉽긴 하지만 웹부터 차근차근 다시 해야겠다는 생각이 든다.
| 1월 1주차 결산 (0) | 2022.01.09 |
|---|---|
| 12월 5주차 결산 (0) | 2022.01.02 |
| SSAFY 5기 회고 (0) | 2021.12.25 |
| 12월 3주차 결산 (0) | 2021.12.19 |
| 12월 2주차 결산 (0) | 2021.12.12 |
나는 SSAFY 5기 서울지역 교육생이다.
싸피의 모든 교육과정을 마치고 수료를 했다.
나의 싸피 생활을 돌아보며 회고를 할려고 한다.
1학기에는 자바와 웹, 알고리즘 위주의 학습을 했다.
개인적으로 가장 아쉬움에 남았고, 후회가 되는 학기였다.
나는 싸피 입교 전에 이미 백준 600문제 이상을 푼 상태였고, 소규모지만 대회 수상 경력도 여러번 쌓여 있는 상태였다.
그래서인지 초반에 있었던 모든 알고리즘 수업이 아는 내용이었고, 용고리즘이라고 불릴 정도로 여유가 넘쳤다.
그리고 같은 반 교육생분들과 알고리즘 스터디를 진행하며 더 다양한 문제들과 코드리뷰를 경험했다.
하지만 웹을 배우는 시간에는 모든 내용이 너무 어렵게 느껴졌었고, 순식간에 벽을 느꼈다.
다른 교육생분들께 질문도 하면서 극복하기 위한 노력을 했지만 그날 주어진 과제를 겨우 넘기는 정도였다.
게다가 이해가 안되면 화가나서 알고리즘 문제를 풀러가는 일이 많았다. 물론 그 시간에 한 강의는 스킵이었다.
이런 일들이 많아서 1학기 때는 원하는 목표를 달성하지 못했다.
근데 1학기 성적 우수상을 받았다. 처음에는 멕이는줄 알고 기분이 전혀 좋지 않았다.
아무리 생각해도 알고리즘 비중이 컸던것 같다.
방학이 왔지만 쉬어야겠다는 생각을 전혀 안했다.
뭔가 이 실력에 쉬기에는 양심이 허락하지 않았던것 같다.
웹이랑 안 맞는것 같다는 생각이 들었었고, 열심히 하지않은 자신에게 너무 화가 났었다.
그래서 내 마인드에 변화를 주면서 어떻게든 따라가려는 노력을 했다.
이 때 놀았더라면 중간 퇴소를 하지 않았을까 생각이 든다..
아무튼 시작한 2학기 공통 프로젝트..
1학기 때 좋은 기억이 없었어서 자신감이 많이 떨어진 상태였지만 개성 넘치는 팀원들을 만난 덕분에 프로젝트 하는 내내 재밌었고,
나는 팀장을 맡았지만 오히려 내가 팀원들에게 자기애나 긍정 마인드 등 얻어가는게 많은 프로젝트였다.
서브 프로젝트부터 역할을 나눠서 사전학습을 수행함으로 수월하게 프로젝트를 마무리 할 수 있었던것 같다.
그리고 9시 ~ 21시(가끔 24시)의 코어타임이 있었지만 아무도 불평하지않고, 잘 따라와줘서 너무 고마웠다.
팀원 모두 캐미가 좋아서인지 부탁도 망설임없이 하고, 요구사항에 맞춰서 서로 일을 도와주기도 했다.
그 덕분인지 반에서 1등을 차지했고, 웹에 대한 자신감이 생겨 가장 기억에 남는 프로젝트로 남았다.
그 다음은 특화 프로젝트 시간에 진행한 SSDC 프로젝트.
우선 처음부터 꼬였다. 팀을 꾸리지 못해 남아있던 5명이서 마지막 팀을 꾸렸다.
그래서 걱정이 많이 됐었다. 자동으로 구성된 팀이라 안맞거나 하진 않을지, 새벽 늦게까지 하는 팀원이 있을지 걱정이 됐다.
게다가 처음보는 주제에서 아이디어를 생각해야 하다 보니 주제에 대한 지식도 필요했고, 접근하기가 어려웠다.
하지만 팀원 모두가 사전 학습에 열심히 참여했고, 테스트하는 과정에서 서로 공유도 해가면서 어려운 일을 잘 해낸것 같고, 괜한 걱정이었다는 생각이 들었다.
무엇보다도 현직 개발자의 다양한 컨벤션들과 자신의 코드가 현직 개발자의 깃허브에 머지가 되는것을 보고 팀원 모두가 신기해했다.
결과는 3팀 중 2등을 차지했고, 나름 좋은 경험을 했고, 깃에 대해 많이 알아가는 유익한 시간이었던것 같다.
마지막 자율 프로젝트..
이번에는 VR이라는 주제에 새로운 도전을 했다.
주제도 잘 나왔고, Unity에 적응해서 시나리오를 잘 구성하면 된다는 생각을 했다.
하지만 초반에 팀원 한명이 취업으로 인해 조기 퇴소를 하면서 거의 취업우선 분위기로 바뀐것 같다.
나는 취업보다는 프로젝트가 우선이었지만 팀원이 취업준비를 하는 것을 막을 자격은 없다는 판단을 했다.
그래서 프로젝트 진행속도가 더디게 되었고, 많은 시나리오를 개발하지 못했다는 아쉬움이 많이 남았다.
그래도 취업 준비하느라 바빴을텐데 프로젝트 할때는 정말 열심히 해준것 같아서 너무 고마웠다.
결과는 3등을 했고, UCC도 입상을 했다.
사실 생각하지 못했던 입상이라 당황했지만 팀원 모두가 열심히 한 덕분이라는 생각이 들었고, 마무리를 잘 한것 같아서 다행이라는 생각이 들었다.
벌써 1년 교육과정이 마무리되었고, 수료를 했다.
다른 사람들에게 싸피를 추천하냐고 묻는다면 무조건 추천한다고 할 것이다.
자신의 진로를 결정할 수 있는 기회가 주어지고, 혼자서는 할 수 없는 새로운 경험을 한다는 것이 가장 큰 장점이라고 생각한다.
나는 이곳에서 웹을 처음 접했고, 처음에는 적응을 하지 못했다.
하지만 노력으로 이를 극복했고, 백엔드 개발자가 되기로 결정을 했다.
그리고 이제는 취업 준비를 해야할 때다.
지금까지 배운것들 잘 다듬어서 원하는 곳 가야겠다는 생각이 든다.
ssafy 5기,
1학기 서울 11반,
2학기 SpotLive, 라스트ONE, 오우야 팀
모두 고생많으셨습니다!!
| 12월 5주차 결산 (0) | 2022.01.02 |
|---|---|
| 12월 4주차 결산 (0) | 2021.12.26 |
| 12월 3주차 결산 (0) | 2021.12.19 |
| 12월 2주차 결산 (0) | 2021.12.12 |
| 12월 1주차 결산 (0) | 2021.12.05 |
이번주 역시 CS 스터디를 진행하였다.
1일 1알고리즘 실천
이번주는 알고리즘을 했다.
나는 브루트포스, 순열조합, 힙을 맡아서 공부하였고, 스터디원들에게 설명을 해주었다.
다음주는 에라토스테네스의 체, GCD, LCM이다.
마침 정수론 부분은 제대로 알지 못해서 공부할 기회가 생겨서 좋다.
지금 CS스터디를 진행 중이지만 스터디에서 다루지 않는 Java나 Spring 개념들은 혼자서 해야 할 부분이다.
시간관리 잘해서 감도 찾고, 완벽하게 해야겠다는 생각이 든다.
이번주는 본가에 내려가서 휴식을 취했기 때문에 다음주부터 다시 달려야겠다!
| 12월 4주차 결산 (0) | 2021.12.26 |
|---|---|
| SSAFY 5기 회고 (0) | 2021.12.25 |
| 12월 2주차 결산 (0) | 2021.12.12 |
| 12월 1주차 결산 (0) | 2021.12.05 |
| 11월 4주차 결산 (0) | 2021.11.28 |
https://www.acmicpc.net/problem/9081
9081번: 단어 맞추기
입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알
www.acmicpc.net
문자열이지만 순열에 더 가까운 문제입니다.
주어진 단어의 사전 순으로 바로 다음 단어를 출력하는 문제로, next_permutation을 이용하였습니다.
next_permutation으로 다음 순열을 구하고, 출력하면 됩니다.
만약 마지막 단어라서 다음 순열을 구하지 못하더라도 주어진 단어를 유지하므로 그냥 출력해줍니다.
c++ 내장의 next_permutation을 사용하면 됐지만 직접 구현해보았습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <string>
using namespace std;
string str;
int N;
bool nextPermutation() {
int i = N - 1;
while (i > 0 && str[i - 1] >= str[i]) {
i--;
}
if (!i) return false;
int j = N - 1;
while (str[i - 1] >= str[j]) j--;
swap(str[i - 1], str[j]);
int k = N - 1;
while (i < k) swap(str[i++], str[k--]);
return true;
}
void func() {
nextPermutation();
cout << str << '\n';
}
void input() {
cin >> str;
N = str.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
}
return 0;
}
|
cs |
| boj 10453 문자열 변환 (0) | 2024.07.24 |
|---|---|
| boj 10096 세 친구 (0) | 2021.01.29 |
https://www.acmicpc.net/problem/23059
23059번: 리그 오브 레게노
첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구
www.acmicpc.net
간만에 위상정렬 문제입니다.
이 문제는 문자열을 인덱스로 변환해야 하지만 출력하는게 문자열이라 문자열 기준, 인덱스 기준의 맵을 따로 사용하였습니다.
intToString에는 인덱스 기준 문자열, stringToInt에는 문자열 기준 인덱스를 저장합니다.
이 부분이 해당 문자열에 대한 인덱스 값을 구해 맵에 넣는 과정입니다.
stringToInt와 intToString에 같이 넣어줍니다.
그 다음 위상정렬로 구매할 아이템의 순서를 정해주면 되는데
여기서 현재 같은 우선순위의 아이템은 사전 순으로 구매하기 때문에 우선순위를 인덱스로 둔 배열을 사용하였습니다.
우선순위가 낮은 (인덱스가 낮은) 배열부터 문자열들을 사전 순으로 정렬한 후에 출력합니다.
이 문제에서 N이 200000이라 MAX를 200000으로 잡았는데.. N이 문자열 갯수가 아닌 관계의 수였습니다..
이런 실수를 좀 줄여야겠습니다..
그리고 처음에는 map을 사용했었는데 시간 초과가 발생해서 unordered_map으로 바꾸니 AC를 받았습니다.
찾아보니 데이터가 많을 때 unordered_map의 성능이 훨씬 좋다고 하는 것을 보았습니다.
하지만 이 둘의 차이를 공부할 필요가 있어보입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#define MAX 400000
using namespace std;
typedef pair<int, int> pi;
unordered_map<int, string> intToString;
unordered_map<string, int> stringToInt;
vector<int> graph[MAX], ans[MAX];
int conn[MAX];
int N, idx;
bool cmp(int a, int b) {
return intToString[a] < intToString[b];
}
void print() {
for (int i = 0; ; i++) {
if (!ans[i].size()) return;
sort(ans[i].begin(), ans[i].end(), cmp);
for (int j = 0; j < ans[i].size(); j++) {
cout << intToString[ans[i][j]] << '\n';
}
}
}
void func() {
queue<pi> q;
for (int i = 0; i < idx; i++) {
if (!conn[i]) {
q.push({ i,0 });
ans[0].push_back(i);
}
}
for (int t = 0; t < idx; t++) {
if (q.empty()) {
cout << "-1\n";
return;
}
int x = q.front().first;
int cnt = q.front().second;
q.pop();
for (int i = 0; i < graph[x].size(); i++) {
int next = graph[x][i];
conn[next]--;
if (!conn[next]) {
q.push({ next, cnt + 1 });
ans[cnt + 1].push_back(next);
}
}
}
print();
}
void input() {
string str1, str2;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> str1 >> str2;
if (stringToInt.find(str1) == stringToInt.end()) {
stringToInt.insert({ str1, idx });
intToString.insert({ idx++, str1 });
}
if (stringToInt.find(str2) == stringToInt.end()) {
stringToInt.insert({ str2, idx });
intToString.insert({ idx++, str2 });
}
int a = stringToInt[str1];
int b = stringToInt[str2];
graph[a].push_back(b);
conn[b]++;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
| boj 2252 줄 세우기 (0) | 2021.02.07 |
|---|
이번주는 CS 스터디를 진행하였다.
1일 1알고리즘 실천
이번주는 자료구조를 마무리하였고, 다음 있을 알고리즘 관련 역할분배를 하였다.
이번주는 자소서 작성에 시간을 다 쓴것 같다.
막상 쓰고보니 미리좀 써놓을걸 하며 후회를 하기도 하지만 지금이라도 쓰고있는 것에 만족한다.
올해도 3주밖에 남지 않았는데 열심히 살아야겠다!
| SSAFY 5기 회고 (0) | 2021.12.25 |
|---|---|
| 12월 3주차 결산 (0) | 2021.12.19 |
| 12월 1주차 결산 (0) | 2021.12.05 |
| 11월 4주차 결산 (0) | 2021.11.28 |
| 11월 3주차 결산 (0) | 2021.11.21 |
이번주는 CS공부를 진행하였다.
1일 1알고리즘 실천
CS 스터디 첫주째다.
일단은 각자 맡은 파트를 공부해서 주 1회 모여서 설명하는 방식으로 진행하고 있다.
이번주는 자료구조를 진행하였고, 다음주에 마무리를 할 예정이다.
싸피 정규 교육과정이 끝나고, 취업 컨설팅 기간이다.
이때 부족했던 CS지식을 쌓기 위한 노력을 해야겠다는 생각을 했고,
이제는 진짜 취업에 올인을 하려고 한다.
저와 같은 취준생분들 모두 화이팅입니다!
| 12월 3주차 결산 (0) | 2021.12.19 |
|---|---|
| 12월 2주차 결산 (0) | 2021.12.12 |
| 11월 4주차 결산 (0) | 2021.11.28 |
| 11월 3주차 결산 (0) | 2021.11.21 |
| 11월 2주차 결산 (0) | 2021.11.14 |
이번주는 포트폴리오 작성을 했다.
1일 1알고리즘 실천
마침 포폴을 정리해야 하는데 싸피 교육과정에 포트폴리오 작성 기간이 있었다.
좋은 기회라고 생각해서 각잡고 써봤다.
지인들에게 피드백도 받으면서 작성했지만 아직 부족한 부분이 많아보인다.
[포트폴리오] 피드백은 언제나 환영입니다. ^^7
싸피 교육과정이 끝나면 부족한 CS공부를 1부터 다시 해야겠다고 생각했었다.
그리고 저번주에 프로젝트가 마무리되었고, 바로 대학 친구들과 스터디 팀을 꾸렸다.
각자 맡은 주제를 정하였고, 스터디가 시작되었다.
처음하는 CS 스터디인 만큼 열심히 해야겠다.
싸피 벌써 끝난거 맞아요..?
조금 전까지만 하더라도 2학기 시작해서 새로운 팀원들을 만났던것 같은데.. 벌써 마지막 프로젝트도 끝났다.
비록 본선에는 가지 못했지만 우리 팀원들 너무 잘해줘서 좋은 경험이었다!
요즘 취업 관련해서 여러 생각이 들긴 하지만 나만의 방향을 딱 정해서 진행해야겠다.
| 12월 2주차 결산 (0) | 2021.12.12 |
|---|---|
| 12월 1주차 결산 (0) | 2021.12.05 |
| 11월 3주차 결산 (0) | 2021.11.21 |
| 11월 2주차 결산 (0) | 2021.11.14 |
| 11월 1주차 결산 (0) | 2021.11.07 |
https://www.acmicpc.net/problem/17244
17244번: 아맞다우산
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출
www.acmicpc.net
챙겨야 하는 물건은 최대 5개이므로 bfs + 비트마스킹이 가능합니다.
visit[x][y][bit]: 좌표 (x, y)에 도착했을 때 찾은 물건의 비트가 bit인 경우의 방문 처리입니다.
비트를 어떻게 할지 고민하다가 chk배열을 사용하여 해당 좌표에 있는 물건의 비트를 정해주었습니다.
나가는 문에 도착했을 때 모든 물건을 찾았을 때만 t를 출력합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <iostream> #include <queue> #define MAX 50 using namespace std; typedef pair<pair<int, int>, int> pii; queue<pii> q; char list[MAX][MAX]; bool visit[MAX][MAX][1 << 5]; int chk[MAX][MAX]; int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }; int N, M, bit; void bfs() { for (int t = 1; !q.empty(); t++) { int qsize = q.size(); while (qsize--) { int x = q.front().first.first; int y = q.front().first.second; int cnt = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + direct[i][0]; int ny = y + direct[i][1]; int ncnt = cnt; if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; if (list[nx][ny] == 'X') { int b = chk[nx][ny]; ncnt |= b; } if (list[nx][ny] == '#' || visit[nx][ny][ncnt]) continue; if (list[nx][ny] == 'E' && ncnt == bit) { cout << t << '\n'; return; } q.push({ {nx,ny}, ncnt }); visit[nx][ny][ncnt] = true; } } } } void input() { int cnt = 0; cin >> M >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> list[i][j]; if (list[i][j] == 'S') { q.push({ {i,j},0 }); visit[i][j][0] = true; } else if (list[i][j] == 'X') { chk[i][j] = (1 << cnt); cnt++; } } } bit = (1 << cnt) - 1; } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); input(); bfs(); return 0; } | cs |
| boj 5547 일루미네이션 (0) | 2022.05.15 |
|---|---|
| boj 16932 모양 만들기 (0) | 2022.05.14 |
| boj 1194 달이 차오른다, 가자. (0) | 2021.04.21 |
| boj 17471 게리맨더링 (0) | 2021.04.16 |
| boj 2573 빙산 (0) | 2021.04.05 |
https://www.acmicpc.net/problem/13701
13701번: 중복 제거
문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1
www.acmicpc.net
이 문제는 메모리 제한이 8MB 이므로 2^25만큼의 배열을 사용하면 메모리 초과가 뜹니다.
따라서 이를 수를 구분할 수 있는 몫과 나머지를 이용한 비트마스킹을 이용합니다.
인덱스는 몫이 되겠으며, 비트로 사용할 값은 나머지입니다.
x라는 몫에 y라는 나머지가 있는지 비트 연산자로 확인합니다.
y라는 나머지가 있으면 출력, 없으면 return을 시키면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#define MAX 1 + (1 << 20)
using namespace std;
int list[MAX];
void func(int N) {
int x = N >> 5;
int y = N % 32;
int z = (1 << y);
if (list[x] & z) return;
list[x] |= z;
cout << N << ' ';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int N;
while (cin >> N) {
func(N);
}
return 0;
}
|
cs |
이번주는 면접과 자율 프로젝트 마무리를 하였다.
1일 1알고리즘 실천
각종 테스트 및 버그 수정을 진행하였다.
팀원 한명이 마지막에 취업으로 퇴소를 하였고, 3명으로 마무리했다.
그리고 최종 발표까지 마쳤다.
드디어 싸피에서 진행하는 모든 교육과정이 끝났다.
시간 진짜 너무 빠르다는 생각이 들고, 실감이 나지 않는다.
프로젝트를 진행하며 지쳤다는 핑계를 대며 주말에는 휴식을 취했지만
이게 마지막이라는 생각을 하고 앞으로는 취업 준비에 올인할 생각이다.
싸피 5기분들 다들 고생많으셨습니다!
| 12월 1주차 결산 (0) | 2021.12.05 |
|---|---|
| 11월 4주차 결산 (0) | 2021.11.28 |
| 11월 2주차 결산 (0) | 2021.11.14 |
| 11월 1주차 결산 (0) | 2021.11.07 |
| 10월 4주차 결산 (0) | 2021.10.31 |
https://www.acmicpc.net/problem/1135
1135번: 뉴스 전하기
민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다
www.acmicpc.net
TreeDP는 난이도도 생각보다 높고, 많이 못 풀어봤어서 그런지 어렵네요..
0번 직원부터 시작해서 모든 직원에게 뉴스를 전하는데 최소 시간을 구하는 문제입니다.
한 번에 한 명에게만 전파가 가능하므로 전파하는 시간이 가장 오래걸리는 직속 부하에게 먼저 전파를 해야합니다.
list라는 벡터에 자신의 직속 부하에게 전파하는 시간을 모두 저장한 후에 내림차순으로 정렬합니다.
먼저 전파하는 부하에게는 추가적인 시간이 필요하지 않으므로 +0,
두 번째 전파하는 부하에게는 추가적인 시간이 +1,
마지막에 전파하는 부하에게는 list.size() - 1 만큼 추가적인 시간이 추가됩니다.
이 경우들의 최댓값이 자신의 부하직원에게 소식을 전하는데 걸리는 최소 시간입니다.
24번째 줄 +1을 한 이유는 부하가 없는 직원에게서 오는 값은 0이기 때문에 1을 더한 것입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 50
using namespace std;
vector<int> graph[MAX];
int N;
int dfs(int v) {
vector<int> list;
int ret = 0;
for (int i = 0; i < graph[v].size(); i++) {
int next = graph[v][i];
list.push_back(dfs(next));
}
sort(list.begin(), list.end(), [](int a, int b) {
return a > b;
});
for (int i = 0; i < list.size(); i++) {
ret = max(ret, list[i] + i + 1);
}
return ret;
}
void func() {
cout << dfs(0) << '\n';
}
void input() {
int x;
cin >> N >> x;
for (int i = 1; i < N; i++) {
cin >> x;
graph[x].push_back(i);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
|---|---|
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |
| boj 1648 격자판 채우기 (0) | 2021.06.22 |
| boj 14700 넴모넴모 (Hard) (0) | 2021.06.22 |