생각 구조체를 사용해서 풀면 될 것 같다. 문제를 풀 때 시행착오를 겪었는데, 처음에는 struct s s1[100005]로 구조체 배열을 선언했었는데, 그러면 코드가 잘 실행되지 않는다. -> 스택 오버플로우가 발생하기 때문! 구조체 배열을 동적 할당하자. 그리고 정렬을 할 때 그냥 sort를 썼었는데, 그냥 sort를 쓰면 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않는다. -> sort가 아닌 stable_sort를 써야한다. 코드 #include using namespace std; struct s { // 구조체 선언 int age; string name; }; bool compare(const s& s1, const s& s2) { // 나이가 적은 순서대로 정렬 retur..
생각 수의 개수가 천만개까지 주어진다. 일반적인 방법을 썼다가는 분명히 시간이든 메모리든 초과가 뜰 것 같다. 그래서 그냥 sort는 안될 것 같고, merge sort를 써보기로 하였다. -> merge sort를 사용해도 메모리 초과가 되었다. 그래서 그냥 sort를 써보았다. -> 당연히 안됐다. 왜 자꾸 메모리 초과가 뜰까? 배열을 천만개를 선언해서 그런가? 그러면 벡터를 써볼까? -> 그래도 안됐다. 그렇다면 주어진 수는 10000보다 작으니, 주어진 수를 10000 크기의 배열에 넣고 그 배열을 순회하면서 배열에 들어간 수만큼 그 숫자를 출력한다. -> 몇번의 실패끝에, 드디어 성공했다. 코드 #include typedef long long ll; // 큰 수가 쓰이므로 int 대신 long ..
생각 앞선 N과 M 문제처럼 백트래킹을 사용하면 된다. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 출처 : https://chanhuiseok.github.io/posts/algo-23/ 알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 이번에 살펴볼 개념은 백트래킹에 관한 내용입니다. chanhuiseok.github.io 만약 백트래킹에 대해서 더 자세히 배우고 싶다면 바킹독님의 강의를 듣는 것을 추천한다. 바킹독 백트래킹 강의 다른 점은 같은 수를 여러 번 골라도 된다는 점이다. 그렇다면 수가 사용되었는 지 검사하는 부분은 빼도 된다. 그리고 예제 ..
생각 재귀를 사용하면 될 것 같다. 1. 사각형을 4분면으로 나눠서 거기서부터 루프를 돌면서 0인지 1인지 확인한다. 2. bool 변수를 두개 만든다. 하나는 루프를 돌 때 한 번이라도 1이 나오면 false(흰색 사각형이 아니라는 뜻), 또 하나는 루프를 돌 때 한 번이라도 0이 아니면 false(파란색 사각형이 아니라는 뜻.)이다. 3. 그리고 재귀를 사용해서 흰색 혹은 파란색 사각형을 찾을 때까지 계속 탐색한다. 4. 두 bool 변수 중 하나라도 true가 나오면 사각형을 찾은 것이므로 재귀를 그만둔다. 5. 파란색 사각형이면 파란색 사각형의 개수를 나타내는 변수에 1을 더하고, 흰색 사각형이면 흰색 사각형의 개수를 나타내는 변수에 1을 더한다. 6. 모든 과정이 다 끝나면 하얀색 색종이의 개수..
생각 BFS를 사용하여 푸는 문제이다. 일단 나이트는 한 칸을 이동한 후 바라보는 방향의 대각선으로 이동할 수 있다. 따라서 이동은 X = { 1 2 2 1 -1 -2 -2 -1} Y = { 2 1 -1 -2 -2 -1 1 2} 이렇게 설정할 수 있다. (오른쪽으로 갈수록 x가 커지고, 아래쪽으로 갈수록 y가 커진다고 가정했다.) dist 배열을 만들어서 지금 내가 몇번 이동했는지 배열에 입력해야겠다. 코드 #include using namespace std; int board[305][305]; int dist[305][305]; // 해당 칸을 방문했는지 여부를 저장 #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int..
생각 일단 이항 계수가 무슨 뜻인지 몰라서 검색을 해봤다. 이항 계수는 nCk 였구나. 고등학교 확통 시간 때 배운 적이 있다. 문제 조건에서 0 > k; int ans = factorial(n) / ( factorial(k) * factorial(n - k) ); cout
생각 맨 처음 든 생각: 벡터로 입력받아서 오름차순으로 정렬한 다음, M/3과 가장 가까운 수를 찾아서 그 수와 양 옆에 있는 수를 더한 값을 구하면 될 것 같다. -> 정렬했을 때 붙어있는 세 값의 합만이 정답이 아니다. 반례가 있으므로 틀렸다. 두번째 든 생각: 벡터로 입력받아서 오름차순으로 정렬한 다음, (*it) + *(it+1) + *(it+2)가 m보다 클 때를 찾아서 그 때 *(it-1) + *it + *(it+1)을 구하면 될 것 같다. -> 아까 위에 말했던 것처럼 정렬했을 때 붙어있는 세 값만이 정답이 아니다. 역시 틀렸다. 붙어있는 값들의 합만이 정답이 아니다. 그러면 어떻게 해야될까? -> 삼중루프를 돌려서 m과 가장 가깝지만 m보다 작은 값을 찾는다. 여기서 주의해야 할 점은 삼중..
생각 이 문제에서 해결해야 될 문제는 크게 두 가지다. 1. [숫자,숫자,숫자...]를 입력받고 어떻게 숫자만 쏙 빼서 덱에 넣을까? 2. 뒤집는 것과 지우는 것을 어떻게 구현하면 될까? 처음에는 1번 문제를 어떻게 풀었냐면, 1. string으로 배열을 입력받는다. 2. '[', ',' ']'가 아니면 숫자로 바꿔서 덱에 push한다. 하지만 이렇게 하면 문제가 있다. 만약 두 자리 수의 숫자가 들어왔을 경우에도 숫자를 따로따로 인식하게 되기 때문이다. 그래서 어떻게 풀었냐면, 1. string으로 배열을 입력받는다. 2. ',', ']'가 아니면 또 다른 string 변수에 더해준다. 3. 만약 ',' 나 ']'이 나오면 string 변수를 stoi로 int로 바꿔주고 덱에 push한다. 4. str..
어떻게 풀까? (문제를 처음 보고 든 생각) 스택을 사용하자. for문을 써서 현재 for문이 가리키는 알파벳이 스택의 top에 있는 알파벳과 같다면 pop을 하자. for문 loop가 다 끝나고 스택이 비어있으면 좋은 단어고, 아니면 좋은 단어가 아니다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; // 단어 수 int cnt = 0; // 좋은 단어 개수 cin >> n; while (n--) { stack s; string a; cin >> a; for (int i = 0; i < a.length(); i++) { if (s.empty()) { // 스택이 비어있다면 s.push(a[..
어떻게 풀까? (문제를 보고 처음 든 생각) 큐를 사용해서 풀면 될 것 같다. 먼저 큐의 front를 한 번 pop하고, 그리고 임시 변수에 갱신된 큐의 front를 저장하고, 큐의 front를 다시 pop한다. 그리고 임시 변수를 큐에 push한다.(위에 있던 수를 밑으로 옮기는 효과) 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); queue q; int n; int temp = 0; cin >> n; for (int i = 1; i n; for (int i = 1; i
