TIL 7일차: 자료구조와 알고리즘, 자바스크립트 올인원

오늘은 대망의 자료구조, 알고리즘을 시작한 날이다.

처음에는 그럭저럭 할만 했는데 가면 갈수록 알고리즘 아이디어 떠올리기가 쉽지 않았다.

 

1. 알고리즘이란 어떤 문제가 있을 때 그것을 해결하기 위한 여러 동작들의 모임이다.

 

2. 최빈값 중 알파벳 별 빈도수 찾기

1) 알파벳별 빈도수를 찾기 위해 alphabet_occurrence_array = [0]*26을 미리 설정해 주기

2) 아스키 코드로 숫자-문자값 변환하기

3) alphabet_occurrency_array[arr_index] +=1 배열에 인덱스값 넣고 하나씩 더해주기

 

3. 최빈값 중 가장 빈번하게 등장한 알파벳 찾기에서 첫 시작은

1) 각 알파벳들을 하나하나 문자열과 비교하면서 몇 번 나왔는지 검사하는 것

또는

2) 각 알파벳의 빈도수를 alphabet_occurrence_list 라는 변수에 저장하고

각 문자열을 돌면서 해당 문자가 알파벳인지 확인하는 것이다.

 

여기서 내가 놓친 것은 알파벳을 인덱스화시켜 알파벳 빈도수를 업데이트 하는 것.

for index in range(len(alphabet_occurrence_array)): ...

 

그 후 알파벳의 빈도수가 가장 높은 인덱스를 문자로 찾아야 하는데, 이 때 아스키 코드를 다시 한 번 이용한다.

 

4. 시간 복잡도와 공간 복잡도, 점근 표기법

시간 복잡도란 입력값과 문제를 해결하는 데 걸리는 시간의 상관관계이다. 공간 복잡도는 공간과의 상관관계.

입력값이란 함수에서 크기가 변경될 수 있는 값을 말하며, 공간보다 시간복잡도가 더 중요하다.

점근표기법은 알고리즘의 성능을 수학적으로 표기하는 방법으로, 주로 쓰는 것은 최악의 성능을 고려하는 빅오 표기법.

 

5. 연습문제: 곱하기 or 더하기

1이나 0일 때는 더하기, 나머지는 곱하기.

첫번째 숫자가 1보다 작거나 같을 땐 더해줘야 한다.

 

연습문제: 반복되지 않은 문자

해당 문자가 몇 번 나왔는지 배열에 저장해야 한다. 알파벳 빈도수 센 것과 비슷하다.

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_character_array:
            return char

 

연습문제: 소수 나열하기: 소수의 특징을 살려 개선할 수 있는 방법을 생각하자.

 

연습문제: 문자열 뒤집기

1에서 0 또는 0에서 1로 바뀌는 순간을 캐치할 수 있는 변수를 지정해 더해주기, 첫번째 문자 확인하기.

얘는 30분 걸려도 못풀어서 답을 봤다. 뜨악 못풀만 했다...

input = "011110"

// 0에서 1로, 1에서 0으로 변하는 순간에 주목해야 한다.
// 전체를 0으로 또는 1로 만들기 위한 숫자를 계산하기.

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0
    count_to_all_one = 0 

// 첫번째 원소가 0인지, 1인지를 파악해야 한다.
    if string[0] == "0":
        count_to_all_one += 1
    elif string[0] == "1":
        count_to_all_zero += 1

// 그 다음으로 오는 숫자와 비교하기
    for i in range(len(string) - 1):
        if string[i] != string[i + 1]:
            if string[i + 1] == "0":
                count_to_all_one += 1
            if string[i + 1] == "1":
                count_to_all_zero += 1
    return min(count_to_all_zero, count_to_all_one)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

 

후에 튜터님이 방문하셔서 pseudo code를 자연어로 짜면서 알고리즘 틀을 구성하는 방법을 알려주셨다.

이건 자바 배우면서 미친듯이 연습했던 거라 생각보다 쉽게 나왔다. 하지만 풀이 경험 없는 알고리즘에서는 턱턱 막힌다.

연습 뺑뺑이 돌리다보면 깨닫는 바가 있겠지.

 

이후에 자바스크립트 기초를 다졌다.

새로 익힌 것들은 객체, 클래스, 생성자, this, 객체만들기 new, 메소드, 배열.

오늘 배운 사소한 기능은... 블록 주석 단축키 shift+alt+A다. 이제 자자!