Algorithm

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 다이나믹 프로그래밍(Dynamic Programing), 동적 계획법 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 다이나믹 프로그래밍과 동적 할당의 다이나믹 프로그램에서 다이나믹은 "프로그램이 실행되는 도중에" 라는 의미이다. 예를 들어 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다. 그러나, 다이나믹 프로그래밍에서의 '다이나믹'은 다른 의미이다. 피보나치 수열 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 수학에서는 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현한다. 점화식..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 떡볶이 떡의 길이는 일정하지 않아서 한 봉지 안에 들어가는 떡의 총길이를 절단기로 잘라서 맞춘다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위 부분이 잘리고, 낮은 떡은 잘리지 않는다. 모든 떡의 잘린 길이만큼 떡을 가져간다. 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라. 입력 조건 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 전자 매장에 부품 N개가 있다. 각 부품은 정수 형태의 고유한 번호를 가진다. 손님이 M개 종류의 부품 구매할 때 매장에 부품이 모두 있는지 확인하라. 입력 조건 첫째 줄에 정수 N이 주어진다. (1

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 이진탐색 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 순차 탐색(Sequential Search) 가장 기본 탐색 방법 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다. 리스트에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다. 첫 번째 데이터를 확인한다. 찾고자 하는 문자열과 같지 않다면 다음 데이터로 이동하고. 찾고자 하는 문자열과 같다면 탐색을 종료한다. 순차탐색 소스코드 # n 원소의 개수 # target 찾을 문자열 # array 문자열 배열 def sequent..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 두 배열 A, B는 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. N, K 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하라. 입력 조건 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 N명의 학생 정보가 있고, 학생 정보는 학생의 이름과 성적으로 구분된다. 학생 정보가 주어졌을 때, 성적이 낮은 순서대로 학생의 이름을 출력하라. 입력 조건 첫 번째 줄부터 학생의 수 N이 입력된다. (1

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 수열을 내림차순으로 정렬하는 프로그램을 만드시오 입력 조건 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 정렬(Sorting) 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 즉, 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 정렬 알고리즘에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있고, 파이썬에서 제공하는 기본 정렬 라이브러리를 이용할 수도 있다. 아래의 예제는 모두 오름차순 정렬을 수행하고, 내림차순 정렬은 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행하면 된다. 파이썬에서는 리스트의 원소를 뒤집는 메서드를 제공하기 때문에 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기(Reverse)하여 내림차순 리..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 처음 위치는 (1, 1)이고, 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M(4 = M: continue # 다음 값이 1이고, 이동 횟수가 크면 작은걸로 수정 if maze[ni][nj] == 1 and board[ni][nj] > step+1: board[ni][..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 N X M 크기의 얼음 틀 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하라. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결된 것으로 간주한다. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 = M: continue if board[ni][nj] == '0' and visited[ni][nj] == 0: visited[ni][nj] = 1 check(ni, nj) cnt = 0 for i in range(0, N): for j in range(0, M): # 구멍이 뚫려있고 체크한 적 없으면 if board[i][j] == '0' and ..