173만명의 커뮤니티!! 함께 토론해봐요.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/511ca2fd92df4f8886ede64c256bd10e 안녕하세요 선생님! 재귀를 이용하여 양옆의 톱니들과 비교해 계속해서 갱신해 나가는 방법으로 로직을 구현하였습니다. 테스트 케이스로 테스트 중 일부는 맞고 일부는 틀리게 결과가 나옵니다. 디버깅도 해보았으나 적절한 문제점을 찾지 못하였습니다. 혹시 로직에서 틀린 부분이 있을까요? 제 눈이 더 이상 보이지 않아서 질문 드립니다ㅠㅠ
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 선생님 for(char a : str){ cnt[a - 'a']++; } 이 부분이 이해가 잘 되지 않습니다..ㅠㅠ cnt[a-'a']++ 이면 cnt[0]의 인덱스만 증가한다는 거 아닌가요?? 아니면 여기서 a가 str배열을 나타내고 있는 것인가요? 어떤 메커니즘인지 잘 모르겠습니다ㅠ
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
문제 : 긍정왕 홍철이의 구걸 여행 제가 코드는 다 맞았는데 ny,nx를 전역변수로 해주니 값이 다르던데 왜 다른지 잘 모르겠습니다. 보통 ny,nx는 지역변수로 해줘야 하나여? #include <bits/stdc++.h> using namespace std; int a[3][3] = {{10,20,21},{70,90,12},{80,110,120}}; const int dy[] = {-1,0,1,0}; const int dx[] = {0,1,0,-1}; int visited[3][3]; int ny, nx; vector<int> v; void print() { for(int i : v) cout << i << ' '; cout << '\n'; } void dfs(int y, int x) { visited[y][x] = 1; v.push_back(a[y][x]); if(y == 2 && x == 2) { print(); return; } for(int i = 0 ; i < 4 ; i++) { ny = y + dy[i]; nx = x + dx[i]; if(ny < 0 || ny >= 3 || nx < 0 || nx >= 3) continue; if(visited[ny][nx]) continue; dfs(ny,nx); visited[ny][nx] = 0; v.pop_back(); } } int main() { dfs(0,0); }
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
선생님께서 올려주신 공유 소스를 dev c++ 컴파일 하였을 때 오류가 납니다 ㅠㅠ 문제가 무엇일까요? 마지막 for(int i : v) cout << i << " "; 여기서 빨간 표시가 뜨더라구요..!! http://boj.kr/6b0acb8d4af043f88800c74b72d77610 10 9 C:\Users\PC\Desktop\AA\main.cpp [Warning] extended initializer lists only available with -std=c++11 or -std=gnu++11 29 14 C:\Users\PC\Desktop\AA\main.cpp [Error] range-based 'for' loops are not allowed in C++98 mode
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
일단 모든 케이스에 대해 다 정답처리가 됐지만, 틀렸다고 합니다. 그래서 제가 왜 그런지 잘 모르겠고 의문점을 가져서 질문을 하였습니다. 첫번 째 주석을 보시면 저는 저런식으로 생각했는데 저렇게 하는게 시간복잡도상 더 효율적이라고 판단하는데 어떻게 생각하는지 궁금합니다. 메모리도 128MB라 충분하다고 판단하여 저렇게 썼습니다. 어떤 점에서 이게 틀린지 지적해주시면 감사하겠습니다. http://boj.kr/4196de180bb04eac9c50cd3825761e1e
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요. 이분탐색 문제를 풀다가 질문이 생겨서 문의남깁니다. 6-F의 경우 최댓값을 1e18+4로 설정합니다. http://boj.kr/cb329d7bb6e049b590ebc6c647d69f5c 이에 반해, 6-G의 경우 최댓값을 1e9로 설정하는데요. (hi = 1e18로 하면 틀렸다고 뜹니다.) http://boj.kr/cddbd0a20bc54eb7ba549c25c6f3b187 그 이유를 알 수 있을까요?? 어떤 기준으로 최댓값을 설정해야 하는지 모호합니다.
해결됨
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
안녕하세요. 선생님. 동적계획법 파트에서 [동전교환(냅색알고리즘)] 정답 코드에 오류가 있는 것 같습니다. 제 파일만 그런지 모르겠는데, 첫번째 for 문에서 i 가 1부터 초기화되고, 뒤에 변수명이 arr.length로 되어있습니다.( arr.length > coin.length) 확인 부탁드립니다! 좋은 강의 감사드립니다..!
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/81a1ae0b49434b32aa98a3a34c0c8f42 반례를 찾는 것에 어려움을 느껴 질문드립니다. 좋은 강의 감사드립니다!
미해결
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
저도 배열로 접근했고 cnt와 answer 2가지 변수를 선언한 것까지는 동일했지만... solution은 전혀 달랐습니다. 현재 문제의 정답여부와 이전 문제의 정답여부를 비교하면... 총 4가지 케이스가 있다는 걸 알게 되어.. 1 1 현재 문제도 맞고 이전 문제도 맞은 경우 1 0 현재 문제가 맞고 이전 문제는 틀린 경우 0 1 현재 문제는 틀리고 이전 문제는 맞은 경우 0 0 현재 문제도 틀리고 이전 문제도 틀린 경우 로..코딩하였더니 소스도 길어지고.. 답도 틀렸습니다.... 명쾌한 영상을 보고 나니 왜 단순하게 선생님처럼 문제가 정답일 때만 코드를 작동하도록 생각하지 못 했을 가요...? 사고방식에 문제가 있는 건 아닌지.. 문제를 파악하는 노하우가 있을 가요?
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 1-G 문제를 풀었는데 일단 게시판에 있는 반례를 다 적용하여도 틀렸다고 하는데 알고리즘 부분에서 복잡해서 그런거 같은데 어떤 문제점이 있는가요? http://boj.kr/7c33677aa106459385854be91d02ac26 아.... 제가 다시 보니 asterisk가 한 개이군요,,,, 저는 asterisk 갯수도 제한 없는 줄 알았네요.. ㅎㅎㅎ;
해결됨
[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
제가 경험이 부족해서 그런 것 같은데요, 이 문제는 'x < y'라는 조건이 없다면 DFS로 풀 수 있는 문제가 아닌 것 같다는 생각이 들었습니다. https://www.acmicpc.net/problem/2644 에서 '입력' 파트를 보면, '번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.'라고만 나와있습니다. 즉, 'x < y'라는 조건이 주어져 있지 않습니다. 부모 노드 번호가 자식 노드 번호보다 작다는 조건이 주어져 있지 않는 것입니다. 그래서 저는 이 문제가 DFS로 풀리는 문제가 아닐 것 같다고 생각했었습니다. 위 그림에서는 노드2의 부모가 1이지만, 2보다 값이 큰 3이 될 수도, 4가 될 수도 있을 것이라 생각했습니다. 따라서 노드2를 방문한 이후에, 노드2와 연결된 노드 중 아직 방문하지 않은 노드들 중 어떻게 부모 노드를 찾아야하지? '부모 노드 번호 < 자식 노드 번호'라는 조건이 없으면, 부모 노드를 찾을 수 없을 것 같은데?하는 생각이 들었습니다. 문제에서 x<y라는 조건이 없는 것 같은데, 어떻게 '나와 연결되어 있고 아직 방문하지 않은 노드 중 번호가 가장 작은 노드를 방문해야겠다'는 생각을 하신 것인지 궁금합니다..
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
구간합 풀이에서 강사님께서 항상 typedef long long ll; 로 설정을 하시는데 풀이에서는 long long을 사용하지 않는데 타입 정의를 해주는 이유가 따로 있으신지 궁금합니다.
해결됨
[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
문제( https://www.acmicpc.net/problem/1260 )에 다음과 같은 조건이 있는데, 이게 무슨 의미인가요..? 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 먼저 제가 처음 작성한 코드입니다. http://boj.kr/fa4a2cffd39f4e388d7b79b7d140679 강사님의 코드와 99% 유사한데, 17코드, FOR문에서 i<=(1<<n)로 작성하였을 때, 틀렸다고 나왔습니다. 여기서, i<=(1<<n) --> i<(1<<n)로 변경하였을 때는 맞다고 나왔습니다. 그런데, 저는 (1<<n)열까지 포합시켰을 때 틀린 이유를 모르겠습니다. (1<<n) 열은 아무 값도 없어서 굳이 탐색할 필요 없지만, 전역변수로 선언하면 어차피 0으로 초기화 되므로, cnt는 항상 0이 되야 된다고 생각했는데 1<<n열의 값을 출력해보니까 -5,-6 같은 값이 들어가 있는 이유를 모르겠습니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
https://www.acmicpc.net/source/66823795 안녕하세요 선생님 항상 좋은 강의 감사드립니다. 해당 코드를 보면 선생님의 코드와 사실상 동일한 것 같은데, 왜 시간초과가 발생하는지 모르겠습니다. ㅠㅠ 제가 어떤 부분을 놓치고 있는 걸까요?
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
코드보다는 알고리즘의 사용이유입니다. sort()를 사용하면 간단하게 구현 할 수 있는데, 선택정렬을 사용하는 이유가 궁금합니다.
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 선생님 문제를 풀던 중 궁금한 내용이 생겨서 질문 드립니다. #include<bits/stdc++.h> using namespace std; string str; string bstr; stack<char> st; int flag; int main() { cin >> str >> bstr; for (int i = 0; i < str.length(); i++) { st.push(str[i]); if (st.size() >= bstr.size() && st.top() == bstr[bstr.length() - 1]) { // 마지막이랑 똑같으면 string istr = ""; for (int a = 0; a < bstr.length(); a++) { istr += st.top(); st.pop(); } reverse(istr.begin(), istr.end()); if (istr != bstr) { for (int b = 0; b < istr.length(); i++) { st.push(istr[b]); } } } } str = ""; if (st.size() == 0) { cout << "FRULA" << "\n"; } else { while (st.size()) { str += st.top(); st.pop(); } reverse(str.begin(), str.end()); cout << str << "\n"; } return 0; } 제가 처음으로 작성한 코드입니다. for(char a : str) st.push(a) 같이 범위 기반 for문 대신 for (int i = 0; i < str.length(); i++) st.push(str[i]) 같이 원래의 for문 방식을 사용했다가 메모리 초과 오류를 겪었습니다. 두 방법이 어째서 메모리 차이가 많이 나는지 궁금합니다! 항상 감사합니다 좋은 하루 되세요 :)
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
큰돌님 안녕하세요. 3주차 문제들을 풀던 중 의문점이 생겨서 질문드립니다. 3주차 개념강의 때 합을 mod 11한 숫자 중 가장 큰 수를 구하는 예시문제가 있었습니다. 이 문제를 아래와 같은 방법으로 재귀를 통해 각 숫자별로 더할지 말지로 나눠서 숫자가 {1,2,3}인 경우는 총 경우의 수가 8이 된다고 말씀하셨습니다. go(idx + 1, sum + v[idx]); go(idx + 1, sum); 그런데 3주차 문제들을 풀던 도중 백트래킹을 쓰는 경우와 이렇게 재귀로 현재 위치를 하나씩 증가시켜가며 포함하는지 안하는지를 체크해가며 완전탐색을 돌리는 경우가 같은 경우가 아닌가 하는 의문점이 들었습니다(둘 다 모든 경우를 따지는 것이기 때문입니다). 그래서 개념강의 예시문제를 다시 백트래킹으로 풀어보았는데 {1,2,3}인 경우에서 8번의 경우를 따져야 하는데 경우의 수를 4번만 도출해는 것을 확인하였습니다. 아래는 백트래킹으로 구현한 mod 11 문제입니다. #include<bits/stdc++.h> using namespace std; const int mod = 11; int n, temp, cnt, ret; vector<int> v; void go(int idx, int sum){ if(idx == n){ ret = max(ret, sum % mod); cnt++; return; } for(int i = idx; i < n; i++){ sum += v[i]; go(i + 1, sum); sum -= v[i]; } // 설명해주신 방식 // go(idx + 1, sum + v[idx]); // go(idx + 1, sum); } int main(){ cin >> n; for(int i = 0; i < n; i++){ cin >> temp; v.push_back(temp); } go(0, 0); cout << ret << '\n'; cout << cnt << '\n'; } 코드를 하나하나 디버깅해가며 체크해보면서 왜 4번만 경우를 구하게 되는지는 알게 되었는데, 개념적으로 백트래킹이라는 개념이 모든 경우의 수를 구하는 것이고, 기존에 풀었던 방법인 idx를 증가시키면서 해당 위치의 숫자를 더할지 말지를 구하는 것도 모든 경우의 수를 구하는 것이라서 두 경우의 문제 접근할 때의 사고방식이 같다고 생각하는데 왜 백트래킹은 안되는 것인가요? 두 경우의 차이점이 너무 헷갈립니다 ㅠㅠ
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
void go(int here){ if(here == 0) return; printf("%d ", here); if(here % 3 == 0 && dp[here] == (dp[here / 3] + 1)) go(here / 3); if(here % 2 == 0 && dp[here] == (dp[here / 2] + 1))go(here / 2); if((here - 1 >= 0) && (dp[here] == (dp[here - 1] + 1))) go(here - 1); return; } 왜 이렇게 하면 안되나요?
해결됨
[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
graph, visited의 사이즈를 다음 코드와 같이 노드 개수에 맞게 (n+1)로 하면 되겠다고 생각했는데, 노드 개수의 최댓값인 1000을 이용해 사이즈를 정하신 이유가 무엇인가요?? graph = [[False]*(n+1) for _ in range(n+1)] visited = [False]*(n+1)
