Doby's Lab

문제를 풀다 보면 어떤 한 변수를 자료형이 가질 수 있는 최댓값 혹은 최솟값으로 선언할 일이 생긴다. 일일이 선언하는 경우는 까다로워 그와 관련된 헤더 파일이 있다는 것을 알게 되었다. https://docs.microsoft.com/ko-kr/cpp/c-language/cpp-integer-limits?view=msvc-160 C 및 C++ 정수 제한 자세한 정보: C 및 C++ 정수 제한 docs.microsoft.com

논리 입력으로 4가 주어지면 4자리 수 중에 예를 들어 7331이면 맨 앞자리부터 7, 73, 733, 7331처럼 모두 소수가 되어 만족하는 수들을 구하는 문제였다. 논리를 이렇게 짜두고 코드는 반대로 7331, 733, 73, 7 순서로 소수인지 판별했다. 하지만, 이는 시간 초과를 유발한다. 그래서 반대로 맨 앞자리부터 소수 판정을 하는 코드를 짰다. 왜냐하면 극단적으로 8자리 수가 주어졌을 때, 8자리 수가 소수인지 판정을 하고 7자리 수가 소수인지 판정하는 것보다는 1자리 수가 소수인지 판정하고 그다음으로 넘어가는 형식이 더 빠르기 때문이다. 그래서 다음과 같이 코드를 짰다. (맨 처음의 수를 기억하고 있어야 하기 때문에 solution 함수에서 answer에 초기값을 넣어줬다.) #includ..

(N과 M (1) 문제를 중심으로 설명하려 했으나 Backtracking과 DFS의 차이를 설명하기 위해 N과 M (2) 문제가 적합하다는 생각이 들었다.) 개념 백트래킹은 DFS를 응용하여 나온 알고리즘 같았다. DFS에 대해서는 그래프 이론에 대한 문제를 풀기 시작할 때 제대로 다시 다루겠지만 간단히 정리하면 어떠한 그래프가 주어졌을 때, 시작 노드로부터 연결돼있는 모든 노드를 탐색해나가는 완전 탐색 알고리즘이다. 또한 노드끼리 연결되었는가도 따져보아야 하는데 다음에 다시 다루겠다. 이러한 그래프가 있다고 가정하자. 시작 노드가 1일 때, DFS는 모든 노드들을 다음과 같이 탐색해나간다. 백트래킹은 DFS에 어떠한 조건을 주어서 (조건이라고 해서 무조건 if문을 사용하지 않는다.) 원하는 부분만 탐색..

이 문제는 논리를 짤 수 없어서 다른 사람들의 답을 참고했다. 그래도 이분 탐색을 사용해서 풀어보고자 했던 마음이 있었기에 논리만 참고했다. 논리는 이랬다. 어떠한 거리가 주어지면 '그 거리와 같거나 그 이상의 거리를 가질 때'의 공유기가 설치될 수 있는 개수가 주어진 C보다 많으면 거리를 더 늘려서 탐색해나가고, 그와 반대로 어떠한 거리가 공유기가 설치될 수 있는 개수보다 작으면 거리를 좁혀서 탐색해나가는 논리였다. 논리를 알기 전까지는 어디에 포커스를 두어야 할지도 몰랐다. 구하는 것이 거리이기에 거리에 초점을 두어야 했을까 코드 탐색 내가 짠 코드를 토대로 나름의 해설을 해두어야 할 거 같다. #include #include #include using namespace std; int main() ..

이 문제를 보았을 때, 너무 쉬운 문제인데 CLASS 2에 왜 있을까라는 생각을 했다. 어떤 수 N이 있다고 가정하자. 'N이 카드 패에 있는지 없는지는 그냥 for문 돌려서 확인하면 끝나는 거 아닐까?'라고 생각할 수 있었다. 하지만, 문제에서의 N과 M의 주어진 범위를 보고, 시간제한을 보면 떠올랐던 생각으로 풀었을 때 '시간 초과'라는 오류를 초래할 수 있다. 왜냐하면 N의 범위가 1~500,000 M의 범위가 1~500,000이면 for문을 돌렸을 때 시간 복잡도가 O(N*M) 일 것이고, 최댓값이 250,000,000,000 즉, 2500억을 넘어가기 때문이다. 시간제한은 1초로 약 1억번 안에 끝내라는 암묵적인 조건을 주기 때문에 for문으로는 처리할 수가 없었다. 해결법 어떠한 배열 안에 특..

알고리즘 문제에서 소수에 관한 문제를 보면 1차적으로 에라토스테네스의 체를 떠올리게 된다. 허나, 에라토스테네스의 체를 잘못 알고 있었기 때문에 블로그의 정리를 해두려한다. (이름 외우는게 젤 어려워.. 아리토스테네스 아레스토테네스...) 기존에 잘못 알고있었던 건 어떤 정수 N이 있을 때 2부터 N까지 소수를 구하려면 2부터 N의 제곱근까지 범위를 주면된다. 이까지만 알고 범위 안에서 뭘 하는지 생각하지 않고 있었다. 물론 소수를 구할 때 N의 제곱근까지만 범위를 준다는게 시간을 조금이라도 줄여주는 것은 존재하는 내용이다. 에라토스테네스의 체 2~정수 N까지의 소수를 구한다고 했을 때 에라토스테네스의 체를 몰랐다면 2~N 사이의 값 i를 i 이하 수들로 나누어보며 소수인지 아닌지 판별했을 것이다. 이런..

다음 문제를 풀 때 부호가 나올 수 있는 경우는 구현을 했지만 "NO"가 출력되어야 하는 부분을 처리하지 못했다. 내가 짰던 코드는 다음과 같다. #include #include #include using namespace std; int main() { int n; cin >> n; stack idx; vector sample; vector chart; for (int i = 0; i > a; sample.push_back(a); } int max = sample[0]; for (int i = 1; i max) { while (1) { if (idx.top() == sample[i]) { popNum.push_back(idx.top()); idx.pop(); ..

평소 문자열 문제(특히 입력)에 취약하던 입장에서 이 문제로 문자열 입력에 대해 정리를 하려 한다. 처음에는 string 변수를 선언하여 입력 문자들을 집어넣으려 했다. >> 공백 전의 한 단어밖에 담지 못 하기 때문에 pass getline() 그래서 공백을 포함한 모든 문자열을 담을 수 있는 방법이 필요했다. >> getline(입력스트림(입력할 방법(?)), 문자를 담을 곳, 이 문자가 나오면 입력을 끝내겠다는 문자) getline은 에 선언되어있다. ex) #include int main(){ string idx; getline(cin, idx, '\n'); } >> idx라는 string 변수에 cin을 통해 '\n'이 나오기 전까지 입력을 받겠다는 뜻이다. 그밖에도 문자열 입력에 관한 함수들을..