궤도

문제 풀이 요구하는 것이 많지만, 이 중에서 까다로운건 최빈값 구하기 뿐이다. 입력을 받으면서 모든 배열의 합도 구해놓고, 최댓값과 최솟값도 구해놓는다. 그리고 해당 숫자의 등장 횟수도 count 배열을 갱신하며 기록해준다. 중요한건 입력으로 음수가 들어오기도 한다는 것이다. 범위가 -4,000~4,000 이니까 8,000 크기의 배열을 선언하고 입력으로 들어온 값에 4,000을 더한 인덱스를 갱신하면 된다. -4,000~4,000의 범위가 0~8,000으로 변하는 셈이다. 입력을 다 받았으면 중앙값을 구하기 위해 정렬한다. 그리고 count 배열을 돌며 최빈값을 체크한다. 해당 최빈값이 유일하다면 바로 출력하면 되지만, 유일하지 않다면 배열을 다시 돌며 최빈값 중 두 번째로 작은 값을 출력한다. 최빈값..

문제 풀이 이 문제 굉장히 힘들었다. 문제 힌트에 counting sort를 사용하라고 써있어서 정석적인 counting sort로 구현했다. counting sort(계수 정렬)이 어떤 것인지 설명하는 곳은 굉장히 많으므로 생략하도록 하겠다. 아무튼 계수 정렬을 구현하려면 배열이 3개 필요하다 정렬 전 배열, 배열의 값의 누적합을 저장한 배열, 정렬 후 배열. 열심히 구현하고 채점을 돌린 나는 메모리 초과를 맞이했다. N크기의 배열을 동적할당하는 과정에서 메모리 초과가 발생한 것일까? 그래서 처음부터 max만큼의 고정 배열을 선언했다. 또 메모리 초과였다. 찾아보니 정렬 전 배열과 정렬 후 배열을 만들면 안된다고 한다. 정렬 전 배열조차 저장하지 말라니? 아무래도 이 문제는 내가 생각한 계수 정렬이 아..

문제 문제 이 문제에서 처음으로 C++에 내장된 정렬함수인 sort를 사용해봤다. 그리고 난 이제 그 이전으로 돌아갈 수 없다. sort 함수는 구조체도 정렬하고 문자열도 정렬하고 오름차순, 내림차순 그냥 내가 적당히 조건을 넣으면 다 정렬해준다. 이 함수의 활용도에 대해 말할 수 있는 기회는 뒤로도 충분히 많으니 일단 간단한 사용법만 소개한다. sort 함수는 기본적으로 오름차순 정렬을 한다. 정렬하고자 하는 배열이 있을 때 그 배열의 첫 인덱스와 마지막 인덱스+1 을 인자로 넣어주면 바로 정렬할 수 있다. 이 말은 즉, 내가 넣는 인덱스에 따라서 배열 전체가 아니라 배열의 일부만 정렬할 수도 있다는 것이다. 소스코드 #include #include using namespace std; int main..

문제 문제 생각했던 것 보다 훨씬 간단한 방법으로 풀려 당황했던 문제이다. 처음엔 '666'이 등장하는 숫자의 패턴을 찾으려고 했으나, 변수가 너무 많았다. 그러다가 이 문제가 브루트 포스에 포함된다는 것을 떠올리고, 혹시나 하는 생각을 하며 코드를 짰는데 그게 맞았다. 그냥 단순하게 666부터 숫자를 늘려가며 해당 숫자를 문자열로 바꾸고 그 문자열에 '666'이라는 패턴이 있는지 확인했다. 시간초과가 날 것이라고 생각 했는데, 코드가 돌아갔다. 소스코드 #include #include #include using namespace std; int main() { //이게 되네... int N, count = 0; cin >> N; for (int i = 666;; i++) { //666부터 시작해서 st..

문제 풀이 커다란 체스판을 8x8 체스판으로 만들 수 있는 모든 경우의 수에 대해 계산한다. 체스판을 자르고, 편의상 왼쪽 맨위칸은 흰색으로 시작한다고 가정한다. 바꿔야 할 칸의 수를 계산했다면 이게 32보다 큰지 확인해야 한다. 만약 32칸보다 많이 바꿔야 한다면, 그냥 반대로 칠하는게 더 나았던 상황인 것이다. 아무튼 이런식으로 각 부분 체스판마다 바꿔야 하는 칸 수를 세고 최솟값을 갱신하면 된다. 소스코드 #include using namespace std; int main() { int N, M, i, j, a, b, fix, min_fix = 65; cin >> N >> M; char** panel = new char* [N]; for (i = 0; i < N; i++) panel[i] = ne..

문제 풀이 지금까지 봐온 별찍기 문제 중에서 가장 어려웠다. 바로 출력하는건 정말 어려울 것 같아서 배열을 만들었다. 재귀함수를 돌리며 배열에 적당히 값을 넣어주고 한번에 출력하면 될 것 같았다. 배열을 9등분 한다고 했을 때, 가운데를 제외한 모든 구역에 대해 재귀함수를 호출한다. 배열의 크기가 1x1이 되면 호출을 끝내면 될 것이다. 어차피 가운데에 대해서는 함수가 호출되지도 않을테니 바로 별을 넣어주면 된다. 재귀함수의 인자로는 뭐가 있으면 될까. 전체 배열, 부분 배열의 왼쪽 맨위 좌표, 부분 배열의 크기를 넣으면 된다. 소스코드 #include #include using namespace std; void star(char** matrix, int x, int y, int n) { if (n =..

문제 풀이 원의 내접과 외접에 대해 기억이 난다면 이 문제가 그리 어렵지 않을 것이고, 나처럼 기억이 가물가물 하다면 힘들 것이다. 각 좌표(x1, y1 / x2, y2)를 중심으로 하고 반지름이 (r1 / r2)인 원을 그려보자. 류재명이 존재할 수 있는 위치는 각각의 경우에 대해 해당 원의 경계선이다. 원을 2개 그리게 되니까 두 원의 교점의 수가 류재명이 있을 수 있는 좌표의 수다. 그렇다면 두 원의 관계는 어떤 경우가 있을까. 빨간원과 초록원은 조규현과 백승환의 위치가 같은 경우이다. 이 상황에서 두 원의 반지름이 다르면 류재명이 존재할 수 있는 위치는 없고, 같다면 무한하다. 검은원과 보라색원은 두 원의 교점이 1개인 경우다. 각각 내접, 외접하고 있다. 파란원은 교점의 수가 2개이고 주황색 원..

문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토스테네스의 체가 무엇이냐고 물어본다면... 이런식으로 특정 소수의 배수를 전부 지우는 과정을 통해 소수를 구하는 방법이다. 만약 1~n 사이의 소수를 구하고 싶다면 √n 까지만 구하면 된다. 왜일까? n보다 작거나 같은 합성수 m=ab가 있다고 하자. a와 b가 모두 최대일 때는 a=b=√n 일 때이다. a가 이보다 커지면 b가 √n보다 작아지고 반대의 경우엔 a가 √n보다 작아질 것이다. 그러므로 √n 까지만 체크해도 모든 합성수는 지워진다는 것이다. 그렇다면 이제 구현을 할 차례이다. 0과 1은 소수가 아니니 지워주고 2부터 시작한다. 2의 배수를 전부 지워주고, 3의 배수를 전부 지워주고, 4의 배수를 지울 필요는 없다. 왜냐하면 ..