솔

최소공배수를 구하는 문제입니다. 중학교 때 배웠던 소인수분해를 기억하시나요? 만약 8과 16이라는 두 수가 주어졌을 때, 소인수분해를 통해 최대공약수와 최소공배수를 구할 수 있습니다.아래의 표는 소인수분해의 과정을 나타낸 것입니다.2816248224 12 여기서 좌측의 노란색 배경 숫자들을 곱하면 최대공약수, 최대공약수에 초록 배경 숫자들까지 곱해주면 최소공배수를 구할 수 있습니다. 8과 16의 최대공약수는 2*2*2 = 8 이 되겠고,최소공배수는 2*2*2*1*2 = 16 이 되겠죠. 소인수분해의 과정만 코드로 구현한다면, 이 문제를 해결할 수 있습니다.  최대공약수,최소공배수 구하는 함수)int common(int a, int b){ int divisor = 1; for (int i = 2..

문제는 매우 단순합니다. N을 입력받아 N번 숫자를 입력받은 후 오름차순으로 정렬하는 문제입니다. 하지만 제한시간이 2초라는 점을 감안해야 할 것 같습니다. 시간이 짧으므로, 시간 복잡도가 작은 기수 정렬 (radix sort) 를 활용해 문제를 풀어보겠습니다. https://sol248.tistory.com/17 백준_10845_큐(queue)큐를 구현하는 문제입니다.   큐의 개념)큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다. 나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고sol248.tistory.com바로 이전에 큐 문제를 푼 적이 있습니다. 이 문제도 원형 큐를 이용한 기수정렬로 풀 것이기에, 큐에 대해 모르시는 분은 10845_큐 문제를 ..

큐를 구현하는 문제입니다.   큐의 개념)큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다. 나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고 있죠. ( 스택에 대해서는 추후에 정리해보겠습니다 ) 큐에서 front와 rear은 데이터의 시작과 끝 위치를 나타냅니다. rear을 이용해 가장 나중에 최근에 데이터에 접근할 수 있고, front를 통해 가장 나중에 들어간 데이터에 접근할 수 있습니다.   큐의 종류)1. 선형 큐(Linear Queue) : 가장 기본적인 막대기 형태의 큐. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있습니다. 2. 원형 큐(Circular Queue) : 선형 큐의 단점..

규칙이 있는 아파트 문제입니다. a층의 b 호에 살기 위해서는 a-1층의 1호~b호 까지의 사람의 합 만큼 사람을 데려와야 한다는 규칙이 있습니다. 처음에는 반복문을 통해 시그마를 구현하고 하나하나 다 더해서 풀어야 하나 생각을 했지만 더 간단한 방법이 있었습니다. 아파트를 표로 구현해보았습니다.아래 표에서 규칙을 찾으면, 문제를 쉽게 풀 수 있을 것 같습니다.2층1명4명10명20명35명56명84명120명165명1층1명3명6명10명15명21명28명36명45명0층1명2명3명4명5명6명7명8명9명 __1호__2호__3호__4호__5호__6호__7호__8호__9호 규칙이 보이시나요?? 해당 호수에 몇명이 살고 있는지 구하기 위해서는, 같은 층의 이전 호수와, 바로 아래층의 같은 호수에 살고 있는 사람 수를 더..

달팽이가 올라가는데 며칠이 걸리는지 구하는 문제입니다. 조건은 고려하지 않고 문제만 보면 쉬워보여서 바로 코드를 짜보았습니다. #include int main(void){ int A, B, V; scanf("%d %d %d", &A, &B, &V); int i = 1; int height = 0; int count = 0; while (i) { height = height + A; count++; if (height >= V) { break; } height = height - B; } printf("%d\n", count); return 0;}  단순히 다..

팰린드롬에 대한 문제입니다. 문제에 나와있다시피, radar 와 sees 같이 뒤에서부터 읽어도 똑같다면 그 단어는 팰린드롬입니다. 숫자도 마찬가지로, 121 이나 12421 같이 뒤에서부터 읽어도 똑같으면 팰린드롬수 입니다. 숫자를 입력받아 팰린드롬수인지 아닌지 판별하는 프로그램을 작성해 봅시다.   1. 0이 입력될 때까지 종료되지 않아야 하므로 무한루프에 0이 입력되면 종료되도록 하는 조건을 넣습니다. while (1){ scanf("%d", &num); if (num == 0) // num이 0이면 종료 { return 0; }}   2. 입력받은 num의 자리수를 세고, number 배열에는 그대로, check 배열에는 역순으로 넣습니다. (비교하기 쉽도록 배열..

바로 이전에 풀었던 10810_공넣기 문제의 응용 버전입니다. 바구니의 개수와 움직일 횟수를 받는 것 까지는 동일하지만, 이 문제에서는 입력받은 범위의 바구니를 역순으로 바꾸어야 합니다.  바구니를 역순으로 바꾸기 위해서, 임시 배열을 만들고 0으로 초기화까지 해주었습니다.int temp[N]; for (int s = 0; s   그다음, 바구니의 범위 (i,j) 를 입력받아 임시 배열에 역순으로 저장해주었습니다.scanf("%d %d", &i, &j);for (int q = 0; q   마지막으로, 임시 배열에 있는 역순을 바구니 배열에 넣으면 입력받은 i ~ j 범위의 바구니가 역순으로 바뀌게 되는 것이죠.for (int r = i - 1; r   ..

바구니에 공을 넣는 문제입니다. 공이 들어가지 않으면 0을 출력해야 하므로 배열을 만들고 0으로 초기화를 해줘야 할 것 같습니다. 또한, i번 바구니부터 j번 바구니까지 공을 넣는데 배열의 인덱스는 0부터 시작하므로 이 점을 주의해야 할 것 같습니다. 전체 코드) #include int main(void) { // 바구니의 개수와 공을 넣을 횟수 입력받기 int N = 0, M = 0; scanf("%d %d", &N, &M); // 바구니 배열 생성하고 초기화 int basket[N]; for (int i = 0; i < N; i++) { basket[i] = 0; } // 공을 넣을 바구니의 범위와 공의 번호를 입력받아 바구니에 넣기 int i = 0, j = 0, k = 0; for (int p =..

매우 간단한 문제입니다. 입력받은 물건의 가격과 개수를 이용해 총 가격을 구하는 문제이죠. #include int main(void) { int x = 0, n = 0, a = 0, b = 0; scanf("%d\n%d", &x, &n); int sum = 0; for (int i = 0; i < n; i++) { scanf("%d %d", &a, &b); sum += a * b; } if (x == sum) { printf("yes\n"); } else { printf("no\n"); } return 0; } 하지만 틀렸습니다.. yes/no 가 아니라 Yes/No 를 출력했어야 했네요... #include int main(void) { int x = 0, n = 0, a = 0, b = 0; scan..

문제가 굉장히 깁니다. 해시 함수) 해시 함수란, 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수입니다. 자료구조에서도 사용되고, 암호용으로 사용되기도 하죠. 이 문제에서는 알파벳(a~z) 에 1~26까지 순서대로 고유 번호를 부여하여 해시 값을 계산합니다. 하지만, 이렇게만 하면 비둘기 집의 원리* 에 의해 중복되는 해시 값을 가질 수 있습니다. (문자열은 다르지만 구성하는 알파벳이 같다면 해시 값이 동일하게 나옵니다.) 따라서, 충돌(중복)이 최대한 적게 일어나게 하기 위해 각 항에도 고유 번호(항의 번호에 해당되는 만큼 특정 숫자를 거듭제곱해 곱해주기)를 부여합니다. 최종적으로 이 함수가 문제에서 말하는 해시 함수입니다. 이 함수는 자주 쓰인다고 하니 꼭 기억해두는게 좋을 것 같습니다...