일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 브루트포스
- cs
- 스택
- OS
- 정석학술정보관
- Computer science
- 개발
- 백준
- c++
- 자료구조
- 알고리즘
- 컴퓨터공학과
- 너비우선탐색
- 오퍼레이팅시스템
- coding
- Stack
- 코딩
- 문제풀이
- Operating System
- 그래프
- 북리뷰
- 코테
- 오에스
- 컴공과
- vector
- 컴공
- bfs
- 정석
- 구현
- DP
- Today
- Total
목록전체 글 (304)
Little Jay
중등교육에서 배운 nCm을 출력하는 문제이다. 하지만 여기서 n이 매우 크다면 그 수는 주체할 수 없을 만큼 커질 것이다. 문제의 예시에서의 100C6만 하더라도 1192052400이 출력된다. 따라서 이를 long long 형태가 아닌 string으로 문제를 해결해야 한다. 그리고 떠오를 수 있는 것은 Paskal의 삼각형이다. Paskal의 삼각형의 점화식은 nCm = n-1Cm-1 + n-1Cm 이다. 따라서 이를 재귀적으로 구해준다면 문제를 해결할 수 있다. #include #define endl '\n' #define ll long long using namespace std; string arr[101][101]; int n, m; string longadd(string a, string b)..
전형적인 DFS문제이다. 그런데 이제 Sorting을 곁들인..... 순서대로 DFS를 수행해주면 되지만 인접리스트로 구현한 그래프를 정렬을 하고 DFS를 수행해줘야 한다. 문제해결기법 13주차 A번 문제와 매우 유사한 문제였던 것 같다. #include #define endl '\n' #define pii pair using namespace std; int t; vector v[100001]; bool visited[100001]; int order[100001]; vector dfs_order; bool cmp(int& a, int& b) { return order[a] < order[b]; } void dfs(int start) { if (visited[start]) return; visited[..
Prefix Sum문제. 문제에서 정확히 뭘 출력하라고 하는지만 파악하면 쉽게 풀 수 있다. #include #define endl '\n' using namespace std; int dp[1025][1025]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; int x1, y1, x2, y2; cin >> n >> m; for (int i = 1; i dp[i][j]; for (int i = 1; i y1 >> x2 >> y2; cout
DP가 하도 어려워서 요새 DP를 집중적으로 공부하고 있다. 그 와중에 조금 어이없는(?) 문제를 발견해서 풀이를 올리고자 한다. 위 문제는 어떤 실수 형태의 배열에서 연속되는 구간의 곱의 최대값을 출력하는 문제이다. 이를 간단하게 구성을 construct해보면 어떤 배열이 자기 자신으로 초기화 된 후에, 그 0번 인덱스의 것을 제외하고 1번 인덱스부터 자기 자신과 그 전에 있는 것의 곱의 대소 비교를 통해서 누적곱을 구할 수 있다. 이렇게 업데이트 시켜 주면서 최대값을 찾아주면 정답인데, C++를 하는 사람들은 당연히 setprecision 메서드를 사용했을 것이다. 문제는 이렇게 하면 정답이 아니다. 문제에서 요구한 것은 어떤 값들이 들어와도 소수 3번째 자리수까지 출력하는 것이다. 정수값을 setp..
고등학생 때부터 예민해지기 시작하면 항상 화가 자주 났다. 그 화는 스스로에게 나는 화일수도 있고, 타인에게 나는 화일수 도 있으며, 아무런 대상이 없이 화가 날 때가 많았다. 그러나 이렇게 불쑥불쑥 생겨나는 화를 밖으로 드러낼 수도 없었다. 따라서 참다보니 마음의 병이 생기기 시작했고 나아가 내 몸을 힘들게 하였다. 대학교에 와서도 달라지는 것은 없었다. 똑같이 예민한 상황이 되면 화가 나고 나는 그것을 점점 통제하기가 힘들었다. 따라서 나는 이 책을 읽게 되었다. 인간에게 감정이란 무엇이고 이것은 어떻게 생겨나는지 근본적으로 알고 싶었기 때문이다. 결론적으로 이 책을 이렇게 말했다. 원시 시대부터 지금까지 인간은 진화를 해왔고 인간에게 필요하고 도움이 되는 것들만 남겨져 왔기 때문에 화나는 감정을 포..
‘난장이가 쏘아올린 작은 공’은 도시 빈민인 난장이 가족을 통해 1970년대 급속히 진행되는 산업화 사회에서 비롯된 소외계층의 아픔과 도시 재개발 사업의 실상과 허위성, 국가의 횡포 등을 드러내며 도시 빈민의 현실적인 상황을 폭로한다. 난장이 가족은 열심히 노력하지만 빈곤을 떨쳐내기 어려웠으며 이들의 빈곤은 대대로 내려져 온 것으로 이는 빈곤이 개인이 아닌 사회 구조적 문제라는 것을 보여준다. ‘난장이가 쏘아올린 작은 공’이라는 제목에서 ‘작은 공’은 경제적 소외계층이 바라는 행복하고 평등한 삶을 살고자 하는 희망을 뜻한다. 하지만 바라는 세상이 오는 것은 쉽지 않았고 난장이는 끝내 자살하고 만다. 이때 난장이는 굴뚝 안으로 떨어져 죽었는데 이 장면을 보고 모든 고통과 아픔을 혼자 지고 자살하는 느낌이 ..
substring과 map을 활용한 문제 map은 자료를 저장할때 red-black tree 구조로 구현이 되어있기 때문에 자동 정렬이 된다. 이는 int형 뿐만 아니라 string 형태에서도 char에 따라서 정렬을 한다. 'ab' > n; v..
플로이드-와샬 알고리즘으로도 풀 수 있는 문제이지만, 다익스트라가 문제를 보고 떠올랐기에 다익스트라로 풀었다 각 vertex에 대해서 다익스트라를 수행해주고, 수행 후의 distance와 m을 비교해 ans의 max값을 찾아내면 된다. #include #define endl '\n' #define pii pair #define MAX 987654321 using namespace std; int n, m, r; int a, b, l; int items[101]; vector v[101]; int dist[101]; void init() { for (int i = 0; i > n >> m >> r; for (int i = 1; i > items[i]; } for (int i = 0; i < r; i++) ..
트리를 활용한 문제이다. 사실 트리 문제가 나오면 DFS를 활용하는 것이 정배라고는 하지만 이 문제는 단순히 BFS를 통해서 문제를 풀 수 있었다. 1번 Node는 고려하지 않으므로, 1번 Node에서 출반하여 BFS 탐색을 수행하면 문제가 풀린다. 문제는 항상 root node가 1이 아니기 때문에 입력에서 양방향 인접리스트로 받았는데, 이제 visited한 것을 잘 처리해주면 된다. #include #define endl '\n' #define pii pair using namespace std; int n; vector tree[100001]; bool visited[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)..
골드문제라 겁먹었지만 Tree개념을 제대로만 알고 있다면 어려운 문제는 아니었다. 먼저 단절점에 대해서 생각을 해보자. 단절점에서 해당 vertex가 삭제가 되었는데, child가 없다면 해당 vertex는 단절점이 아니고, 그래프로 하나로 유지될 것이다. 따라서 해당 vertex의 size가 1 초과라면 당연히 해당 정점은 단절점이 된다. 반면 단절선은 무의미하다. 편향 tree라고 하더라도 간선을 하나 자르면 무조건 그래프는 2개 이상으로 쪼개진다. 이 점을 고려하여 잘 그림만 그려도 쉽게 풀 수 있다. #include #define endl '\n' using namespace std; int n, q, t, k; vector tree[100001]; int main() { ios::sync_wit..