본문 바로가기

알고리즘 문제 풀어보기

[카카오/신입공채] 비밀 지도 (2017/09/27) 카카오 신입 공채 (2017/09/27)- 비밀 지도 - 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 “공백”(“ “) 또는 “벽”(“#”) 두 종류로 이루어져 있다.전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 “지도 1”과 “지도 2”라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.“지도 1”과 “지도 2”는 각각 정수 배열로 암호화..
[카카오/신입공채] 다트게임 (2017/09/27) 카카오 신입 공채 2017/09/27- 다트게임 문제 - 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다.각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다.옵션으로 스타상(*) , 아차상(#)이 존재하며..
[백준 2501번] 약수 구하기 백준 2501번- 약수 구하기 문제 - 문제어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 6을 예로 들면6 ÷ 1 = 6 … 06 ÷ 2 = 3 … 06 ÷ 3 = 2 … 06 ÷ 4 = 1 … 26 ÷ 5 = 1 … 16 ÷ 6 = 1 … 0그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. 출력첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을..
5x5 배열에 직각삼각형 만들기 직각삼각형 만들기 정보처리기사 실기 알고리즘 문제에 직각삼각형 안에 값을 넣는 그런 문제들이 있어서그럼 근본적으로 직각삼각형을 어떻게 만드는지에 대하여 알아볼 것이다. 일단 예시로 5x5배열에 직각삼각형을 만들어 볼텐데 배열 칸수는 상관없이 정사각형 모양이면 된다. 정사각형꼴의 배열에 직각삼각형은 총 4가지 경우의 모양으로 나오는데 하나씩 살펴보자 1번째 경우 배열로 생각해서 본다면 arr[i][j]에서i = 0, j = 0i = 1, j = 0, 1i = 2, j = 0, 1, 2i = 3, j = 0, 1, 2, 3i = 4, j = 0, 1, 2, 3, 4 인덱스 번호에 다음과 같은 규칙성이 나타난 것을 알 수 있다. j의 시작점은 0으로 고정인데 반해,j의 끝부분은 i와 같은 값이 나온다.이는 이..
최대공약수, 최소공배수 구하기 알고리즘(+약수 구하기) [최대공약수 / 최소공배수 알고리즘] 정보처리기사 실기 문제 중 한 가지인 최대공약수/최소공배수 알고리즘을 공부하면서 포스팅을 해 본다.보너스로 약수 구하는 알고리즘도 간단하게 남겨본다. 1. 최대공약수 (Greatest Common Divisor) 최대공약수는 0이 아닌 두 개 이상의 정수의 공통되는 약수이다. 보통 최대공약수를 구하라 하면이와 같이 그려서 구할 것이다. 하지만 프로그래밍 언어로 변환하여 나타내려면 어려울 것이다.따라서 프로그래밍 언어로 구현하고자 할 때는 다음과 같은 방법으로 나타낸다.이와 같이 두 수의 나머지값으로 최대공약수를 구할 수 있다. 글로만 봐서는 이해가 어려울 수 있으니 최대공약수를 구하는 함수와 같이 보자. 123456789101112131415161718//gdc : ..
[백준 1475] 방 번호 문제 1475번 방 번호 문제 문제 다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입력 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 필요한 세트의 개수를 출력한다. 입력 예제 9999 출력 예제 2 이 문제는 얼마나 빨리 규칙을 찾고, 그 규칙을 어떤 방법으로 처리해 결과를 나타낼 것이냐에 따라 달린 문제이다. 규..
[백준 8958번] OX퀴즈 문제 : OX퀴즈 문제"OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다."OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다.OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다. 출력각 테스트 케이스마다 점수를 출력한다. 예제 입력5 OOXXOXXOOO OOXXOOXXOO OXOXOXOXOXOXOX O..
[백준 1152번] 단어의 개수 구하기 (문자열 문제) 단어의 개수 문제 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 들어가 있을까? 단 한 단어가 여러 번 들어가면 등장한 횟수만큼 모두 세어야 한다. 입력첫 줄에는 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000 을 넘지 않는다. 단어는 띄어쓰기로 구분한다. 공백이 연속으로 나오는 경우는 없다. 또한 문자열 앞, 뒤에는 공백이 있을 수 있다. 출력첫째 줄에 단어의 개수를 출력한다. 예시입력 : The Curious Case of Benjamin Button출력 : 6 이 문제를 접근한 방식으로는 1. 문자열에서 공백(띄어쓰기)의 개수를 받는다.2. 공백의 수 + 1 = 단어의 개수 간단한 문제이겠거니 생각했지만 생각..

티스토리툴바