알고리즘 문제 34

[알고리즘 2단계] 방 배정하기-완전 탐색 (Brute-Force)

[출처 : Goorm 사이트 - 웃긴 뽑기] 문제 정보 초등학교 6학년 여학생들(중학교 3학년 남학생들)은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다. 예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년..

[알고리즘 2단계] 다이아몬드, 마름모 (반복문 활용)

[출처 : Goorm 사이트 - 웃긴 초밥] 문제 가장 빛나는 보석 다이아몬드를 출력하는 문제입니다. 입력한 숫자에 해당하는 줄 수 에 맞게 다이아몬드 모양(마름모)을 출력하는 프로그램을 작성해보시오. *주의사항은 입력이 짝수일 경우와 홀수일 경우의 처리입니다. 입력 자연수 (최대 100) 출력 입력한 수에 맞는 라인 수를 가진 마름모 모양 풀이 이중 반복문 연습할 때 많이 해보았던 유형이다. *로 피라미드를 만들었던 것을 잘 응용하면 될 것 같다. - 피라미드 만드는 코드 //피라미드 #include int main() { int n; scanf("%d", &n); for(int i=1; i

[알고리즘 2단계] 방 탈출하기 (퀵 정렬, 이진탐색)

[출처 : Goorm 사이트 - Yun Goon] 문제 한밤 중에 갑자기 출출해진 종수, 뭐라도 사먹기위해 편의점으로 향하던 중 괴한으로부터 습격을 받아 정신을 잃었습니다. 긴 시간이 흐르고, 정신을 차린 종수는 자신 앞에 길이가 N인 수열과 그 옆에 떨어진 메모지를 발견하였습니다. 메모지를 읽어보니 다음과 같이 쓰여있습니다. 이 방을 탈출하고 싶다면 다음 지시를 따르시오. 눈 앞에 보이는 수열을 모두 외운 후 벽에 있는 버튼을 누른다. 모니터를 통해 M개의 숫자를 하나씩 보여주면, 그 숫자가 수열에 있는지 없는지 바로 대답한다. 한 번이라도 실패하면 탈출할 수 없다. 종수는 과연 이 방을 탈출할 수 있을까요? 입력 첫째 줄에 정수 N이 주어집니다. (단, ) 둘째 줄에 수열을 구성하는 -10억 이상 1..

[알고리즘 2단계] 알파벳 빈도 구하기

[출처 : Goorm 사이트 - 심심한 튀김] 문제 이 문제는 입력된 문장에 포함된 알파벳의 빈도를 구하고 출력하는 것이 목표입니다. 대소문자 구분 없이 알파벳의 빈도를 구하는 프로그램을 작성하십시오. 입력 임의의 문장(최대 80자) 출력 알파벳 별 빈도 수 풀이 if나 switch문을 사용하면 코드가 너무 길어지니 배열과 반복문으로 간결히 만들어보자 1. 출력 부분 코드 - 아스키코드를 사용하여 알파벳의 10진수 값을 이용한다. for(int j=0; j96)alpa = input[i]-97;//소문자의 아스키 10진수값의 시작이 (a:97, b:98...) elsealpa = input[i]-65;//대문자의 아스키 코드 10진수값의 시작이 65 (A:65, B:66...) alpha_count[al..

[알고리즘 2단계] 완전수

[출처 : Goorm 사이트 - 화난 묵밥] 문제 완전수란 자신을 제외한 모든 약수의 합이 자신과 같은 수를 말합니다. 입력값으로 범위를 입력하고 해당 범위 내의 완전수들을 모두 출력하는 프로그램을 작성하세요. * 완전수의 예 : 6 6의 약수 1, 2, 3, 6 => 1 + 2 + 3 = 6 (완전수) 입력 두 수 A, B ( A 1부터 해당 수 까지 나누기해서 나머지 값이 '0'인 경우 2) 구한 약수 더하기 3) 더한 결과값이 숫자 n과 같은지 비교 4) 같은 경우 출력하기. 이중 반복문을 이용했다. 숫자가 완전수 인지 판별할 때마다 이전 ..

[알고리즘 2단계] Factorial(계승)

[출처 : Goorm 사이트 - 슬픈 냉면] 문제 팩토리얼은 1부터 n까지의 수를 모두 곱하는 것입니다. n이 양수일 때 n의 팩토리얼은 로 나타냅니다. 팩토리얼의 결과를 구하는 프로그램을 작성하십시오. 입력 15 이하 양의 정수 출력 팩토리얼의 결과 값 풀이 재귀식 개념 이해할 때 자주 작성했던 문제였다. 재귀식과 반복문 형식으로 풀 수 있다. 재귀식과 반복문 형식으로 작성할 수 있다. 이와 비슷한 문제로 저번에 풀어본 피보나치 수열 문제가 있다. 재귀식 //재귀식 함수로 작성 #include unsigned long long fac(int); int main() { unsigned long long n; scanf("%lld", &n); printf("%lld", fac(n)); } unsigned ..

[알고리즘 2단계] 계산기

[출처 : Goorm 사이트 - 기쁜 전골] 문제 이 문제는 사칙 연산을 수행할 수 있는 계산기를 프로그램화하는 것이 목표입니다. *switch문 사용을 권장합니다. 입력 두 수의 +, -, *, / 연산 중 하나 ( '수1 연산 수2' 형태로 입력) *단, 두 수는 정수이다. 출력 연산에 맞는 결과 *단, 나눗셈의 경우 결과값을 소수 둘째 자리까지 표시 풀이 스위치문 사용 입력 3개 사칙연산 case 4가지 경우 2단계 문제지만 스위치의 기본 문법만 알고 있어도 충분히 풀 수 있다. 나누셈 할 때 형 변환 연산자만 잘 쓰면 될 것 같다. #include int main() { int fir; int sec; char a; scanf("%d %c %d", &fir, &a, &sec); switch(a){..

[알고리즘 1단계] 369게임

[출처 : Goorm 사이트 - 노곤한 초밥] 문제 여름을 맞아 친구들과 여행을 간 구름이는 369게임을 하게 됐다. 369게임은 여러명이 둘러앉아서 숫자를 하나씩 돌아가며 말하다가 숫자에 3,6,9가 포함된 숫자가 되면 박수를 치는 게임이다. (이때, 해당 숫자에 3,6,9가 여러 개이면 박수를 개수만큼 쳐야 한다. 예를 들어 33, 36의 경우 박수를 두 번 쳐야 한다) 게임이 끝난 숫자 N이 주어졌을 때, N 이전까지 박수를 친 횟수를 구하여라. 풀이 369게임 알고리즘!! 생각보다 쉽게 접근하면 되는 문제였다. 각 자리수 마다 3, 6, 9가 있는지 파악하고, 만약 있으면 카운트하면 된다! 각 자리수 마다 있는지 판별법 : 몫이 0이 될 때까지 10으로 나눈다. 그다음, 나머지가 3, 6, 9인지..

[알고리즘 1단계] 단어의 개수 세기

[출처 : Goorm 사이트 - 화난 튀김] 문제 문자열 한 줄이 주어졌을 때, 해당 줄에 몇 개의 영단어가 존재하는지 계산하는 프로그램을 작성하시오. 문자열은 알파벳 대/소문자 및 공백으로 구성되어 있으며, 공백 없이 하나 이상의 알파벳이 연속된 부분 문자열(Substring)을 단어(Word)로 정의한다. 예를 들어서 문자열 Goorm Edu 의 경우 두 개의 단어 Goorm, Edu가 존재한다. 입력 형식 한 줄에 공백과 알파벳을 포함하는 문자열이 주어진다. 문자열의 길이는 1글자 이상 1,000글자 이하로 주어진다. 출력 형식 입력으로 주어진 문자열에 존재하는 영단어의 개수를 정수로 출력하시오. 풀이 간단하게 생각했는데 생각보다 까다로웠다. 입력의 종료를 뜻하는 엔터키의 입력이 아스키 코드로 0 ..

[알고리즘 1단계] [KOI 2016] 타일 장식물

[출처 : Goorm 사이트 - Yun Goon] 문제 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1 인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. 1, 1, 2, 3, 5, 8, ... 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는..