/* 본 게시물은 ' 이것이 코딩 테스트다 with Python | 나동빈 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ # 그리디 알고리즘 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라는 특징이 있다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족 시킬 수 있으므로 그리디 알고리즘 문제는 자주 정..

/* 본 게시물은 ' 이것이 코딩 테스트다 with Python | 나동빈 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [점프 투 파이썬] 리스트 자료형 : https://wikidocs.net/14 #리스트 자료형 리스트는 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용한다. 리스트는 시퀀스(순서) 자료형(string, list, tuple)이다. 내부적으로 배열을 채택하고 있으며, 연결 리스트 자료구조 기능을 포함하고 있어서 append(), remove() 등의 메서드를 지원한다. 파이썬에서는 따로 배열이 있지 않고 리스트를 사용한다. 리스트 만들기 a = [1, 2, 3, 4, 5, ..

/* 본 게시물은 '이것이 코딩테스트다 with Python | 나동빈', 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [URL] : 1. 정수형 정수형에는 양의 정수, 음의 정수, 0이 있다. # 1. 정수형 a = 100 # 양의 정수 a = -100 # 음의 정수 a = 0 # 0 파이썬 정수 계산에 있어 특이점으로는 '/', '//' 연산자를 구분한다는 점이다. '/' 는 나눈 결과를 '//'는 몫을 뜻한다. # 정수 계산 a, b = 5, 3 print(a / b) # 나눈 결과 1.6666666666666667 print(a // b) # 몫 1 print(a % b) # 나머지 2 prin..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 11729번 - 하노이 탑 이동 순서 : https://www.acmicpc.net/problem/11729 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [BoostCourse] 자바로 구현하고 배우는 자료구조 - 힙 정렬 : https://www.boostcourse.org/cs204 힙 정렬 힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 한다. *힙에 대해 자세히 알고 싶다면 다음 글을 확인하면 된다. 만약 데이터가 힙 규칙에 따라 있다면, trickleDown을 반복하면 숫자들이 정렬된다. 이때 최대힙 이면 오름차순으로, 최소힙이면 내림차순으로 정렬된다. 코드는 다음과 같다. fun heapSort(): E{ val removeVal = array[1] as E if (arr..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [URL] : fun main() { var arr = arrayOf(1,2,3,4,5) var size = 4 fun swap (from: Int, to: Int){ val tmp = arr[from] arr[from] = arr[to] arr[to] = tmp } /** * swap(1,size) * size-- * ---------------- * size-- * swap(1,size) */ // 함수 실행 후 감소 swap(1, size--) // [1, 5, 3, 4, 2] println(arr.contentToString()) arr = a..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1436번 - 영화감독 숌 : https://www.acmicpc.net/problem/1436 문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1018번 - 체스판 다시 칠하기 : https://www.acmicpc.net/problem/1018 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 7568번 - 덩치 : https://www.acmicpc.net/problem/7568 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 2231번 - 분해합 : https://www.acmicpc.net/problem/2231 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 2798번 - 블랙잭 : https://www.acmicpc.net/problem/2798 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 16967번 : https://www.acmicpc.net/problem/16967 문제 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다. 즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다. (i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다. (i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다...