본문 바로가기

파이썬

(17)
알고리즘 정리 <이진 탐색> 이진 탐색 알고리즘이란 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 먼저 이진 탐색을 배우기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 알아보겠다. 1. 순차 탐색 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 데이터 예시) 순차 탐색으로 "dongbin"을 찾는 과정 list = ["haneul", "jonggu", "dongbin", "taeil", "sangwook"] 1) 가장 먼저 첫 번째 데이터를 확인한다. -> "haneul"은 찾는 데이터가 ..
이코테 Chapter 05 정렬 - 두 배열의 원소 교체 문제 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다 N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라 예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자 배열 A = [1, 2, 5, 4, 3] 배열 B..
이코테 Chapter 05 정렬 - 성적이 낮은 순서로 학생 출력하기 문제 N명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다. 입력 첫 번째 줄에 학생의 수 N이 입력된다. (1
이코테 Chapter 05 정렬 - 위에서 아래로 문제 하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다. 입력 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1
알고리즘 정리 <정렬> 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램을 작성할 때 보통 오름차순, 내림차순 등 어떤 방식으로든 정렬해서 사용하는 경우가 많다. 일반적인 코딩 테스트 문제에서는 요구하는 조건에 따라서 적절한 정렬 알고리즘이 사용되어야 한다. 상황에 적절하지 못한 정렬 알고리즘을 이용하면 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소모한다. 정렬 알고리즘에는 대표적으로 [선택 정렬, 삽입 정렬, 퀵 정렬]이 있다. 1. 선택 정렬 쉽게말해 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것. 이 방법은 가장 원시적인 방법으로 매번 ..
이코테 Chapter 04 구현 - 왕실의 나이트 문제 행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 × 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a 부터 h로 표현한다 c2에 있을 때 ..
이코테 Chapter 04 구현 - 시각 문제 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다 00시 02분 55초 01시 27분 45초 접근법 & 풀이 1. for문을 이용해서 시, 분, 초에 3이있으면 count + 1해주면되지않을까.. 소스코드 n = int(input()) count = 0 for hour in range(n+1): for min in range(60): for second in range(60): if '3' ..
이코테 Chapter 04 구현 - 상하좌우 접근법 (생각의 회로) 1. n을 입력받음 2. 계획서 내용을 리스트로 입력받음 3. 리스트를 for문으로 돌려 조건문을 통해 L이면 y좌표 -1, R이면 +1, U이면 x좌표 -1, D이면 +1 4. 출력 소스코드 n = int(input()) x, y = 1, 1 route = input().split() # for문을 통해 여행계획서에 따른 위치 바꿈 for i in route: if i == 'L' and y > 1: # 'L'인 경우 y값이 1보다 커야함 y -= 1 elif i == 'R' and y 1: # 'U'인경우 x값이 1보다 커야함 x -= 1 elif i == 'D' and x <..