✒️ 정보시스템기술

1. 학습개요

• 컴퓨터를 사용하여 산업공학 분야에서 발생하는 다양한 문제를 해결해 봅니다. 이러한 문제에는 배낭 문제, 외판원 문제, 바이너리 패킹, 최단 경로, 스케쥴링 등이 포함됩니다.
• 컴퓨터를 효과적으로 사용하기 위해 Python을 통해 객체지향 프로그래밍 패러다임, 데이터 구조 및 여러 알고리즘을 배웁니다.

2. 수강목표

• Understand growth rate of algorithms using the Big-Oh notation
• Understand the notion of NP-completeness
• Understand how recursion can be used to design algorithms
• Understand the principles and usage application of basic data structures, such as arrays, stack, queues and lists.
• Understand the principles and usage applications of advanced data structures, such as trees and hash tables
• Understand and apply typical sorting and searching algorithms
• Understand graphs, graph traversal and paths within graphs
• Implement basic and advanced data structures in Python
• Implement the algorithms covered by this course in Python
• Design and evaluate efficient algorithms in Python to solve specific applied problems

현실적으로 3학점 짜리 수업에서 전부 깊게 다루긴 힘들것 같지만.. 그래도 학부 마지막 수업에서 많은 것을 얻어 갈수 있을거라 기대합니다.

📕 Word Count 함수

---

# 제외목록 파일을 읽어 분석에 제외할 단어들의 배열을 반환합니다.
def read_no_meaning_words(Filename):
    temp_no_meaning_words = []
    f = open(Filename, "r", encoding="UTF8")
    word_lines = f.readlines()
    for line in word_lines:
        new_line = line.strip()
        temp_no_meaning_words.append(new_line)
    f.close()
    return temp_no_meaning_words

# 분석할 파일을 읽습니다.
# 모든 문자를 소문자로 바꾸고, ".",","와 같은 기호를 빼는 전처리를 해줍니다.
def read_address_file(Filename, no_meaning_words):

    word_counts = {}

    f = open(Filename, "r", encoding="UTF8")
    lines = f.readlines()
    for line in lines:
        words = line.split()

        for word in words:
            word = word.strip().strip('.,').lower()

            if word not in no_meaning_words:

                if word in word_counts:
                    word_counts[word] += 1
                else:
                    word_counts[word] = 1

    word_list = list(word_counts.keys())
    word_count = list(word_counts.values())

    f.close()
    return word_list, word_count

# Bubble Sort를 이용해서 Count별로 오름차순으로 단어를 정렬합니다.
def words_sort(word_list, word_count):       
    num = len(word_list)

    for i in range(num-1):
        for j in range(0, num-i-1):

            if word_count[j] < word_count[j+1]:

                word_list[j], word_list[j+1] = word_list[j+1], word_list[j]
                word_count[j], word_count[j+1] = word_count[j+1], word_count[j]

# 넘겨 받은 단어에서 대칭인 모든 substirng들을 반환
def palindrome_finder(word):
    temp_string = ""

    for i in range(len(word)):
        for j in range(i + 1, len(word) + 1):
            substring = word[i:j]
            if substring == substring[::-1] and len(substring) > len(temp_string):
                temp_string = substring
    return temp_string

# 리턴받은 palindrome substring 중 길이가 제일 긴 단어를 찾는 함수
def find_longest_palindrome(word_list):
    the_longest = ""
    for i in word_list:
        temp = palindrome_finder(i)
        
        if len(the_longest) < len(temp):
            the_longest = temp
    return the_longest

✒️함수설명

---

함수명	의미
read_no_meaning_words(Filename)	파일에서 제외할 단어 리스트를 가져옵니다.
read_address_file(Filename, no_meaning_words)	파일에서 단어 리스트와 빈도수를 배열에 담아 반환합니다.
words_sort(word_list, word_count)	Bubble Sort 알고리즘을 이용해 단어 리스트를 빈도수에 따라 내림차순으로 정렬합니다.
palindrome_finder(word)	word의 substring중 가장 길아가 긴 palindrome을 찾아 리턴 합니다.
find_longest_palindrome(word_list)	palindrome_finder 함수가 리턴한 palindrome 중 가장 길이가 긴 단어를 찾아서 리턴합니다.

• Bubble Sort: 왼쪽의 숫자가 오른쪽 숫자 보다 작으면 스왑하는 방식의 Sorting Algorithms
• Palindrome: 좌우가 대칭인 단어, python의 경우 str[::-1]로 쉽게 비교할 수 있습니다.

📕 Main 함수

---

if __name__ == "__main__":
    no_meaning_words = read_no_meaning_words("address_no_meaning_words.txt")
    print(no_meaning_words)
    
    word_list, word_count = read_address_file("address.txt", no_meaning_words)
    print(word_list)
    print(word_count)

    wanted_num = int(input("사용 빈도가 많은 단어 순으로 print하려고 합니다. 원하는 단어의 수를 입력하세요: "))
    words_sort(word_list, word_count)
    min_num = min(wanted_num, len(word_list))
    for i in range(min_num):
        print(word_list[i], ": ", word_count[i])

    the_longest = find_longest_palindrome(word_list)
    print("The longest palindrome:", the_longest)

    print("Success!")

---

✒️실행결과

---

🐱 Martin Luther King의 명연설 “I have a dream”의 원문을 분석하였습니다.

1. No Meaning Words

['the', 'of', 'to', 'and', 'a', 'be', 'will', 'that', 'is', 'as', 'in', 'we', 'have', 'from', 'not', 'this', 'for', 'are', '']

• 미리 정해진 단어 리스트를 파일에서 읽습니다. the,**of**,**are**,**is** 와 같이 영어 문장에 항상 자주 사용 되는 단어들은 분석대상에서 제외하였습니다

2. Word List, Word Count

['Five', 'score', 'years', 'ago', 'great', 'American', 'whose', 'symbolic', 'shadow', 'stand', 'today', 'signed', 'Emancipation', 'Proclamation', 'This', 'momentous', 'decree', 'came', 'beacon', 'light', 'hope', 'millions', 'Negro', 'slaves', 'who', 'had', 'been', 'seared', 'flames', 'withering', 'injustice', 'It', 'joyous', 'daybreak', 'end', 'long', 'night', 'their', 'captivity', 'But', '100', 'later', 'still', 'free', 'One', 'hundred', 'life', 'sadly', 'crippled', 'by', 'manacles', 'segregation', 'chains', 'discrimination', 'lives', 'on', 'lonely', 'island', 'poverty', 'midst', 'vast', 'ocean', 'material', 'prosperity', 'languished', 'corners', 'society', 'finds', 'himself', 'exile', 'his', 'own', 'land', 'And', 'so', "we've", 'come', 'here', 'dramatize', 'shameful', 'condition', 'In', 'sense', 'our', "nation's", 'capital', 'cash', 'check', 'When', 'architects', 'republic', 'wrote', 'magnificent', 'words', 'Constitution', 'Declaration', 'Independence', 'they', 'were', 'signing', 'promissory', 'note', 'which', 'every', 'was', 'fall', 'heir', 'promise', 'all', 'men', '—', 'yes', 'Black', 'well', 'white', 'would', 'guaranteed', 'unalienable', 'rights', 'liberty', 'pursuit', 'happiness', 'obvious', 'America', 'has', 'defaulted', 'insofar', 'her', 'citizens', 'color', 'concerned', 'Instead', 'honoring', 'sacred', 'obligation', 'given', 'people', 'bad', 'back', 'marked', 'insufficient', 'funds', 'refuse', 'believe', 'bank', 'justice', 'bankrupt', 'We', 'there', 'vaults', 'opportunity', 'nation', 'give', 'us', 'upon', 'demand', 'riches', 'freedom', 'security', 'also', 'hallowed', 'spot', 'remind', 'fierce', 'urgency', 'now', 'no', 'time', 'engage', 'luxury', 'cooling', 'off', 'or', 'take', 'tranquilizing', 'drug', 'gradualism', 'Now', 'make', 'real', 'promises', 'democracy', 'rise', 'dark', 'desolate', 'valley', 'sunlit', 'path', 'racial', 'lift', 'quick', 'sands', 'solid', 'rock', 'brotherhood', 'reality', "God's", 'children', 'fatal', 'overlook', 'moment', 'sweltering', 'summer', "Negro's", 'legitimate', 'discontent', 'pass', 'until', 'an', 'invigorating', 'autumn', 'equality', '1963', 'but', 'beginning', 'Those', 'needed', 'blow', 'steam', 'content', 'rude', 'awakening', 'if', 'returns', 'business', 'usual', 'There', 'neither', 'rest', 'nor', 'tranquility', 'granted', 'citizenship', 'The', 'whirlwinds', 'revolt', 'continue', 'shake', 'foundations', 'bright', 'day', 'emerges', 'something', 'I', 'must', 'say', 'my', 'warm', 'threshold', 'leads', 'into', 'palace', 'process', 'gaining', 'rightful', 'place', 'guilty', 'wrongful', 'deeds', 'Let', 'seek', 'satisfy', 'thirst', 'drinking', 'cup', 'bitterness', 'hatred', 'forever', 'conduct', 'struggle', 'high', 'plane', 'dignity', 'discipline', 'allow', 'creative', 'protest', 'degenerate', 'physical', 'violence', 'Again', 'again', 'majestic', 'heights', 'meeting', 'force', 'with', 'soul', 'marvelous', 'new', 'militancy', 'engulfed', 'community', 'lead', 'distrust', 'many', 'brothers', 'evidenced', 'presence', 'realize', 'destiny', 'tied', 'up', 'inextricably', 'bound', 'cannot', 'walk', 'alone', 'pledge', 'shall', 'always', 'march', 'ahead', 'turn', 'those', 'asking', 'devotees', 'civil', 'when', 'you', 'satisfied?', 'can', 'never', 'satisfied', 'victim', 'unspeakable', 'horrors', 'police', 'brutality', 'bodies', 'heavy', 'fatigue', 'travel', 'gain', 'lodging', 'motels', 'highways', 'hotels', 'cities', 'basic', 'mobility', 'smaller', 'ghetto', 'larger', 'one', 'stripped', 'selfhood', 'robbed', 'signs', 'stating:', 'whites', 'only', 'Mississippi', 'vote', 'New', 'York', 'believes', 'he', 'nothing', 'No', 'rolls', 'down', 'like', 'waters', 'righteousness', 'mighty', 'stream', 'am', 'unmindful', 'some', 'out', 'trials', 'tribulations', 'Some', 'fresh', 'narrow', 'jail', 'cells', 'areas', 'where', 'your', 'quest', 'left', 'battered', 'storms', 'persecution', 'staggered', 'winds', 'You', 'veterans', 'suffering', 'Continue', 'work', 'faith', 'unearned', 'redemptive', 'Go', 'go', 'Alabama', 'South', 'Carolina', 'Georgia', 'Louisiana', 'slums', 'ghettos', 'Northern', 'knowing', 'somehow', 'situation', 'changed', 'wallow', 'despair', 'friends', 'So', 'even', 'though', 'face', 'difficulties', 'tomorrow', 'dream', 'deeply', 'rooted', 'live', 'true', 'meaning', 'its', 'creed:', 'hold', 'these', 'truths', 'self-evident', 'created', 'equal', 'People', 'clap', 'sing', 'along', 'song', 'between', 'speeches', 'at', 'March', 'Washington', 'Jobs', 'Freedom', 'red', 'hills', 'sons', 'former', 'slave', 'owners', 'able', 'sit', 'together', 'table', 'state', 'heat', 'oppression', 'transformed', 'oasis', 'four', 'little', 'judged', 'skin', 'character', 'vicious', 'racists', 'governor', 'having', 'lips', 'dripping', 'interposition', 'nullification', 'right', 'boys', 'girls', 'join', 'hands', 'sisters', 'exalted', 'hill', 'mountain', 'made', 'low', 'rough', 'places', 'plain', 'crooked', 'straight', 'glory', 'Lord', 'revealed', 'flesh', 'see', 'it', 'With', 'hew', 'stone', 'transform', 'jangling', 'discords', 'beautiful', 'symphony', 'pray', 'meaning:', 'My', 'country', "'tis", 'thee', 'sweet', 'Land', 'fathers', 'died', "pilgrims'", 'pride', 'mountainside', 'let', 'ring', 'become', 'prodigious', 'hilltops', 'Hampshire', 'mountains', 'heightening', 'Alleghenies', 'Pennsylvania', 'snowcapped', 'Rockies', 'Colorado', 'curvaceous', 'slopes', 'California', 'Stone', 'Mountain', 'Lookout', 'Tennessee', 'molehill', 'From', 'happens', 'village', 'hamlet', 'city', 'speed', 'Jews', 'Gentiles', 'Protestants', 'Catholics', 'old', 'spiritual:', 'Free', 'last', 'Thank', 'God', 'almighty']
[1, 1, 5, 1, 5, 4, 1, 1, 1, 3, 8, 1, 1, 1, 7, 1, 1, 2, 1, 1, 4, 1, 13, 2, 4, 1, 2, 1, 1, 1, 3, 4, 1, 1, 2, 6, 1, 8, 1, 4, 1, 4, 4, 3, 3, 3, 2, 1, 1, 8, 1, 2, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 3, 7, 3, 3, 10, 3, 1, 1, 1, 2, 1, 16, 1, 1, 2, 5, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 2, 3, 5, 10, 2, 1, 1, 1, 7, 6, 2, 1, 4, 1, 6, 2, 1, 1, 3, 2, 1, 1, 1, 5, 5, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 3, 1, 9, 1, 2, 2, 2, 2, 1, 8, 1, 12, 3, 1, 1, 9, 1, 4, 1, 1, 1, 20, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5, 1, 1, 1, 2, 1, 1, 1, 1, 1, 4, 3, 1, 1, 1, 3, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 3, 5, 1, 1, 1, 3, 1, 2, 1, 1, 1, 4, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 11, 1, 1, 14, 8, 2, 4, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 12, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 4, 1, 1, 6, 2, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 1, 4, 3, 7, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 2, 4, 2, 3, 2, 1, 1, 1, 1, 1, 4, 2, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 5, 1, 1, 1, 7, 3, 2, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 11, 1, 1, 2, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 8, 1, 7, 1, 3, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 5, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1]

• Word와 Count를 각각 배열에 담았습니다.
• Word,Count를 Key-Value로 설정하여 Object에 담는 것도 좋은 방법입니다.

3. Sorting Words

사용 빈도가 많은 단어 순으로 print하려고 합니다. 원하는 단어의 수를 입력하세요: 10

freedom :  20
our :  16
I :  14
Negro :  13
We :  12
with :  12
ring :  12
day :  11
dream :  11
come :  10

• 사용 빈도가 많은 순으로 상위 10개의 단어를 출력하였습니다.
• 역시 흑인 인권을 위한 연설 답게 freedom을 가장 많이 말했습니다.

4. Palindrome 찾기

The longest palindrome: ississi

• Mississipi의 ississi가 연설문에서 가장 긴 palindrome이라고 합니다.
• 엄밀히 따지면 단어 자체가 대칭이어야 palindrome 인데, 이번 연설에 palindrome인 단어가 없어서 substring도 같이 분석하였습니다.