Connecting the dots

행렬의 곱셈 - Lv.2 문제 설명 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요. 제한 조건 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 입출력 예 arr1 arr2 return [[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]] [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20..

다이나믹 프로그래밍이란? (Dynamic Programming) 다이나믹 프로그래밍이란 기본적으로 복잡하게 반복해야 하는 문제를 여러개의 문제로 나눈 후, 그 문제들을 매 번 반복하지 않고, 그 값을 저장해 두었다가 재 사용하는 기법이다. 위에 달아놓은 블로그에 가서도 볼 수 있지만, 네 살짜리 아이에게 다이나믹 프로그램을 어떻게 설명해야하나요? 라는 질문에 달린 명쾌한 답변이 있었다. 종이에 "1+1+1+1+1+1+1+1 =" 을 쓰고, 아이에게 답이 무엇이냐고 묻는다. 아이 : (숫자를 하나씩 센 후) 8! 문제의 왼쪽에 "1+"을 덧붙인 후, 아이에게 다시 답을 묻는다. 아이: (빠르게) 9! 어떻게 9인지 빨리 알았니?라고 물으면 아이는 "그냥 1을 더했어요!" 라고 말한다. 왜냐하면 8을 기억해..

전화번호 목록(해시) - Lv.2 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들..

체육복(탐욕법(Greedy)) - Lv.1 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을..

K번째수(정렬) - Lv.1 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1..

완주하지 못한 선수(해시) - Lv.1 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion ret..

최단 경로(Shortest Path) 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 각 지점은 그래프에서 노드로 표현되며, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 ..

정렬 알고리즘 - Sort Algorithm 정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용되는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보려고 한다. 선택 정렬 - Selection Sort 설명 컴퓨터가 데이터를 정렬할 때 어떻게 할지 한번 생각해보자. 데이터가 무작위로 여러 개 있을 ..

List to String, 리스트를 문자열로 변경하기 파이썬에서 리스트를 문자열로 변경하는 두 가지 방법에 대해 알아보자. 1) Join 메소드를 이용하는 방법 2) for문을 이용하는 방법을 통하여 배열을 문자열로 변경할 수 있다. - Join 메소드를 이용하는 방법 파이썬의 String 클래스는 'join(list)' 메소드를 제공하고 있다. join 메소드를 이용하면 리스트를 구성하고 있는 각각의 캐릭터들을 하나의 문자열 형태로 변경해서 반환해준다. 다음과 같이, seperator.join(iterable)의 형식으로 사용하면 된다. list = ['a', 'b', 'c'] print(''.join(list)) # abc print(','.join(list)) # a,b,c 지정된 구분자로 구분되..

[Python] 2차원 리스트 생성 및 입력 받기 1. 2차원 리스트의 구조 2차원 리스트는 1차원 리스트를 묶어놓은 구조로, 많이 사용되는 자료구조 중 하나이다. 2차원 리스트의 선언은 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 한다. ex) 2행 4열의 2차원 리스트 a = [ [0, 1, 2, 3], [4, 5, 6, 7] ] 0 1 2 3 4 5 6 7 이제 리스트를 선언하고 초기화 하는 방법에 대해 알아보자. 2. 리스트 초기화 arr = [0, 0, 0, 0, 0] arr = [0] * 5 arr = [i for i in range(2, 9) if i % 2 == 0] # [2, 4, 6, 8] brr = [[1, 2, 3], [1, 2, 3], [1, 2, 3]] brr = [[1..