📝문제1. 정렬된 배열에서 특정 수의 개수 구하기

- 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)이므로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받습니다.

입력 조건

  • 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 ≤ N ≤ 1,000,000), (-10⁹ ≤ x ≤ 10⁹)
  • 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10⁹ ≤ 각 원소의 값 ≤ 10⁹)

출력 조건

  • 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

입력 예시 1
7 2
1 1 2 2 2 2 3

출력 예시 1
4

입력 예시 2
7 4
1 1 2 2 2 2 3

출력 예시 2
-1

- 나의 코드💻

from sys import stdin
n, x = map(int, stdin.readline().split())
array = list(map(int, stdin.readline().split()))
print(array.count(x))

-> 시간 복잡도를 고려하지 않고 작성함

- 정답 코드💻

  1. 이진 탐색 예시 1
from sys import stdin

# 정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드
def count_by_value(array, x):
    # 데이터의 개수
    n = len(array)

    # x가 처음 등장한 인덱스 계산
    a = first(array, x, 0, n-1)

    # 수열에 x가 존재하지 않는 경우
    if a == None:
        return 0  # 값이 x인 원소의 개수는 0이므로 0 반환

    # x가 마지막으로 등장한 인덱스 계산
    b = last(array, x, 0, n-1)

    # 개수를 반환
    return b - a + 1

# 처음 위치를 찾는 이진 탐색 메서드
def first(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 해당 값을 가지는 원소 중에서 가장 왼쪽에 있는 경우에만 인덱스 반환
    if (mid == 0 or target > array[mid - 1]) and array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작거나 같은 경우 왼쪽 확인
    elif array[mid] >= target:
        return first(array, target, start, mid-1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return first(array, target, mid+1, end)

# 마지막 위치를 찾는 이진 탐색 메서드
def last(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 해당 값을 가지는 원소 중에서 가장 오른쪽에 있는 경우에만 인덱스 반환
    if (mid == n-1 or target < array[mid + 1]) and array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return last(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 크거나 같은 경우 오른쪽 확인
    else:
        return last(array, target, mid + 1, end)

n, x = map(int, stdin.readline().split())
array = list(map(int, stdin.readline().split()))

# 값이 x인 데이터의 개수 계산
count = count_by_value(array, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)
  1. 이진 탐색 예시 2(bisect 이용)
from sys import stdin
from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value] 인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

n, x = map(int, stdin.readline().split())
array = list(map(int, stdin.readline().split()))

# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)

참고 :

- 비교 분석📖

시간 복잡도 O(logN)으로 동작하는 알고리즘을 요구하고 있는 문제이다. 따라서 일반적인 선형 탐색으로는 해결할 수 없다. 다행히 모든 원소가 정렬된 채로 입력되므로 이진 탐색을 이용하여 값이 x인 원소의 개수를 시간 내에 찾아낼 수 있다.

원소들은 모두 정렬되어 있기 때문에, 수열 내에 x가 존재한다면 연속적으로 나열되어 있을 것으로 예상할 수 있다. 따라서 x가 처음 등장하는 인덱스와 x가 마지막으로 등장하는 인덱스를 각각 계산한 뒤에, 그 인덱스의 차이를 계산하여 문제를 해결할 수 있다. 그러므로 이진 탐색 함수를 2개 작성하여 문제를 해결한다.

예를 들어 [1, 1, 2, 2, 2, 2, 3] 으로 7개의 원소를 갖는 정렬된 수열이 있을 때, '2'가 등장하는 첫 위치와 마지막 위치를 찾는 것이다.

하나는 데이터가 존재한다면 가장 첫 번째 위치를 찾는 이진 탐색 함수이며, 다른 하나는 데이터가 존재한다면 가장 마지막 위치를 찾는 이진 탐색 함수이다. 이 2개를 각각 실행한 뒤에 답을 도출할 수 있다. 이러한 방법은 이진 탐색을 요구하는 고난이도 문제에서 자주 사용할 수 있는 테크닉으로, 이 문제에서 사용된 코드를 잘 이해하면 도움이 될 것이다.

-> 아직 이진 탐색 코드는 좀 어려운 것 같다. 그나마 비교적 수월하게 느껴지는 bisect 라이브러리를 잘 이용해봐야겠다.


📝문제2. 고정점 찾기

- 문제

고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2]=2이므로, 고정점은 2가 됩니다.

하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 만약 고정점이 없다면 -1을 출력합니다.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 조건

  • 첫째 줄에 N이 입력됩니다. (1≤N≤1,000,000)
  • 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤각 원소의 값 ≤10^9)

출력 조건

  • 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

입력 예시 1
5
-15 -6 1 3 7
출력 예시 1
3

입력 예시 2
7
-15 -4 2 8 9 13 15
출력 예시 2
2

입력 예시 3
7
-15 -4 3 8 9 13 15
출력 예시 3
-1

- 나의 코드💻

from sys import stdin

n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))


def fixed_dot(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == mid:
        return mid
    elif array[mid] > mid:
        return fixed_dot(array, start, mid - 1)
    else:
        return fixed_dot(array, mid + 1, end)


result = fixed_dot(array, 0, n - 1)
if result == None:
    print(-1)
else:
    print(result)

- 정답 코드💻

from sys import stdin

def fixed_dot(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 고정점을 찾은 경우 인덱스 반환
    if array[mid] == mid:
        return mid
    # 중간점이 가리키는 위치의 값보다 중간점이 작은 경우 왼쪽 확인
    elif array[mid] > mid:
        return fixed_dot(array, start, mid - 1)
    # 중간점이 가리키는 위치의 값보다 중간점이 큰 경우 오른쪽 확인
    else:
        return fixed_dot(array, mid + 1, end)


n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

result = fixed_dot(array, 0, n - 1)
if result == None:
    print(-1)
else:
    print(result)

- 비교 분석📖

이미 배열이 정렬되어 있으므로 바로 이진탐색을 적용할 수 있는 문제이다. 참고로 이진 탐색을 수행할 때는 '찾고자 하는 값'이 '중간점'과 동일하다고 가정하고, 탐색을 수행하면 된다. 그래서 중간점이 가리키는 위치의 값보다 중간점이 작은 경우에는 왼쪽 부분을 탐색하고, 중간점이 가리키는 위치의 값보다 중간점이 큰 경우에는 오른쪽 부분을 탐색하는 것을 반복하면 된다.

-> 월요일 스터디 자료에 있는 기본 이진탐색 코드를 보면서 작성해봤다. 사실 그 과정을 완전히 이해하지는 못했고, 잘 모르겠어서 코드를 비슷한대로 따라쳤다.. 다행히 옳게 작성한 것 같다. 그런데 고정점이 여러개인 경우는 없는건가? 배열을 이용해 고정점이 여러개인 상황을 고려하려고 했는데 그러면 출력할때 for문이 생기는데 괜찮은건가??...


📝문제3. 백준 2352번(반도체 설계)

- 문제

https://www.acmicpc.net/problem/2352

문제
반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

입력
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력
첫째 줄에 최대 연결 개수를 출력한다.

예제 입력
6
4 2 6 3 1 5
예제 출력
3

- 나의 코드💻

from sys import stdin
n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

def design(array, start, end):
    if start > end:
        return None
    mid = (start + end) //2
    if

-> 포기..

- 정답 코드💻

코드를 입력하세요

- 비교 분석📖

lis 문제라고 하는데, 개념이 낯설기도 하고 코드 이해가 잘 가지도 않는다. 마음이 급해져서 그런지 잘 머리에 들어오지 않아 추후 다시 복습하겠다..!

참고 블로그
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=adamdoha&logNo=221622180884


'이것이 코딩 테스트다 with 파이썬(나동빈)' 책을 기반으로 작성한 글입니다.

1개의 댓글

comment-user-thumbnail
2021년 7월 28일

안녕하세요 알고리줌입니다!
저도 3번문제가 안풀혀서 복습시간에 풀어볼려고 합니다ㅎㅎ
오늘 수고 많으셨습니다~

답글 달기
Powered by GraphCDN, the GraphQL CDN