Algorithms, Data Analytics

기본 탐색 알고리즘

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

해설을 듣기전에 먼저 풀어봤다.

data = input()
find = input()
i = 0
count = 0

while len(data) >= i + len(find):
    
    if (data[i:i + len(find)] == find):
        i += len(find)
        count += 1
        
    else:
        i += 1
        
print(count)

거의 똑같아서 놀랐다.

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

이 정렬을 병합정렬, 퀵정렬을 재귀를 이용하여 풀어봤다.

먼저 병합 정렬

def merge_sort(array):
    
    if len(array) <= 1:
        return array
    
    medium = int(len(array) / 2)
    left = merge_sort(array[:medium])
    right = merge_sort(array[medium:])
    
    lp = 0
    rp = 0
    res = []
    
    while (len(left) > lp and len(right) > rp):
        
        if (left[lp] < right[rp]):
            res.append(left[lp])
            lp += 1

        else:
            res.append(right[rp])
            rp += 1
        
    while (len(left) > lp):
        res.append(left[lp])
        lp += 1
        
    while (len(right) > rp):
        res.append(right[rp])
        rp += 1
                
                
    return res

다음 퀵 정렬

import sys

def quick_sort(array):

    if len(array) <= 1:
        return array

    pivot = array[0]
    left = []
    right = []

    for i in range(1, len(array)):

        if pivot > array[i]:
            left.append(array[i])

        else:
            right.append(array[i])

    return quick_sort(left) + [pivot] + quick_sort(right)

test_case = int(sys.stdin.readline())
num_list = []

for _ in range(test_case):
    num_list.append(int(sys.stdin.readline()))

quick_sort(num_list)

sys.stdin.readline()도 input()과 같은 역할인데, 많은 양의 데이터를 받아야 할 때는 저게 더 빠르다고 한다.

Jupyter Notebook에서는 사용이 불가한듯..

하지만 문제를 풀 때는 array = sorted(array)로 더 빨리 정렬할 수 있다.

문제 난이도 : 중

문제 유형 : 해시, 집합, 그래프

추천 풀이 시간 : 50분

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

test_case = int(input())

for __ in range(test_case):
    
    rela = int(input())
    
    fri_list = []

    res = set()

    for _ in range(rela):

        names = list(map(str, input().split()))
        
        if len(res) <= 0:
            for name in names:
                res.add(name)


        elif (names[0] or names[1]) in res:

            res.add(names[0])
            res.add(names[1])

            if fri_list:

                for fri in fri_list:

                    if (fri[0] or fri[1]) in res:
                        res.add(fri[0])
                        res.add(fri[1])

        else:
            fri_list.append(names)
                    
        print(len(res))

내가 먼저 풀어본 코드이다.

시간 초과가 나왔지만 일단 예시 입력을 통과하긴 했다.

설명을 들었지만 잘 모르겠어서 이건 일단 통과..