게시글
질문&답변
2024.05.30
While 문 질문입니다
안녕하세요 sunny님 ㅎㅎ 이부분은 교안에도 나와있는데요. ㅎㅎ find부분을 보시면... 다음과 같이 나와있습니다. 😃 find(문자열) 특정 문자열을 찾아 위치를 반환합니다. 만약 해당 문자열을 못 찾을 경우 string::npos를 반환하며 O(n)의 시간복잡도를 가집니다. string::npos는 size_t 타입의 최대값을 의미합니다. size_t 타입의 최대값은 OS에 따라 달라지며 64비트 운영체제라면 64비트 부호가 없는 최대정수, 32비트 운영체제라면 32비트 부호가 없는 최대 정수값을 가집니다. 필자의 컴퓨터는 64비트 운영체제이기 때문에 18446744073709551615라는 값을 가집니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 2
- 19
질문&답변
2024.05.30
2-B. 유기농 배추 질문있습니다.
안녕하세요 룰루님 ㅎㅎ for (int i = 0; i 이부분을 while문이 아닌 for문으로 하셨다는거죠? for문과 while문의 시간복잡도는 크게 상이하지 않습니다. for문도 괜찮고 while문도 괜찮습니다. 또한, while문의 시간 복잡도를 구하는게 조금 헷갈리는데 간단하게라고 설명 해주시면 감사하겠습니다. >> while문이 얼마나 동작했나를 보시면 됩니다. 이 문제의 해설코드 같은 경우 while(T--)를 했기 때문에 while문의 시간복잡도는 O(T)가 됩니다. 다만, 이 코드를 제출했을 때 틀렸습니다가 나오는데 혹시 코드 잘못올리신게 아닌가요? 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 1
- 26
질문&답변
2024.05.30
1-L combi 방식으로 했을때 시간초과
안녕하세요 현이님ㅎㅎ 기저사례를 잘못 걸어서 함수가 불필요하게 많이 호출되서 그렇습니다. 기저사례는 반드시 return을 해주어야 합니다. void combi(int start, vector &b) { if (b.size() == 2) { int sum = 0; for (int i = 0; i 이렇게 해보시겠어요? 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 1
- 27
질문&답변
2024.05.29
5-H 질문
안녕하세요 ㅎㅎ 로직상 그렇습니다. 이 문제의 풀이로직이 이렇게 나눠진다고 보시면 됩니다. 이 idx를 포함한 unique한 수열의 경우의 수 + 이 범위에서 unique한 수열의 경우의 수 이 idx를 포함한 unique한 수열의 경우의 수의 경우 a, b, c 라고 했을 때 a를 포함하는 unique한 수열의 경우의 수는 a a b a b c 이겠죠? 그리고 나서 idx를 오른쪽으로 움직여가면서 해당 로직을 반복하는 것이죠. 그러나 마지막에 이 범위에서 unique한 수열의 경우의 수의 수 같은 경우 a, b, c라고 했을 때 a b c a, b b, c a, b, c 가 되기 때문입니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 2
- 61
질문&답변
2024.05.29
안녕하세요 선생님 reverse 함수 사용하지 않고 문제풀이 해봤는데...
안녕하세요 진우님 ㅎㅎ 대략적인 부분도 잘 짜셨구 for문으로 하셔도 됩니다. 다만 bool부분이 틀린 것 같습니다. 이렇게 고쳐볼까요? #include using namespace std; int main() { string str; bool flag = true; // 초기 값을 true로 설정 cin >> str; // 문자열의 절반만 확인 for (int i = 0; i 또한 문자열 전체를 확인해도 되지만 앞의 코드처럼 문자열 반만 확인해도 됩니다. 예를 들어 abcd라고 했을 때 a - d 확인하고 -> 나중에 d - a를 확인하나 둘 다 똑같기 때문입니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 2
- 44
질문&답변
2024.05.29
3-O 질문 있습니다
안녕하세요 honn님 ㅎㅎ cnt가 찾은 ret 이상이면 (제 코드에서는 mn) return하는 코를 안 적으면 왜 시간초과가 나는지 잘 모르겠습니다. 문제를 풀 때 최악의 상황을 생각해서 그 최악의 상황을 돌렸을 때 제한 시간안에 돌아가야 한다고 생각합니다. 만약 정답이 가로선 3개를 추가하는 것인 최악의 상황에서 이 코드가 유의미한 시간복잡도 차이를 만들어내지 못하는게 아닌가 하고 생각합니다. 이 문제 같은 경우 테스트케이스가 그러한 방식으로 짜여져있어서 통과와 시간초과라는 차이를 만드는 것인지 궁금합니다. >> 먼저 이 알고리즘의 유형은 백트래킹인데 백트래킹의 시간복잡도를 잡는 것은 어렵습니다. 물론 문제 시작전에 시간복잡도 최악으로 잡고 드가야 하고 -> 어? 이거 이부분에서 return 하게 되면 불필요한 정점은 탐색하지 않게 되네? -> 하면서 수정하는게 백트래킹인데 이 백트래킹까지 고려하면서 시간복잡도를 잡는게 어렵습니다. 문제를 풀 때 최악의 상황을 생각해서 그 최악의 상황을 돌렸을 때 제한 시간안에 돌아가야 한다고 생각합니다. 라는 말씀은 맞습니다만 백트래킹의 경우 백트래킹을 넣은 최악의 상황잡기가 어려워서 대략적으로 판단하셔야합니다. com++; if (cnt > 3) return; // || cnt >= mn 생략했더니 시간초과 이부분에서 mn을 넣게 되면 당연히 불필요한 부분은 줄일 수 있기 때문에 시간을 줄일 수 있는 부분이고 TC가 그런 부분에서 차이를 많이 두게 설계된 것 같습니다. 전에 선생님께서 가르쳐주신 조합 코드를 생각해보면 한번 확인한 위치는 다시는 확인을 안 하도록 start+1을 해서 코드를 작성했던 기억이 납니다. 하지만 이 코드는 확인했던 행 - 1까지는 확인을 안하도록 here을 사용하지만 열, 즉 j는 1부터 확인함으로써 중복으로 검사하고 있습니다. 왜 무한루프가 안 생기는지 이해가 잘 되지 않습니다. for (int i = start; i >> 이부분 말씀이신가요? 저거는 근데 어쩔 수 없는게 v[1][2]를 탐색하고 -> v[1][3]을 탐색하려면 i = start로 잡을 수 밖에 없어요. 그리고 if(v[i][j])를 걸어서 v[1][2] 중복 탐색은 막습니다. 검사는 하지만 -> 탐색은 막습니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 2
- 38
질문&답변
2024.05.27
2-O 질문있습니다
안녕하세요 yjs님 ㅎㅎ 전체적인 로직은 잘 짜셨는데 일부 반례를 해결하지 못하는 것 같아요 ㅎㅎ 먼저 반례는 다음과 같습니다. [)]. yjs 님 : yes 답: no 그리고 제가 yjs님 코드를 좀 다듬어 봤는데요. 이렇게 하시면 됩니다. #include #include using namespace std; int main() { while (true) { string s; stack st; getline(cin, s); if (s == ".") break; bool isBalanced = true; for (int i = 0; i isBalanced를 추가하면서 일부로직을 다듬었습니다. 참고부탁드립니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 1
- 39
질문&답변
2024.05.27
5 - B 질문입니다!
안녕하세요 JOXX님 ㅎㅎ 코드 중에 fire_str.size()-1 이부분에서 size가 0이면 -1를 참조하기 때문에 해당 에러가 발생하게 됩니다. 감사합니다.
- 0
- 2
- 45
질문&답변
2024.05.26
알고리즘 교안 62 페이지 관련 질문드립니다!
안녕하세요 bromp님 ㅎㅎ p는 int와는 다른 타입을 의미합니다. 예를 들어 double 형이 될 수도 있습니다. 해당 부분은 다음의 코드를 추가해서 설명을 보완하겠습니다. #include using namespace std; int main(){ double p = 1.5; int a = (int) p * 100; // 100 1.5 -> 1로 타입변환이 됨. int b = (int) 100 * p; // 150 cout 해당 부분은 오늘내로 수정하도록 하겠습니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 1
- 35
질문&답변
2024.05.26
2-E 기저조건 질문있습니다
안녕하세요 유태님 ㅎㅎ string(1, a[y][x]) >> string(1, a[y][x]) 는 a[y][x] 에 있는 단일 문자를 사용하여 길이가 1인 문자열을 생성합니다.여기서 1 은 반복 횟수로, 문자 a[y][x] 를 1번 반복하라는 의미입니다. 함수 안에 있는 string ret = "";를 전역으로 빼면 값이 이상해지더라구요. 이유를 잘 모르겠어서 질문드립니다. >> string quard(int y, int x, int size){ if(size == 1) return string(1, a[y][x]); char b = a[y][x]; string ret = ""; 아마 이부분을 string ret = ""; string quard(int y, int x, int size){ if(size == 1) return string(1, a[y][x]); char b = a[y][x]; 이런식으로 하셨다는거겠죠? 이렇게 되면 여기서 문제가 생깁니다. string ret = ""; for(int i = y; i 지금 보시면 quard -> quard , quard , quard , quard 이렇게 호출이 되고 있는데요. quard 함수단위로 문자열을 쌓아야 함. = (1010) + (1010) 이런식이 되어야 하는데 이렇게 되면 quard 함수단위로 쌓을 수없고 중도에 문자열이 추가 가 되서 문제가 생깁니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.
- 0
- 1
- 42