[이코테] 문제2 - 떡볶이 떡 만들기(201p) (한줄평) 탐색 범위를 보고 이진 탐색으로 풀어야함을 알아야 풀 수 있는 문제로 해결은 했지만 복습이 필요한 문제! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 적절한 절단기 높이를 찾을 때까지 이진 탐색을 수행하여 높이 h를 반복해서 조정하면 된다. "현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 뒤 조건의 만족 여부(예/아니오)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 절단기의 높이는 0이상 10억이하의 정수인데 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다!! 그렇지 않으면 시간초과가 날 것이다! 여기서 기억할 점은 절단기의 높이가 커질 수록 잘린 떡의 길이의 총합이 작아진다는 점이다. 1. 시작점: 0, ..
[이코테] 문제1 - 부품 찾기(197p) (한줄평) 집합을 이용하여 쉽게 풀 수 있었던 문제! 하지만 다른 풀이 방법으로도 풀어보는 것을 추천! 이 문제는 부품 목록 n개, 손님이 구매를 원하는 부품 m개가 있을 때, 손님이 요쳥한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력하는 문제다. 이진 탐색, 집합, 계수 정렬 3가지 방법으로 모두 효과적으로 풀 수 있는 문제다. (풀이1) 집합(set)을 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 단순히 특정 수가 있는지 여부를 검사하면 되기 때문에 부품목록(graph)를 집합으로 선언한다. Q. 리스트가 아닌 집합으로 선언한 이유는? 집합에서 in 연산의 시간복잡도가 O(1)이고 리스트에서 in 연산의 시간복잡도는..
[이코테] 예제2 - 값이 특정 범위에 속하는 데이터 개수 구하기 (한줄평) bisect 라이브러리 사용법을 익힐 수 있는 기초 문제! 사용하지 않으면 잊어버릴 듯 하니 추후 복습 필요! 풀이 시간: 10분 이내 1) 문제 해결 아이디어 오름차순 정렬되어있는 리스트(a)에서 특정 범위(left_value ~ right_value)에 속하는 데이터 개수를 구하는 문제다. bisect는 정렬된 배열에서 특정 원소를 찾을 때 사용한다. bisect_left(a, x) 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스 리턴 bisect_right(a, x) 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스 리턴 [참고] https://velog.io/@woo0..
[이코테] 예제1 - 이진 탐색 (한줄평) 이진 탐색 기초 문제로 재귀, 반복문 구현 방식 둘다 풀어보면 좋은 문제! 이 문제는 n개의 숫자에서 찾으려고 하는 값(target)이 있으면 해당 인덱스를 출력하는 문제다. (풀이1) 재귀 함수로 구현 풀이 시간: 15분 이내 1) 문제 해결 아이디어 1. 타겟을 찾으면 인덱스를 리턴한다. 2. 타겟이 중간점 값보다 작으면 왼쪽 부분에 대해 이진 탐색 수행을 위해 끝점을 (mid - 1)로 넘겨 binary_search()를 리턴한다. 3. 타겟이 중간점 값보다 크면 오른쪽 부분에 대해 이진 탐색 수행을 위해 시작점을 (mid + 1)로 넘겨 binary_search()를 리턴한다. 2, 3번에서 binary_search()를 그냥 호출하는 것이 아니라 bin..
[이코테] 문제3 - 두 배열의 원소 교체(182p) (한줄평) 정렬만 할 줄 안다면 쉽게 해결할 수 있는 문제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 배열의 크기: n, swap 가능 횟수: k 라고 주어졌을 떄 A, B 2가지 배열의 원소를 각각 하나씩 swap하여 만들 수 있는 A의 원소 합의 최댓값을 구하는 문제다. A, B의 원소를 서로 바꿔 A의 원소 합이 최댓값이 되게 하려면 단순하게 A의 작은 수와 B의 큰수를 바꾸는 것을 최대 K번 반복하면 된다. 그러므로 A는 오름차순 정렬, B는 내림차순 정렬하여 0번부터 (k - 1)번 까지 값을 swap하면 된다. 여기서 중요 포인트는 A, B를 각각 정렬 해야함을 떠올리는 것이다. 단, A의 원소가 B의 원소보다 크거나 같으면 굳이 바..
[이코테] 문제2 - 성적인 낮은 순서로 학생 출력하기(180p) (한줄평) 파이썬 기본 정렬 라이브러리를 이용하면 쉽게 풀 수 있었던 기본 문제! (풀이1) 기본 정렬 라이브러리 사용 풀이 시간: 3분 이내 1) 문제 해결 아이디어 sort()의 key에 정렬 기준을 명시하면 정렬 기준대로 정렬을 할 수 있다. 2) 소스코드 n = int(input()) # 학생 수 arr = [input().split() for _ in range(n)] # n명의 학생정보 # 성적을 기준으로 오름차순 정렬 arr.sort(key=lambda x: x[1]) for student in arr: print(student[0], end= " ") # 이름 출력 (풀이2) 계수 정렬 풀이 시간: 15분 이내 1) 문제 해..
[이코테] 문제1 - 위에서 아래로(178p) (한줄평) 정렬 알고리즘 예제 문제 수준으로 여러가지 정렬 알고리즘을 연습해볼 수 있는 문제! 퀵 정렬만 조금 더 연습해보면 좋을 듯! 이 문제는 n개의 수가 주어지고 내림차순 정렬을 하는 문제다. 수의 개수가 500개 이하로 매우 적고 모든 수는 1이상 100,000이하로 어떠한 정렬 알고리즘을 사용해도 해결할 수 있다. (풀이1) 파이썬 기본 정렬 라이브러리 이용 풀이 시간: 3분 이내 1) 문제 해결 아이디어 가장 단순한 방법으로 sorted()를 이용하여 해결하였다. 2) 소스코드 n = int(input()) arr = [int(input()) for _ in range(n)] # n개의 수 # 1. 정렬 라이브러리(내림차순) #print(*sort..
[이코테] 문제2 - 미로 탈출(152p) 풀이 시간: 40~45분 이내 1) 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함 1. 종료 조건 설정 항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다. 다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다. 2. 탐색 조건에서 시작점 제외 상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다. 책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다. 1. 시작..
