월 33,000원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-B 탑다운 vs 바텀업 질문
코드 : http://boj.kr/febf6425d0184aeb834f64197f68727b 안녕하세요. 저는 이문제를 재귀dp로 풀었봤는데요,큰돌님은 이문제는 바텀업으로 푸셨고 자두나무같은경우에 탑다운으로 푸셨던데, 두 방법중에 어떤방법으로 풀어야겠다를 선택하시는 기준이 있는지요?저같은경우는 경우의수가 잘 나눠지면 재귀(탑다운)로 풀고아니면 해보면서 관찰이 필요한경우 for문(바텀업)으로 풀려고 생각을 정했는데 이게 맞을까요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-R 질문 있습니다
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.https://www.acmicpc.net/board/view/141897
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-A dp초기화값 관련 시간초과 질문
안녕하세요 큰돌님 강의 잘 듣고 있는 취준생입니다. 정답코드 : http://boj.kr/d2b2cb191a0c4451ba5269509674bfe5오답코드 : http://boj.kr/afbf220e88c64363b75a17bebd8affdc 정답코드는 큰돌님 코드 그대로인데요 dp를 -1로 초기화하고 -1이아니면 즉 계산된 값이 있으면 return dp 하고 탐색을 하기전에 dp를 987654321로 초기화하는 방식인데 저는 dp를 초기화할때 처음부터 fill로 987654321 로 초기화하면 if(dp != 987654321) return dp 하고 탐색하기전 dp=987654321 안해도 되지 않나? 이생각으로 코드를 바꿧는데 55%에서 시간초과가 뜨더라구요왜 그런지 설명 부탁드립니다 ㅜㅜ
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-m 3986 좋은단어 질문
http://boj.kr/b08f18a0dc7741f59a7216d6b9f8b52f선생님 제가 코드를 짜보았는데 선생님 코드와 크게 다를바가 없어보이는데 무엇이 문제인지 찾지를 못했습니다. 도와주시면 감사하겠습니다!
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1 - K 질문입니다!
http://boj.kr/01ee098d59044720ae701b1fee5685d6반례를 못찾겠습니다 선생님!! 도와주시면 감사하겠습니다! 링크를 잘못올려 수정했습니다!
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6-A 2792 보석 상자 런타임 에러 (DivisionByZero) 질문이 있습니다.
안녕하세요 선생님 !항상 좋은 강의 감사합니다. 이번 보석 상자 강의도 너무 잘 들었는데요, 처음에 혼자 생각해보다가 못 풀고 강의 보고 다시 정리해서 풀어봤습니다. 그런데 첫 제출에서 DivisionByZero 에러가 나서 99% 정도에서 틀렸다고 나오더라고요 탐색을 하는 부분에서 mid가 0일 때 return false를 줘서 두 번째 제출에 성공하긴 했는데, 첫 코드도 선생님 코드와 거의 비슷한 것으로 보여서요 어떤 부분이 잘못됐는지 궁금합니다 ! DivisionByZero 난 코드: https://www.acmicpc.net/source/77479342정답 코드: https://www.acmicpc.net/source/77479392 감사합니다 !!!!!!
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
Map에서 BFS탐색을 하는 경우에도 O(V+E) 시간복잡도인가요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요.2-A 2178번처럼 Map에서 BFS 탐색을 하는 경우에도 시간복잡도는 O(V+E)인가요?감사합니다.
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
문제풀이 질문 드립니다
처음 알고리즘을 공부하게 된 학생입니다.알고리즘 문제풀이를 시작할 때 어떤 방식으로 하면 될지 질문드립니다.우선 교안은 한번 다 익혔습니다. (중간 중간 생각나지 않는 부분도 있긴합니다.) 2309번 문제를 스스로 풀어본다.문제해설을 본다.문제해설을 다 이해하고 공부한 뒤 강의를 듣는다. 이러한 순서로 공부를 하는게 맞을까요? 그리고 문제가 풀리지 않을때는 고민해보다가 답지를 보는게 나을까요??
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-B 문제 메모리 초과 문의
안녕하세요 선생님,4-B 문제를 선생님 풀이를 보고 다시 풀어봤습니다.입력배열 A의 크기를 문제에서 주어진 최댓값인 20으로 설정할 때는 메모리초과로 오류가 나는 데, 혹시나 해서 21로 늘려보니 통과했습니다. http://boj.kr/985212f27de447b19f0c9794794c53e6http://boj.kr/915ba15212a94c9782d0a40dc8e1ce0c 어디서 문제가 생기는 지 알 수 있을까요?강의 항상 잘 보고 있습니다. 감사합니다.
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-M 시간초과 질문있습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/ef8ad015457e4bbba05ac351eb5ae0d8안녕하세요 강사님 7-M 문제에서 살아있는 나무는 정렬을 위해 deque를 사용했고죽은 나무는 queue를 사용해서 양분으로 바꿔줬는데 계속 시간초과에서 막혀 질문글 남깁니다...이 문제는 deque로 풀면 안되는 문제일까요? 아니면 제 코드에서 시간을 단축 시킬만한 곳이 있을까요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-C 입력 질문 있습니다.
for(int i = 1; i <= n; i++){ cin >> m; for(int j = 0; j < m; j++){ cin >> temp; adj[i].push_back(temp); adj[temp].push_back(i); } }입력을 받아서 인접 노드들을 벡터에 삽입해주셨는데, adj[temp].push_back(i); 이 부분이 들어가게 되면 같은 노드가 2번씩 벡터에 삽입되지 않나요? 예를 들어, 예제 입력 1에서 보면 1~6번 구역마다 인접 구역을 입력으로 받으니까 adj[i].push_back(temp); 이코드만 있어도 양방향 간선이 표시된다고 생각합니다. a[1] => {2, 4}a[2] => {1,3,6,5}a[3] => {4, 2}a[4] => {1, 3}a[5] => {2}a[6] => {2}이렇게요
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
어떤 부분이 문제일까요?
http://boj.kr/f9e04dedecf9402eb6e1bcb1042dcfa6선생님 안녕하세요.선생님이 작성해주신 답이랑 비교해봤을 때, 차이가 나는 부분은 if문을 통해 idx가 a[i].first보다 큰지 작은지를 가른뒤, 계산해주는 부분밖에 없는 것 같습니다. 선생님께서는 a[i].second - a[i].first 또는 idx 이런식으로 직접 해주셨고, 저는 s라는 변수에 a[i].first 또는 idx 를 담아줘서 계산해준 것 밖에 차이가 없다고 생각하는데요.어떤부분이 달라서 정답이 아니라고 나오는 걸까요?? (if(a[i].second <= idx) continue; 이부분은 문제에 웅덩이는 겹치지 않는다는 조건이 있어서 넣지않았습니다.)
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2776 암기왕 문제 시간복잡도에 관해 질문이 있습니다
안녕하세요 큰돌님암기왕 문제를 map을 사용한 경우 탐색에 log(n)의 시간복잡도를 갖는데, 이분탐색을 사용한 방법과 시간차이가 커서 질문드립니다. sort를 사용하는 경우에 정렬에 nlog(n), 값을 찾는데 log(n)이 걸리며,map을 사용하면 삽입에 n * log(n), 값을 찾는데 log(n)이 걸리니 결국 비슷할거라 생각했는데 시간차이가 2배나 나는 이유를 모르겠습니다 ㅜ#include<bits/stdc++.h> using namespace std; int t, n, m, temp; int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> t; for(int i = 0; i < t; i++){ map<int, int> mp; cin >> n; for(int j = 0; j < n; j++){ cin >> temp; mp.insert({temp, 0}); } cin >> m; for(int j = 0; j < m; j++){ cin >> temp; if(mp.find(temp) == mp.end()) cout << 0 << '\n'; else cout << 1 << '\n'; } } return 0; }
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6-J 풀이가 가지 않아서 질문드립니다
안녕하세요 큰돌님.풀이를 몇번을 봤는데도 이해가 가지 않아서 질문드립니다. 이분탐색으로 찾으려는 것- 실제 필요한 시간보다 조금 더 큰 시간- 즉, ret이 놀이기구를 타는데 걸린 총 시간이 됨ret - 1 / a[i] - ex) 문제 예시 들어주신 것처럼 4분이 딱 되었을 때 새롭게 타는 사람 수를 빼주기 위해 하는 로직전체 묶음을 다 처리하고 놀이기구에 아무도 안 탄 상태로 가정하고 그 부분부터 한명씩 태우는 로직 이렇게 파악하긴 했는데, 아무리 봐도 2번, 3번이 전혀 이해가 가지 않습니다... 놀이기구 수만큼을 바로 태울 필요가 있나요? 처음 시작을 temp = m으로 시작하지 않고 temp = 0을로 시작하면 4분일 때 딱 7명 태운걸로 나와서 ret - 1 / a[i] 로직을 안해도 되지 않나요? 그리고 마지막에 총 걸린시간(ret) % a[i] 로직이 어떤 의미인건지 이해가 안 됩니다 ㅠㅠ 아래는 제가 선생님 코드를 이해하려고 주석을 달아본 코드입니다.#include<bits/stdc++.h> using namespace std; #define max_n 60000000004 #define MAX_M 10004 typedef long long ll; // ret : 총시간, temp가 m : 여기서 부터 시작 ll n, m, a[MAX_M], lo, hi = max_n, ret, mid, temp; bool check(ll mid) { temp = m; // 놀이기구 수만큼은 바로 태울 수 있으므로 m명은 태우고 시작 for (int i = 0; i < m; i++) temp += mid / a[i]; return temp >= n; // 총 걸리는 시간이 mid일 때 n명이상 태울 수 있는지 } int main() { cin >> n >> m; for (int i = 0; i < m; i++) cin >> a[i]; if (n <= m) { cout << n; return 0; } while (lo <= hi) { mid = (lo + hi) / 2; if (check(mid)) { ret = mid; // 총 걸린 시간 hi = mid - 1; } else lo = mid + 1; } // temp : 4분까지 태운 학생 수 -> 4분이 딱 됐을 때 바로 추가로 태울 수 있는데 그걸 뺀 순수하게 4분까지 태운 학생 수 temp = m; for (int i = 0; i < m; i++) temp += ((ret - 1) / a[i]); // 4분부터 시작해서 다시 순차적으로 놀이기구 태움 -> 즉, 여기서는 놀이기구에 아무도 타있지 않은 초기 상태임 for (int i = 0; i < m; i++) { if (ret % a[i] == 0) temp++; // % 연산의 결과가 0이 아날 경우 == 놀이기구에 이미 학생이 탑승되어 있음 if (temp == n) { cout << i + 1 << "\n"; return 0; } } return 0; }
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
DP 풀이방법에 있어 탑바텀, 바텀업 풀이 방식의 선택 방식
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 ^^강의 너무 잘 듣고 있습니다. DP 문제를 풀다보면.., 시작하기 전에 해당 문제를 바텀업으로 풀어야할지, 탑바텀으로 풀어야할지 어떻게 결정할 수 있을까요?제 느낌은 바텀업풀이가 점화식을 유도할 수 있다면 코드 자체가 간단하여(재귀호출x) 구현 난이도가 쉬운데, 점화식을 생각하는 과정이 경우에 따라 매우 어려운것 같습니다. 탑바텀 풀이는 완전탐색과 동일한 상태에서 메모이제이션 을 잘 정의함으로써 문제를 풀 수 있는데, DP배열의 상태정의를 어떻게 하느냐에 따라, 테스트케이스는 맞지만 제출시 틀리는 결과가 나오는 경우가 종종있습니다 (구현에서 실수 잦음) 어떤 식으로 DP의 풀이를 결정하고 문제를 들어가는지 질문드려요. 감사합니다.!!
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1 - G 질문입니다!
#include <bits/stdc++.h> using namespace std; int cnt; string pattern, input; vector<string> split(string s, string d) { long long pos; vector<string> ret; string token; while ((pos = s.find(d)) != string::npos) { token = s.substr(0, pos); ret.push_back(token); s.erase(0, pos + d.length()); } ret.push_back(s); return ret; } int main() { cin >> cnt; cin >> pattern; vector<string> p = split(pattern, "*"); string str; string front_str, end_str; for (int i = 0; i < cnt; i++) { cin >> str; front_str = str.substr(0, p[0].length()); cout << str.length() << " " << p[1].length() << '\n'; cout << str.length() - p[1].length() << '\n'; if (str.length() - p[1].length()) { // str.length() - p[1].length() 부분이 이상한 양수값을 반환하여 // if값으로 걸러져야할 상황에도 if문 안으로 들어오고 있습니다ㅜㅜ // end_str = str.substr(str.length() - p[1].length(), str.length()); } // cout << front_str << " " << end_str << '\n'; } return 0; }//input값입니다! 1 a*dddddd abcd 선생님 제가 반정도 짠 코드인데 주석에서도 언급하듯이 str.length() - p[1].length()부분이 p[1].length()가 더 큰경우 이상한 값을 반환합니다! 이럴때 어떻게 해야하나요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
구현 알고리즘이 부족한데 계속 진도를 빼도 괜찮을까요?
안녕하세요 선생님.구현 알고리즘에 대해 취약한 것 같아 질문 드립니다.현재 1-O까지 풀면서 답안을 안 보고 푼건은 2번 정도인 것 같습니다. 구현 유형의 알고리즘이 약하다고 생각됩니다. 이런 와중에 2주차 그래프이론을 바로 학습하는게 맞을지, 아니면 구현 관련 알고리즘을 좀 더 찾아서 풀어보는게 맞을지 잘 모르겠습니다.
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-D 문제 질문있습니다
안녕하세요 선생님,올려주신 강의 잘 듣고 있습니다.BFS를 이용하여 3-D 문제를 풀고 있습니다. http://boj.kr/c6c17d2eb9a749febe75792df0897cafTree 깊이가 변할 때마다 fire() 라는 함수를 사용하여 불의 위치를 업데이트하는 방법으로 구현했습니다.예제는 잘 통과하는데, 성공하지 못했습니다. 혹시 반례를 알 수 있을까요?감사합니다.
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-x_1480 질문 있습니다
재귀를 이용해서 dp를 하는 방식이 아닌 선생님께서 배낭채우기 할 때 처럼 표를 완성하여 dp를 했는데 무엇이 문제 인지 잘 모르겠습니다. 이 문제에서는 표에 넣을 수 있는 보석의 인덱스를 저장을 했고표가 완성되면 넣어준 보석을 보석목록에서 제거하고 다음 가방을 완성하는 방식으로 코드를 작성했는데 무엇이 문제인지 잘 모르겠습니다.http://boj.kr/2b01ce15326a43c9ad3c8f340157eab3
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-E 질문 있습니다.
현재 큰돌 강사님이 풀어주신 문제 해설은 이해 됐습니다. 그런데 scv갯수가 주어지고 한 개체를 한번에 여러번 공격을 못하기에 (모든 scv의 총 체력/한번에 줄 수 있는 데미지)이렇게 해서 구할 수도 있지 않을까 했습니다. 이를 바탕으로 코드를 썻으나 틀렸다고 나오는데 이게 왜 되지 않는지 몰라서 질문드립니다. 다음은 해당 코드입니다. http://boj.kr/dab5e07b909146eba418c449e7c219f9