좌충우돌 IT이야기

[설명]

이진 탐색은 찾고자하는 값을 중앙값을 기준으로 찾는 알고리즘입니다. 해당 알고리즘을 사용하려면 중요한 선행작업 필요합니다.

바로 순차정렬입니다. 찾고자하는 값이 x가 중앙값 보다 작다면 왼쪽을 탐색, 크다면 오른쪽을 탐색하기 때문입니다. 그러므로 이때 정렬이 되어 있지 않다면 우리가 원하는 값이 아닌 다른 값이 나오게 될것입니다.

만약 x = 3 이라면, 먼저 정렬된 배열의 중앙값을 찾습니다. 그 후 찾고자 하는 값은 2이므로 왼쪽을 탐색합니다.

2를 찾아왔지만, 원하는 값은 2보다 크므로 오른쪽을 탐색합니다.

[파이썬 코드]

a = [7, 8, 9, 1, 2, 3, 4, 5, 6]
a.sort(reverse=False)
low = 0
high = len(a)-1
while low <= high:
    p = (high + low) // 2
    if a[p] == k:
        print(p+1)
        break
    elif a[p] < k:
        low = p + 1
    else:
        high = p - 1

(주의) 정답은 올바르게 잘 나오는데 시간초과가 발생합니다. 추후 수정하겠습니다!

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

정답

import sys
sys.stdin = open('input.txt', 'rt')
n, m = map(int, input().split())
a = list(map(int, input().split()))
current = 0
cnt = 0
for i in range(len(a)):
    if a[i] == m:
        cnt += 1
    else:
        current = a[i]
        for j in range(i+1, len(a)):
            current += a[j]
            if current == m:
                cnt += 1
                break
            elif current > m:
                break
                
print(cnt)

문제

1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓여있다. 각 카드의 위치는 카드 위에 적힌 숫자와 같이 1부터 20까지로 나타낸다. 

이제 여러분은 다음과 같은 규칙으로 카드의 위치를 바꾼다: 구간 [a, b] (단, 1 ≤ a ≤ b ≤ 20)가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다.

예를 들어, 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [5, 10]으로 주어진다면, 위치 5부터 위치 10까지의 카드 5, 6, 7, 8, 9, 10을 역순으로 하여 10, 9, 8, 7, 6, 5로 놓는다. 이제 전체 카드가 놓인 순서는 아래 그림과 같다.

이 상태에서 구간 [9, 13]이 다시 주어진다면, 위치 9부터 위치 13까지의 카드 6, 5, 11, 12, 13을 역순으로 하여 13, 12, 11, 5, 6으로 놓는다. 이제 전체 카드가 놓인 순서는 아래 그림과 같다.

오름차순으로 한 줄로 놓여있는 20장의 카드에 대해 10개의 구간이 주어지면, 주어진 구간의 순서대로 위의 규칙에 따라 순서를 뒤집는 작업을 연속해서 처리한 뒤 마지막 카드들의 배치를 구하는 프로그램을 작성하시오.

정답

import sys
sys.stdin = open('input.txt', 'rt')
num = list(range(1, 21))

for i in range(10):
    n, k = map(int, input().split())

    n = n-1
    k = k-1
    y = ((n + k) // 2)+1
    for j in range(n, y):
        tmp = num[j]
        #print('tmp = ', tmp, end=' ')

        num[j] = num[k]
        #print('num[i] = ', num[i], end=' ')

        num[k] = tmp
        #print('num[k] = ', num[k])
        k -= 1
    #print(n+1, k+1,')',i,'번째', num)


for x in num:
    print(x, end=' ')

'문자열 회물을 확인한다 '란 문자열이 앞으로 읽으나, 뒤로 읽으나 같은 것인지 확인하는 것입니다.

예를 들어 AbbA, LeveL, LooL 등 과 같은 단어입니다.

자료구조 수업 때 배웠던 기억이 있어서 비교적 쉽게 구현했지만, 보다 파이썬스러운 방법이 있기에 기록합니다.

학부 수업때 배운 방법을 바탕으로 작성한 방법입니다.

import sys
sys.stdin=open("input.txt", "r")
n = int(input())
check = 0
for i in range(n):
    s = input()
    s = s.upper()
    
    for j in range(len(s)//2):
        if s[j] != s[-1-j] :
            check += 1
    if check == 0:
        print('#%d YES' %(i+1))
        check = 0
    else:
        print('#%d NO' %(i+1))
        check = 0

파이썬스럽게 간랸한 방법으로 작성한 코드입니다.

import sys
sys.stdin=open("input.txt", "r")
n = int(input())
check = 0
for i in range(n):
    s = input()
    s = s.upper()
    
    if s==s[::-1]:
        print('#%d YES' %(i+1))
    else:
        print('#%d NO' %(i+1))