쭁쭁이와 프로그래머

스택 뽀개기 프로젝트 - 1 이제부터 BOJ 단계 별 문제의 스택 카테고리에 있는 모든 문제를 풀어볼까 한다.STL을 쓰면 간단하지만 첫 번째 문제인 10828번이 스택을 직접 만드는 문제이기 때문에 직접 만들어서 앞으로의 문제들에선 내 스택 라이브러리를 쓰기로 하겠다.예전에 자료구조 공부할 때 만들어 둔 C언어 라이브러리가 있긴 한데, 그때의 나에대한 불신과 C++로, 템플릿을 이용하여 다시 짜보고 싶다는 점 때문에 다시 짜보겠다. 문제https://www.acmicpc.net/problem/10828스택의 기본 ADT를 작성하고 입출력을 수행하는 문제 난이도 난이도 中, 소요시간 40분 풀이 과정 10828번에서 만들라는 스택은 int형 데이터를 받는 스택인데, 템플릿을 이용하여 int형이 아니라 다..

문제https://www.acmicpc.net/problem/90202보다 큰 짝수의 소수 곱(골드바흐 파티션)을 찾는 문제 난이도 난이도 中, 소요시간 20분 풀이 과정저번에 소수 문제를 풀어봤으니 이어서 소수 카테고리를 마저 풀기로 했다.지난 번에 2581번에서 썼던 소수 구하는 알고리즘을 다음과 같이 조금 개선했다. #include #include bool isPrime(int n) { if (n == 2) return true; if (n == 1 || n % 2 == 0) return false; for (int j = 3; j * j > test; for (int t = 0; t > n; vector results; results = go..

문제https://www.acmicpc.net/problem/2581M이상 N이하의 소수들의 합과 그 중 최솟값을 찾는 문제. https://www.acmicpc.net/problem/1929M이상 N이하의 소수를 찾는 문제. 난이도 2581 - 난이도 下, 소요시간 10분 1929 - 난이도 上, 소요시간 4시간 이상..? 풀이 과정 사실 1929번은 예전에 풀다가 실행시간이 자꾸 초과되서 짜증나서 남겨놓았던 문제이다. 그래서 소요시간을 4시간 이상이라고 적어놨다. 두 문제는 사실상 동일한 문제지만 1929번에선 실행시간을 엄격하게 본다. 먼저 간단한 2581번부터 보자.아이디어는 간단하다.어떤 수가 소수인지를 판단하여 true/false를 return해주는 isPrime이라는 함수를 n에서 시작해서 ..

문제https://www.acmicpc.net/problem/1316 단어들을 받아 몇개의 단어가 그룹단어인지 출력하는 문제. 난이도 난이도 下, 소요시간 10분 풀이 과정 그룹 단어?? 생소한 개념이다. 원래 있는 개념인지 이 문제를 위해 만든건지 딱 보고 바로 아이디어가 떠오르진 않았다. 단어의 앞에서 나온 알파벳들을 기억해뒀다가 뒤에 있는 알파벳들과 비교해야 한다는 생각에 큐를 써야하나 생각하고 있다가, 그냥 코딩을 해봤는데 코딩하는 중에 깨달았다. 기억해 둘 필요가 없다는 것을... 그냥 알파벳이 연속적으로 나오지 않았을 경우 그 뒤에 다시 나오는가만 보면 되는 거였다. 즉, 단어 내의 i번째 알파벳과 i+1번째 알파벳이 다르다면, i+2번째부터 단어의 끝까지 해당 알파벳이 존재하는지만 찾으면 된..

문제https://www.acmicpc.net/problem/2292 육각형 벌집의 각 방에 들어가기 위해 몇 개의 방을 거쳐야 하는지 구하는 문제. 난이도 난이도 下, 소요시간 10분 풀이 과정 정답률 47%짜리 문제에 실패라 떠있길래 뭐지..? 하고 눌러봤는데 예전에 내가 풀었던 문제였다.채점 기록을 보니까 6개월 전에 3번 제출했는데 3번 다 틀렸다ㅋㅋㅋㅋ문제를 보니까 기억이 났다. 그때의 나는 이걸 틀린 수준이었던가... 벌집의 규칙은 이렇다. 가운데 1개가장자리 6개그 가장자리 12개그그 가장자리 18개... 6의 배수로 증가함을 알 수 있다.따라서 1은 1개의 방, 2~7은 2개의 방, 8~19는 3개의 방, ...이고 이는 몇 번째 가장자리에 속하는가?를 구하는 문제와 같다. 따라서 N이 주..

문제https://www.acmicpc.net/problem/4344 학생들의 시험 점수들을 받아 평균을 구하고 평균이 넘는 학생들의 비율을 계산하는 문제. 난이도 난이도 下, 소요시간 10분 풀이 과정 새벽에 잠이 안와서 쉬운 거 하나 풀고 기쁜 마음으로 잠들자는 생각에 적당히 쉬운 걸 찾다가 정답률 40%정도면 적절하다 싶어서 골랐다. scores라는 vector형 배열을 만들고 차례차례 값을 받아 push해준 뒤,accumulate 함수로 0.0부터 시작해서 scores의 첫 번째 원소부터 마지막 원소까지 다 더하고 scores의 원소의 개수로 나눠준다. 예전 같았으면 C++을 쓰면서도 포인터적인(?) 사고를 못벗어나고 동적할당을 해서 값을 입력받고 평균도 직접 함수를 짜서 구했겠지만 이젠 그냥 S..

문제 https://www.acmicpc.net/problem/10250방의 개수가 h * w인 호텔에 손님이 올 때마다 엘레베이터와 가까운 순서대로 방을 배정하고 n번째 손님이 어느 방에 배정될 것인지를 찾는 문제. 난이도난이도 下, 소요시간 20분 이내 풀이 과정 h : 호텔의 층 수 w : 한 층당 방 수 n : n번째 손님 101호 -> 201호 -> 301호 -> ... -> h01호 -> 102호 -> 202호 -> 302호 -> ... -> h02호 -> ... 순이므로 n번째 손님은 n % h층으로 들어갈 것임을 먼저 생각해볼 수 있고 호수는 n / h의 몫에 1을 더한 것임을 쉽게 알 수 있다. 즉, n%h층 n/h + 1호 가 된다. 건물의 왼쪽 줄부터 채워지기 시작하기 때문에 w는 식..