본문 바로가기

알고리즘 삽질장

 (228)
[인프런] 바둑이 승차 문제설명 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성해라. 입력조건 첫줄에 자연수 C(1 중간에 더하다가 c보다 커지면 바로 탐색 중단 if kg > c: return # 종단 조건 if idx == n: if kg c 조건이 어차피 필터링함! max_val = max(max_val, kg) return # DFS else: dfs(idx+1, kg+arr[idx]) # 해당 인덱스 값을 포함할 경우 dfs(idx+1, kg) # 해당 인덱스 값을 포함하..
[인프런] 중복순열 구하기 문제설명 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력한다. 입력조건 첫 줄에 자연수 N(3
[인프런] 합이 같은 부분집합 문제설명 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때, 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 'YES'를 출력하고, 그렇지 않으면 'NO'를 출력하는 프로그램을 작성해라. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 한다. 입력조건 첫째 줄에 자연수 N(1 근데 못쓸경우는! flag 함수 새로 두어야 함 else: DFS(idx+1, sum_val+arr[idx]) # 현재 idx에 있는 원소 사용하기로 결정! DFS(idx+1, sum_val) # 현재 idx에 있는 원소 사용하지 않기로 결정! # main DFS(0, 0) # 0번 인덱스, 누적합=0 print('NO') - sy..
[인프런] 부분집합 구하기 문제설명 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성해라 입력조건 첫 줄에 자연수 N(1 이것이 곧 해당 원소를 사용할지 안할지를 정하는 기반이 됨! check = [0] * (n+1) DFS(1)
[인프런] 재귀함수를 이용한 이진수 출력 문제설명 10진수 N이 주어지면 2진수로 변환하여 출력하는 프로그램을 작성해라. 단, 재귀함수를 이용해야만 한다. 입력조건 첫 줄에 10진수 N(1
[인프런] 아나그램(Anagram) 문제설명 아나그램이란, 두 문자열이 알파벳의 나열 순서는 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다. 예를 들어, AbaAeCe 와 baeeACA 는 알파벳의 나열 순서는 다르지만 그 구성을 살펴보면 A(2개), a(1개), b(1개), C(1개), e(2개)로 알파벳과 그 개수가 모두 일치한다. 즉, 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 한다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성해라. 아나그램 판별 시 대소문자가 구분된다. 입력조건 첫 줄에 첫 번째 단어가 입력되고 둘째 줄에 두 번째 단어가 입력된다. 단어의 길이는 100을 넘지 않는다. 출력조건 두 단어가 아나그램이면 'YES' 출력하고, 아니면 'N..
[인프런] 단어 찾기 문제설명 현수는 영어로 시를 쓰는 것을 좋아한다. 현수는 시를 쓰기 전에 시에 쓰일 단어를 미리 노트에 적어둔다. 이번에는 N개의 단어를 노트에 적었는데 시에 쓰지 않는 단어가 하나 있다고 한다. 여러분이 찾아라. 입력조건 첫 줄에 자연수 N(3
[인프런] 교육과정 설계 문제설명 현수는 1년 과정의 수업계획을 짜야 한다. 수업 중에는 필수과목이 있다. 이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있다. 만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어진다면 필수과목은 C, B, A 과목이며 이 순서대로 꼭 수업계획을 짜야 한다. 여기서 순서란, B과목은 C과목을 이수한 후에 들어야 하고, A과목은 C, B를 모두 이수한 후에 들어야 한다. 현수가 C, B, D, A, G, E로 수업계획을 짜면 제대로 된 설계이지만 C, G, E, A, D, B 순서로 짰다면 잘못 설계된 수업계획이 된다. 수업계획은 순서대로 앞에 수업이 ㅣ수되면 다음 수업을 시작한다는 것으로 해석한다. 수업계획서 상의 각 과목은 무조건 이수된다고 가정..
[인프런] 응급실 문제설명 메디컬 병원 응급실에는 의사가 한 명 밖에 없다. 응급실은 환자가 도착한 순서대로 진료를 한다. 하지만 위험도가 높은 환자는 빨리 응급조치를 의사가 해야 한다. 이런 문제를 보완하기 위해 응급실은 다음과 같은 방법으로 환자의 진료순서를 정한다. 환자가 접수한 순서대로의 목록에서 제일 앞에 있는 환자목록을 꺼낸다. 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣는다. 그렇지 않으면 진료를 받는다. 현재 N명의 환자가 대기목록에 있다. N명의 대기목록 순서의 환자 위험도가 주어지면, 대기목록상의 M번째 환자는 몇 번째로 진료를 받는지 출력하는 프로그램을 작성해라. 대기목록 상의 M번째는 대기목록의 제일 처음 환자를 0번째로 간주하여 표현한 것이다. 입..
[인프런] 공주 구하기 문제설명 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 한다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했다. 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계 방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다. 예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 ..
[인프런] 가장 큰 수 문제설명 선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했다. 여러분이 현수를 도와주저야 한다. 단, 숫자의 순서는 유지해야 한다. 만약 5276823이 주어지고 3개의 자릿수를 제거한다면 7823이 가장 큰 숫자가 된다. 입력조건 첫째 줄에 숫자와 제거해야 할 자릿수의 개수가 주어진다. 출력조건 가장 큰 수를 출력한다. 사고과정 스택을 어떻게 활용해야 하나.. 매우 고민했다.. 스스로 능력으로 구현하는 데 도무지 아이디어가 나질 않아서 강의에서 문제 풀이 아이디어만 듣고 다시 도전해보았다. 결국 구현하긴 했지만 정답 풀이와 비교해보니 내 코드가 너무 만연하고 길어진 코드임을 알 수 있었다.. 핵심 아이디어는 앞에서부터 스택에 숫자를 하나씩 ..
[인프런] 역수열 문제설명 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라고 한다. 예를 들어, 다음과 같은 수열이 있다고 가정하자. [4, 8, 6, 2, 5, 1, 3, 7] 이 때, 1 앞에 놓여있으면서 1보다 큰 수는 4,8,6,2,5로 5개이고, 2 앞에 놓여있으면서 2보다 큰 수는 4,8,6 이렇게 3개, 3 앞에 놓여있으면서 3보다 큰 수는 4,8,6,5 총 4개이다. 따라서 [4, 8, 6, 2, 5, 1, 3, 7] 의 역수열은 [5, 3, 4, 0, 2, 1, 1, 0]이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어질 때, 원래의 수열을 출력하라. 입력조건 첫..
[인프런] 증가수열 만들기 문제설명 1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어진다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열해 가장 긴 증가수열을 만든다. 이 때 수열에서 가져온 숫자는 그 수열에서 제거된다. 예를 들어, 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4이다. 맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽 끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있다. 입력조건 첫째 줄에 자연수 N(3
[인프런] 침몰하는 타이타닉 문제설명 타이타닉 유람선이 침몰하고 있다. 유람선에는 N명의 승객이 타고 있다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성해라. 입력조건 첫째 줄에 자연수 N(5
[인프런] 창고 정리 문제설명 창고에 상자가 가로방향으로 일렬로 쌓여 있다. 만약 가로의 길이가 7이라면 아래와 같이 되어 있다고 해보자. 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있으며 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 있는 사장 1개를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이라면 그 중 아무거나 선택하면 된다. 위에 그림을 1회 높이 조정을 하면 아래와 같아진다. 창고의 가로 길이와 각 열의 상자 높이가 주어진다. m회의 높이 조정을 한 후 가장 높은 곳과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하라. 입력조건 첫째 줄에 창고 가로의 길이긴 자연수 L(1
[인프런] 씨름 선수 문제설명 현수는 씨름 감독이다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했다. "다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했다." 만약 A라는 지원자보다 키도 크고 몸구게도 무거운 지원자가 존재한다면 A지원자는 탈락이다. 입력조건 첫째 줄에 지원자의 수 N(5
[인프런] 회의실 배정 문제설명 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 입력조건 첫째 줄에 회의의 수 n(1
[인프런] 마구간 정하기 문제설명 N개의 마구간이 수직선 상에 있다. 각 마구간은 $x_1, x_2, x_3, \ ..., \ x_N$의 좌표를 가지며 마구간 간에 좌표가 중복되는 일은 없다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않는다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶어한다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성해라. 입력조건 첫 줄에 자연수 N(3
[인프런] 랜선자르기 문제설명 엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어, 300cm 짜리 랜선에서 140cm 짜리 랜선 두 개를 잘라내면 20cm는 버려야 한다.(이미 자른 랜선을 붙일 수 없다.) 편의를 위해 랜선을 자를 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이 때 만들 수 잇는 최대 랜선의 길이를 구하는 프로그램을 작성해라. 입력조건 첫째 줄에는 ..
[인프런] 격자판 회문수 문제설명 1부터 9까지의 자연수로 채워진 7 by 7 격자판이 주어지면 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성해라. 회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 말한다. 단, 빨간색 처럼 구부러진 경우(87178)는 회문수로 간주하지 않는다. 입력조건 1부터 9까지의 자연수로 채워진 7 by 7 격자판이 주어진다. 출력조건 5자리 회문수의 개수를 출력한다. 사고과정 우선 데이터 범위가 7로 정해져있기도 하고 5자리이기 때문에 객 행, 열 방향으로 1칸씩 최대 2번 이동할 수 있다. 행에서는 구현하기 쉬웠지만 열 방향으로는 구현하는 데 고민을 했다. 리스트는 넘파이와 달리 열 방향으로 슬라이싱이 불가능하기 때문이다. 그래..

티스토리툴바