안녕하세요 큰돌님! 이번에 취준을 처음 시작하면서 코딩테스트를 막 준비하는 컴공과 4학년 학생입니다!! 평소 지하철에서 큰돌님 유튜브 영상 많이 봐왔어서 바로 코테 준비도 함께 하려고 합니다! 뭔가 큰돌님 강의 듣기 전에 제 나름대로 문제 유형을 정리해봤는데요, 일단 되게 많은 유형을 준비해야 하는 것 같아 막연합니다.. 😅 학부 수업을 통해 C++ 문법 및 STL 컨테이너, 벡터의 기본적인 사용까지 익숙한 상태인데요. 혹시 정리한 유형이 조금 많지만, 큰돌님께서 학습 우선순위를 개괄적으로 알려주시면 감사하겠습니다! 큰돌님의 본 코테대비 10주 강좌 커리큘럼 외에 따로 준비해야할 유형이 있는지 궁금합니다! [유형 정리] 1. 기초 자료구조 배열, 동적배열, 링크드리스트, 스택, 큐, 덱, 맵, 셋(set), 해시테이블 2. 기본 알고리즘 사고 재귀, 정렬 3. 탐색 / 완전탐색 완전탐색(브루트포스), 이진탐색, BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 4. 조합론 / 백트래킹 순열, 조합, 부분집합, two sum, 백트래킹, 비트마스킹 5. 투포인터 / 스위핑 / 윈도우 투포인터, 슬라이딩 윈도우, 라인스위핑 6. 분할 정복 / 고급 정렬 기법 분할 정복(Divide and Conquer), 병합정렬, 퀵정렬 7. 동적 계획법(DP) DP, LIS(Longest Increasing Subsequence), LCS(Longest Common Subsequence) 8. 기본 그래프 알고리즘 트리, 그래프, 유니온파인드, 힙(우선순위 큐) 9. 그래프 최단 경로 알고리즘 다익스트라, 플로이드-워셜, 벨만-포드 10. 그래프 확장 알고리즘 위상 정렬(Topological Sort), 최소 신장 트리(MST, 크루스칼, 프림), 네트워크 플로우(최대 유량) 11. 기타 알고리즘 패러다임 그리디 12. 수학 / 정수론 소수 판별, 에라토스테네스의 체, 최대공약수(GCD), 최소공배수(LCM), 유클리드 호제법, 모듈러 연산, 페르마 소정리
안녕하세요 큰돌님. 이런 질문 드려 죄송하지만 학습방법에 문의가 있어 질문드립니다. 제 상황에 대해 먼저 설명드리자면 저는 컴퓨터공학 석사과정 학생이고, 이번이 마지막 학기입니다. 즉 졸업논문 준비와 취준을 병행하고 있는 상황입니다. 그래서 평일에 5시간정도, 주말은 모두 코딩테스트 준비에 할애할 수 있습니다. 저의 목표는 삼성전자와 SK하이닉스의 코딩테스트입니다. 제가 이 질문을 드리는 이유는 삼성전자 채용이 작년보다 2주 빨리 나오는 바람에 시간이 촉박해졌습니다 ㅠㅠ 현재 2주정도의 시간이 남은 것 같습니다. 제조업이다보니 네카라쿠배당토와 같은 IT기업보다는 난이도가 쉬운 것으로 알고 있는데요. 삼성전자는 두문제가 출시되고 구현 자체에 대한 문제가 1번으로 나오고 2번 문제는 알고리즘 문제가 나온다고 합니다. 하지만 저의 진도는 이제 비트마스킹을 시작한 상황입니다.... 큰돌님이 중요한 유형만 모아서 만드신 강의라는 것을 잘 알고 있지만 시간이 촉박하다보니 질문드립니다. 비트마스킹 강의를 듣다보니 이 유형이 필수인가? 아니면 알고 있으면 더 좋은 것인가? 라는 생각이 듭니다. 남은 기간동안 이 주차 강의는 꼭 들어야한다! 이렇게 추천해주실수 있으실까요?
강사님이 타이핑해주신 SetArmour함수에 궁금한 부분이 있어 질문합니다. PickupItem destory로 처리한 후 ArmourMap[ArmourType] = NewArmour;로 처리해주셨는데. 따로 Remove를 추가 안 하신 이유가 궁금합니다. 만약 이 흐름으로 진행된다면 59번 줄에서 false처리로 되어 큰 영향은 없어 보이지만 조금 의문이 들어 문의 남깁니다.
안녕하세요 큰돌님 go함수의 이중for문에서 의문이 있어 질문드립니다. int i=here로 세로축(가로선범위)에는 제약을 걸었고, main함수에서 go(1, 0)으로 함수를 시작하는 것을 확인했습니다. 하지만 가로축(세로선범위)는 int j=1로 시작합니다. 그리고 visited는 오직 가로선을 놓을 수 있는지 없는지만 판단하죠. visited[i][j] = 1; go(i, cnt + 1); visited[i][j] = 0; 이 line에 의해서 j=1 상황은 빠져나온 후 (here, j=1) 일때를 지나서 (here, j=2)일때 go함수가 실행된다면 다시 이중for문으로 들어와 j=1일때 go를 실행할 것입니다. 그렇다면 j에 의해서는 조합의 경우의 수가 아니라 순열의 경우의 수만큼 go함수 호출이 발생할 것입니다. 그래서 j에도 1부터 탐색하는게 아니라 현재위치부터 탐색하도록 만들어야하는 것이 아닐까요?? 논리적으로 정답은 똑같아서 정답처리 되었지만 시간 상 더 오래걸릴 수 있지않을까 라는 생각이 들었습니다. 제가 잘못생각하고 있는것인지 궁금하여 질문드립니다.
안녕하세요 선생님! ㅎㅎ 저는 고의로, 시간 초과가 나는 코드를 아래와 같이 작성해보았습니다. (주석은 테스트했던 흔적) http://boj.kr/c3476a1df6d647de81b2d85f187f35e0 그러나 제 기대와는 달리, 시간 초과가 나지 않고 1%에서 바로 '틀렸습니다' 가 뜨더라고요. 이 말은 즉 코드 자체의 로직이 잘못되어 테스트케이스를 통과하지 못하는건데 그 이유가 뭔지 잘 안 찾아져서 여쭤보러 왔어요. (count세는 함수, arr의 뒤집기 등이 잘 안 동작하는지 확인해봤는데 다 잘 동작하는 것 같아서 더 의문이에요) 어떤 부분이 잘못되었길래, 아예 테스트케이스를 통과하지 못하는 것일까요..?
안녕하세요 큰돌님 BFS강의 누구보다 쉽게 알려주셔서 감사합니다. 강의를 듣던 중 질문이 생겼는데요. 개념 및 교안에서 최적의 거리는 visited[목적지] -1 을 하셨는데, 당근마켓 문제에서는 visited[목적지y][목적지x] -1을 하지 않으신 이유가 궁금합니다.
안녕하세요. 저도 객체 잘림에 대한 의문이 들어 durams 님의 질문을 보고 나서 나름대로 정리를 해보고 있는데 (durams 님이 질문에 작성하는 코드) class MyArray { private: int m_data[5]; public: int& operator [](const int& index) { if (index < 0 || 5 <= index) { ArrayException e; cout << &e << endl; throw e; } return m_data[index]; } }; void doSomething() { MyArray my_array; try { my_array[100]; } catch (Exception& e) { cout << "doSomething()" << endl; cout << &e << endl; e.report(); throw e; } } int main() { try { doSomething(); } catch (Exception& e) { cout << "main()" << endl; cout << &e << endl; e.report(); } return 0; } catch (Exception& e) { cout << "doSomething()" << endl; cout <<"catch 참조 변수 주소: " << &e << endl; e.report(); throw e; } 위의 코드를 설명해보면, (Exception& e)는 throw된 객체의 참조이고 위의 throw e;의 e는 throw 될 때 e가 참조하고 있는 변수를 '복사 생성'한 독립적인 객체다 또한 'throw;될 경우 복사 생성하지 않고, catch에서 잡은 예외 객체를 그대로 다시 던지는 것'이다 즉, catch의 &는 부모 type의 매개 변수를 참조 없이 선언하여 객체 잘림이 될 경우를 예방하는 것이다. 위의 설명들이 맞을까요? 그렇다면 5 분 17초에서 임시 객체를 throw하고 있고 매개 변수는 참조의 형태를 가지고 있기 때문에 객체 잘림이라는 설명은 맞지 않고 다형성의 자식의 객체를 부모의 참조로 조작하는 경우인 것 아닌가요?
문제는 해결했지만, 강의에 큰 오류가 있는 것 같아, 강의를 듣는 분들에게 공유하는 것이 좋다 생각돼서 글을 작성했습니다. 강의의 Transform 코드가 미흡하다 생각해서, [LH, row_major, 요우->피치->롤] 을 전제로 하는 Transform ( Vec3, Vec4, Matrix3x3, Matrix4x4, Quaternion ) 을 다른 교재(이득우저 게임수학) 를 참조하여, 강의 코드에 적용해서 공부하고 있었습니다. 문제없이 잘 진행되다, 65.애니매이션 #2 에서 AssimpTool 로 FBX를 변환한 데이터를 애니매이션 진행할시, 로테이션이 반대로 되는 문제가 있었습니다. 이틀에 걸려 문제 원인을 찾았는데, 원인 코드는 아래와 같습니다 (강의 코드의 AssimpTool 프로젝트의 Utils 파일의 Converter.cpp 의 내용) /* std::shared_ptr<asAnimationNode> Converter::ParseAnimationNode(shared_ptr<asAnimation> animation, aiNodeAnim* srcNode) { std::shared_ptr<asAnimationNode> node = make_shared<asAnimationNode>(); node->name = srcNode->mNodeName; uint32 keyCount = max(max(srcNode->mNumPositionKeys, srcNode->mNumScalingKeys), srcNode->mNumRotationKeys); for (uint32 k = 0; k < keyCount; k++) { asKeyframeData frameData; bool found = false; uint32 t = node->keyframe.size(); // Position if (::fabsf((float)srcNode->mPositionKeys[k].mTime - (float)t) <= 0.0001f) { aiVectorKey key = srcNode->mPositionKeys[k]; frameData.time = (float)key.mTime; ::memcpy_s(&frameData.translation, sizeof(Vec3), &key.mValue, sizeof(aiVector3D)); found = true; } // Rotation if (::fabsf((float)srcNode->mRotationKeys[k].mTime - (float)t) <= 0.0001f) { aiQuatKey key = srcNode->mRotationKeys[k]; frameData.time = (float)key.mTime; frameData.rotation.x = key.mValue.x; frameData.rotation.y = key.mValue.y; frameData.rotation.z = key.mValue.z; frameData.rotation.w = key.mValue.w; found = true; } */ ==>> 위 코드에서, Quaternion 로테이션을 전치하기 위해, x, y, z 의 부호를 거꾸로 하는 코드가 필요합니다. 수정한 제 코드에는 아래와 같습니다 frameData.rotation.X = -key.mValue.x; frameData.rotation.Y = -key.mValue.y; frameData.rotation.Z = -key.mValue.z; frameData.rotation.W = key.mValue.w; 저렇게 코드를 수정하니, (LH, row_major) 를 전제로 하는 Transform 코드에서 잘 작동하더군요. 물론 강의의 DirectX::SimpleMath 를 바탕으로 만들어진 Transform 을 사용하면 아무 문제 없습니다. 제가 SimpleMath를 제대로 이해하지 못해서, 어떻게 강의 코드가 잘 작동하는지를 이해하지는 못했고, 여전히 의문이 남습니다. 강의에서도 FBX 데이터는 RH 를 전제로 만들어졌고, 강의는 LH 를 전제로 하기에, AssimpTool 에서 본 트랜스폼 데이터를 변환할 때에, 아래 강의 코드인 Converter::ReadModelData 에서, bone->transform = transform.Transpose(); 트랜스폼을 전치합니다. Converter::ReadKeyframeData 에서도, if (findNode == nullptr) 에서도 transform = transform.Transpose(); 로 전치를 하는데, 앞서 제가 수정했던 else (애니매이션 데이터가 있는 부분) 에서는 전치 (rotation을 거꾸로 전환하는 코드) 가 누락됐습니다. 정리하면, 강의의 일부 코드에서는, RH -> LH 를 위한 전치(로테이션 거꾸로) 코드가 있는데, 일부 코드에서는 전치 코드가 없는데도, 강의 코드는 잘 작동한다는 겁니다. 아무튼 제 문제는 해결됐습니다. 강의를 보다 혼동하실 분들이 제 글을 참고했으면 좋겠네요. 제 코드를 담은 깃허브 링크도 공유합니다 https://github.com/HeeTaeKim996/Learning_DirectX11_3D
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 선생님 ! 조합을 직접 그려보라고 하셔서, 직접 그림으로 표현해보다 궁금한게 생겨 질문드립니다. 타고 내려가다가 c(2, [0,1,2]) 해당 부분에서 , start = 1 i=2 인 상태에서 b.pop_back()을 진행하면, 백터 b에만 영향을 미치는거 아닌가요? 왜 i--를 해주지 않아서 i =2로 그대로 남아 있는데, C(3, [0,1,3])이 될 수 있는지 궁금합니다 .ㅠㅠ
안녕하세요 선생님, 저는 제목과 같이 1순위 희망 기업은 삼성전자이고 이후에도 제조업 기반의 회사 코딩테스트를 보게 될 거 같은데, 현재 학습하고 있는 4주차 비트마스킹을 우선적으로 학습하는 게 좋을지 아니면 그 뒤에 이분탐색이나 DP같은 문제를 먼저 학습하는 게 좋을지 여쭤보고 싶습니다. 감사합니다.
먼저 좋은 강의 해주셔서 감사의 말씀 올립니다!! 제가 첫 시도때 못 풀고 선생님 강의를 보고 그 다음날 다시 복습하는 과정에서 제 나름대로 로직을 찾아보고 테스트 케이스를 다 푼 코드를 만들었는데, 결과적으로 시간초과가 떴습니다. 그래서 선생님 코드랑 비교해봤는데, 제가 생각했을 때 어디서 차이가 나는지 모르겠어서 이렇게 질문남깁니다. 읽어주셔서 감사합니다!! http://boj.kr/c8fc36cc6e9844a88c4495c0a7e8f3a4
안녕하세요 선생님, 17071 문제를 푸는데 도저히 시간 초과가 해결이 되지 않아 질문드립니다. http://boj.kr/205232630d404eddbd6e2f0eeb5e5627 맨 처음에 주석에 달린 조건문이 없을 때는 메모리 초과가 났었고, 이를 해결하기 위해 조건문을 추가했어요. 다만 해당 방법으로 구현하니 시간 초과 문제가 나더라고요. 더더욱 최적화를 해야할 것 같은데, 현재 제 코드에서 더 최적화할 수 있는 방법이 뭔지 궁금합니다. 그리고 이 문제만 6시간 이상 붙잡고 있는데, 이게 맞는건지 잘 모르겠어요. 아예 아이디어가 생각이 안나면 이렇게까지 시간을 붙잡고 있지는 않고, 바로 아이디어 힌트를 얻으려고 할텐데 어느정도 될 것 같은 아이디어(==전체적인 설계나 시간 복잡도, 공간복잡도를 고려했을 때)로 구현했을 때 예상치 못한 동작을 한다던가, 메모리 초과나 시간 초과를 겪으면 제 방법에서 보완하기 위해 고민하다보면 시간이 너무 많이 지나있더라고요. 물론 선생님의 해설은 훌륭해서 잘 이해가고, 해당 방법으로 풀면 풀린다는 것도 잘 알아요. 하지만 그건 제가 푼 게 아니라 선생님이 푼건데, 그저 이해하고 따라하기만 하면 낯선 아이디어를 떠올려야할 때 스스로 생각하는 힘이 부족한 느낌이 들더라고요. 그래서 계속 어떻게든 제 방법의 문제점을 찾아내고 해결하려고 붙잡게 되네요. 방법의 시작 자체가 잘못된 걸수도 있는데, 그렇다면 무엇이 잘못되었는지 파악하려고 하고요. (물론 잘 안돼요. 시간만 버리는 것 같습니다.) 실력도 별로 느는 것 같지 않아요. 연습 시간은 너무 많이 걸리고요. 코드도 너무 못 짜는 것 같아요. 제 방식이나 생각이 잘못된건가요?
안녕하세요 선생님! 수업 듣는 도중 이해가 가지 않는 부분이 있어 질문드리게 되었어요. "8:19~ 이후" 부터 범위가 50만이기 때문에 50만 * 50만의 2차원 배열을 만들 수 없다고 설명해주셨어요. 하지만 만약 범위가 500 정도라면 2차원 배열을 만들어서 활용했을 것이다 라고 말씀해주셨고요. 저는 범위가 500일 때, 2차원 배열을 어떤 식으로 만들어서 활용하신다는건지 잘 이해하지 못했어요. arr[수빈이의 상태][동생의 상태] 로 만들어서 활용한다는 의미인 것으로 이해했고, 이 "상태" 라는 것은 이 문제의 경우 "위치, 즉 x값" 이라고 생각했어요. 그렇다면 예를 들어 arr[1][3]은 수빈이가 x=1에 위치하고, 동생이 x=3에 위치할 때의 값이라는 건데, 그 "값"은 무엇을 의미하나요? 수빈이와 동생이 각각 해당 위치일 때의 시간 을 의미하는건가요? 만약 '시간'을 의미하는게 맞다면, 저는 해당 배열을 활용하는 예시가 전혀 생각나지 않아서 질문드렸어요. 간단히 생각해보았을 때는 오히려 불필요한 행위가 될 것 같기도 하고요. 왜냐하면 저희가 궁금한것은 궁극적으로 arr[samePos][samePos] 일텐데 이 값을 알아내는 순간은 arr가 필요 없을 것 같아서요. 결국 질문을 아주 간단하게 요약하면, "범위가 500 정도라면 2차원 배열을 만들어서 활용했을 것이라고 해주셨는데, 어떻게 활용한다는 건지 이해가 안갑니다. 활용 방안이 떠오르지 않아요" 입니다. 감사합니다.
안녕하세요 선생님~! 처음엔 15686번 문제를 bfs로 곁들여서(?) 풀었는데 시간초과가 나더라고요. 그래서 bfs를 사용하지 않고 푸니까 시간초과없이 문제가 정답처리 되었습니다. 정답 코드 : http://boj.kr/5fa47b86ba5246119038da418cfad011 시간초과 났던 코드(bfs 사용) : http://boj.kr/ef1079acc43c4eb8ab9aeafe01d00bd2 이후 시간 초과가 났던 이유를 분석해봤는데, 제 생각은 아래와 같아요. 치킨집을 고르는 최대 개수 : 13C6 집의 최대 개수 : 100 13C6 * 100 = 171,600 (많이 여유로움) 하지만, bfs를 각 집마다 적용했으므로 (50 * 50) = 2500을 최대치로 잡고 더 곱해줘야 하므로 171,600 * 2500 = 629,000,000 따라서 시간 초과가 난다. 그래서 bfs를 사용하지 않고 abs를 사용해서 바로 거리를 계산하면 이 값이 최대 13이 되므로, 171,600 * 13 = 2,230,800 (여전히 여유로움) 이라서 시간 초과 없이 통과되었다고 판단했어요. 제 질문은 아래와 같아요. bfs를 사용했을 때 의 시간 복잡도 계산식에 오류가 없나요? (잘 계산한게 맞나요?) bfs를 사용하지 않을 때 의 시간 복잡도 계산식에도 오류가 없나요? (잘 계산한게 맞나요?)
