본문 바로가기

알고리즘

 (45)
음료수 얼려먹기 - 이것이 취업을 위한 코딩테스트다. 예제 5-10 N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 떄 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 * 5 얼음틀 예시에서는 아이스크림이 총 3개 생성된다. 입력조건 - 첫 번째 줄에 얼음 틀의 세로길이 N과 가로 길이 M이 주어진다.(1 M - 1: return False # 방문하지 않은 노드라면 if ice_map[x][y] == 0: # 방문한 노드는 얼음으로 만들어서 표시 ice_map[x][y] = 1 # 상, 하, 좌, 우 모두 방문해서 함수가 끝나지 않고 모두 방문되었다면 dfs..
게임개발 - 이것이 취업을 위한 코딩테스트다. 예제 4-4 현민이는 게임캐릭터가 맵 안에서 움직이는 시스템을 개발중이다. 캐릭터가 있는 장소는 1 * 1 크기의 정사각형으로 이뤄진 N * M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 갯수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으..
왕실의 나이트 - 이것이 취업을 위한 코딩테스트다. 예제 4-3 행복왕국의 왕실정원은 체스판과 같은 8 * 8좌표 평면이다. 왕실 정원의 특저안 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위취에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 * 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이떄 왕실의 정원에서 행 위치를 표현할 떄는 1부터 8로 표현하며, 열 위치를 표현 할 때는 a부터 h까지 로 표현한다...
시각 - 이것이 취업을 위한 코딩테스트다. 예제 4-2 정수N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오, 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. - 00시 00분 03초 - 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다. - 00시 02분 55초 - 01시 27분 45초 입력조건 - 첫째 줄에 정수 N 이입력된다. (N = 0) - 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. TIP 삼중 반복문으로 시간, 분, 초를 모두 돌려보며 조건문비교하는 단순 갯수세기문제이다. 3이 들어가는..
잃어버린 괄호 - 백준 알고리즘 1541번 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 출력 첫째 줄에 정답을 출력한다. 예제 입력 1 55-50+40 예제 출력 1 -35 TIP 최솟값을 구하는 방법은 '-'부호 사이사이의 모든 숫자들을 모두 더하고 구분..
회의실배정 - 백준 1931번 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..
동전0 - 백준알고리즘 11047번 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. TIP 1. 동전을 최소화 하기위해서 동전들을 오름차순으로 정렬하여 대입한다. 2. 코인이 K를 나눴을 때 몫이 0이지 않은 것만 동작하고 아닌 것은 넘어간다.
상하좌우 - 이것이 코딩테스트다. 여행가 A는 N * N 크기의 정사각형 공간 위에 서있다. 이공간은 1 * 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며 가장 오른 쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하 ,좌 ,우 방향으로 이동할 수 있으며 시작좌표는 항상(1, 1)이다. 우리앞에는 여행가가 A가 이동할 계획서가 놓여있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로 한 칸 이동 D : 아래로 한 칸 이동 이때 여행가 A가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1) 의 위치에서..

티스토리툴바