TIL 12일차: 자료구조 알고리즘 실전문제1,2, 타임어택문제, 프로그래머스 스쿨, 자바스크립트 클래스와 객체, 배열

오늘은 늦잠을 자서 아침에 너무 늦게 시작했다.

알고리즘 5주차 실전문제에 들어갔다.

사진 출처: 스파르타 코딩클럽

실전 문제들을 푸는데, 이제까지 배운 자료구조에서 어떤 걸 써먹어야 하는지,

어떤 알고리즘으로 문제에 접근해야 하는지 전혀 감을 잡지 못했다 ㅠㅠ

결국엔 10분정도 고민해보다가 안되어서 바로 해설해주시는 걸 보면서 하나하나 따라갔다.

따라가는 것조차 벅찬... 아직은 많이 배워야한다.

 

일단 선형 구조에서는 배열, 스택, 큐, 링크드리스트를 대표적으로 배웠다.

배열은 규칙적으로 증가/감소되는 자료구조에서 주로 쓰인다는 점에서, 자유자재로 데이터를 저장해야 하는 딕셔너리와 반대된다.

또한 배열은 데이터 접근을 할 때 주로 쓰인다. 이는 링크드리스트가 데이터를 삽입/삭제할 때 쓰이는 것과 반대된다.

스택은 한쪽으로만 데이터를 넣고 뺄 수 있고, 배운 구현 기능은 push, pop, peek등이 있다.

이와 다르게 큐는 데이터를 한 쪽으로 넣고 반대쪽으로 뺄 수 있었고, 구현 기능은 enqueue, dequeue, peek등이 있다.

링크드리스트 배울 땐 append도 함께 배웠다. 특정한 원소 찾을 때, 새로운 원소값을 추가하거나 리스트에 있는 원소를 삭제할 때 링크드리스트를 쓰면 된다.

 

다음으로 비선형구조에서는 그래프와 트리를 배웠다.

그래프는 인접행렬이나 인접리스트로 표현이 되었고,

모든 데이터 값을 봐야 할 때, 보는 순서에 따라 DFS와 BFS가 나뉘었다.

실전에서도 모든 데이터를 확인 해야할 때 DFS와 BFS를 많이 쓴 걸로 봐서 활용 범위가 넓다.

그리고 피보나치 수열처럼 재귀적으로 표현할 수 있는 dynamic programming도 이곳에 끼어 있었다.

다음으로 트리에서는 완전이진트리를 배우면서, 어떤 값의 최댓값/최솟값을 찾을 때 맥스 힙을 이용할 수 있다.

맥스 힙의 원소를 추가하거나 제거하는 것도 가능하다. 활용 범위 넓음.

 

오늘 오후 3시 30분부터 5시 30분부터 진행된 타임어택 문제.

덕분에 프로그래머스 스쿨이라는 유용한 사이트를 알게 되었다.

내게 필요한 것들이 이런 단계가 나눠져있는, 간단한 문제들이었기 때문이다.

https://school.programmers.co.kr/learn/challenges/beginner?order=acceptance_desc&statuses=solved%2Cunlocked&languages=python3

코딩테스트 입문 | 프로그래머스 스쿨

 

물론 타임어택 한다고 시간표에 공지가 되었던터라, 자바스크립트를 짬내서 복습하긴 했다.

복습한 걸 짤막하게 써보자면,

객체 타입: 관련 있는 데이터들을 묶어서 한번에 나타내는 것.

클래스는 객체를 만들 때 설계도처럼 사용된다.

클래스를 미리 정의해놓으면 필요할때마다 클래스를 사용해서 동일한 모양을 가진 객체를 만들 수 있다.

class Notebook {
	constructor (name, price, company) {
    	    this.name = name
            this.price = price
            this.company = company
        }
}

객체 만들 때 const 변수명 = new 클래스명(매개변수). new를 꼭 써줘야 한다는 점!!

const notebook1 = new Notebook("Thinkpad", "700", "Lenovo")

클래스에는 데이터를 나타내는 속성 뿐만 아니라 함수와 같이 특정 코드를 실행할 수 있는 메소드도 정의할 수 있다.

메소드를 호출하는 방법은 다음과 같다. 

class Notebook {
	constructor (name, price, company) {
    	    this.name = name
            this.price = price
            this.company = company
        }
        
        printInfo() {
        	console.log("상품명: ${this.name}")
        }
}

const notebook = new Product ("Lenovo Thinkpad", 700)
notebook.printInfo()

물론 템플릿없이 빠르게 객체를 만드는 객체 리터럴 사용할 수도 있지만,

클래스를 재사용하는 게 더 효과적이므로 이렇게 메소드 호출하는 게 더 효율적이다.

 

 

다만 클래스와 객체, 메소드, 배열을 만들 때 문법이 생각이 잘 안났고,

파이썬으로 한창 코드짜다가 자바스크립트로 어려운 문제를 접근하려니 잘 안써졌다.

결국 타임 어택 문제는 모두 파이썬으로 풀었다.

하지만 내가 공부하고 있는 게 node고, 백엔드 개발자 분야의 일을 생각하고 있을 때 자바스크립트는 필수불가결하다.

이번주는 자료구조 알고리즘 끝나자마자 자바스크립트 책으로 공부하고, 프로그래머스 스쿨에서 쉬운문제부터 하나하나 풀어봐야겠다.

 

 

타임어택에서 풀었던 문제 중에 로그인 문제를 2가지 방법으로 풀게 되어 이곳에서 썰을 풀어본다.

처음에는 풀지 못해서 정답을 봤었다. 그 중에서 배열 안에 딕셔너리를 넣어서 id와 pw값을 넣은 답이 있었다.

이를 개발자 친구에게 물어보니, 이럴 땐 entry값이 많아질수록 dictionary를 새로 만들어야 하는 부담이 커지고 비효율적이라고 했다.

그래서 for문으로 그냥 배열 안에 배열을 만들어버렸다.

# 1차 시도. dic을 선언해주고 이 안에 새로운 id와 pw짝들을 추가해서 넣었다.
def solution(id_pw, db):
    dic = {}
    for a in db:
        dic[a[0]] = a[1]

    if id_pw[0] in dic:
        if id_pw[1] == dic[id_pw[0]]:
            return "login"
        else:
            return "wrong pw"
    else:
        return "fail"

 

# for문으로 고친 코드. 딕셔너리 없이 id부분과 pw부분이 입력값과 db에 있는 값과 일치하는 지를 확인했다
def solution(id_pw, db):
    answer = 0
    for trial in db:
        if trial[0] == id_pw[0]:
           if trial[1] == id_pw[1]:
               return "login"
           else:
               return "wrong pw"
    return "fail"

result = solution(["tnwjd1111","1111"],[["tnwjd1111","1112"],["lengi","0000"]])
print(result)

두번째 코드가 더 효율적이라는 것을 깨닫기까지 많은 시간이 걸렸다.

데이터가 1000000개 이런식으로 들어가면 결과값을 보여주기까지 시간이 많이 걸렸고, 끝나지 않은 경우도 있었다.

뭐가 더 효율적인건지 보는 눈은 아직 키워지지 않았다 ㅠㅠ

 

 

 

그리고는 자료구조 알고리즘 5주차 실전문제 풀이.

실전문제 1. 나잡아봐라 게임.

코니는 시간에 따라 달리는 속도가 일정한 반면

브라운의 경우의 수가 너무 많고 쉽게 일반화 지어지지 않을 것 같다.

그러면 모든 경우의 수를 다 나열해야 하므로 BFS를 사용한다.

브라운의 위치를 나타내는 모든 경우의 수를 구해야 한다.

그런 경우의 수를 쌓기 위한 queue를 생성해야 한다. 이 queue안에는 새로운 위치와 시간이 담긴다.

 

또한 "잡았다"라는 뜻이, 브라운과 코니가 똑같은 시간에 똑같은 위치에 있다는 말이다.

따라서 시간과 위치를 저장해놓는 자료구조가 필요하다.

 

배열은 규칙적으로 증가하거나 감소하는 데이터를 넣기 좋았고,

딕셔너리는 데이터를 자유자재로 저장할 수 있었다. 따라서 딕셔너리 형태로 각 시간마다 위치를 저장한다.

 

또한 탈출조건을 살펴보면, 1.코니가 너무 멀리 갈때 2. 브라운이 범위를 벗어나는 위치로는 갈 수 없다는 점을 활용한다.

성공조건으로는 코니와 브라운의 위치와 시간이 같을 때.

이를 위해 방문한 시간과 위치를 저장하는 배열 visited를 선언한다.

위치마다 브라운이 방문한 시간을 적기 위해 배열 안에 딕셔너리를 넣는다.

예를 들어, 5 in visited[3]의 뜻은 5초에 위치 3을 방문했는지 알아보는 것이고,

9 in visited[3]은 9초에 위치 3을 방문했는지 알아보는 것이다.

따라서 visited[코니의 위치]에 브라운의 시간이 있을 때 참값을 반환한다.

즉 브라운이 [현재 코니가 바문한 위치에] 현재시간에 들를 수 있을 때 참값을 반환한다.

from collections import deque

c = 11
b = 2


def catch_me(cony_loc, brown_loc):
    time = 0
    queue = deque()
    queue.append((brown_loc, 0))  # 위치와 시간을 담아줄게요!.
    visited = [{} for _ in range(200001)]

    while cony_loc < 200000:
        cony_loc += time
        if time in visited[cony_loc]:
            return time

        for i in range(0, len(queue)):  # Q. Queue 인데 while 을 안 쓰는 이유를 고민해보세요!
            current_position, current_time = queue.popleft()

            new_position = current_position - 1
            new_time = current_time + 1
            if new_position >= 0 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position + 1
            if new_position < 200001 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position * 2
            if new_position < 200001 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

        time += 1


print(catch_me(c, b))

print("정답 = 3 / 현재 풀이 값 = ", catch_me(10,3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550,500))

 

 

실전문제 2: 문자열 압축

문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현한다.

문자열을 1개 이상의 단위로 잘려서 압축하는 것이 목표다.

 

1개 이상의 단위라는 말은, 1개가 될 수 있고 2개가 될 수 있고, ... 문자 수가 n개일때 n/2개가 될 수 있다.

따라서 모든 경우에서 가장 압축을 많이 시킨 문자열의 길이를 반환해야 한다.

쪼개는 방법은 문자 슬라이싱을 통해 구현 가능하고, split_size 크기만큼 0부터 n까지 반복한다.

또 count라는 변수를 선언해 반복되는 문자열을 세어주고, 동일한 문자열이 오면 count를 늘려나간다.

다른 순간이 오면 compressed라는 변수에 추가한다.

마지막에 주의해야 할 점은, 비교 대상이 설정되지 않은 마지막 인덱스 값을 추가해서 검사해야 한다.

이제까지 나온 값 중 min값을 리턴하면 된다.

input = "abcabcabcabcdededededede"


def string_compression(string):
    n = len(string)
    compression_length_array = []  # 1~len까지 압축했을때 길이 값

    for split_size in range(1, n // 2 + 1):
        compressed = ""
        # string 갯수 단위로 쪼개기 *
        splited = [
            string[i:i + split_size] for i in range(0, n, split_size)
        ]
        count = 1

        for j in range(1, len(splited)):
            prev, cur = splited[j - 1], splited[j]
            if prev == cur:
                count += 1
            else:  # 이전 문자와 다르다면
                if count > 1:
                    compressed += (str(count) + prev)
                else:  # 문자가 반복되지 않아 한번만 나타난 경우 1은 생략함
                    compressed += prev
                count = 1  # 초기화
        if count > 1:
            compressed += (str(count) + splited[-1])
        else:  # 문자가 반복되지 않아 한번만 나타난 경우 1은 생략함
            compressed += splited[-1]
        compression_length_array.append(len(compressed))

    return min(compression_length_array)  # 최솟값 리턴


print(string_compression(input))  # 14 가 출력되어야 합니다!

print("정답 = 3 / 현재 풀이 값 = ", string_compression("JAAA"))
print("정답 = 9 / 현재 풀이 값 = ", string_compression("AZAAAZDWAAA"))
print("정답 = 12 / 현재 풀이 값 = ", string_compression('BBAABAAADABBBD'))

두 번째 문제는 조금 피곤해서 그냥 보기만하고 내가 직접 치지 않았다.

내일은 여기서부터 복습하고, 삼성 역량 테스트 1,2,3풀면 하루가 다 갈것 같다.

내일 오전 9시에 오늘 풀었던 타임어택 풀이가 있다고 하는데, 파이썬이랑 자바스크립트 둘 다 진행하려면 시간이 꽤 오래걸릴텐데... 나중에 녹음본을 들으려 한다.

어차피 프로그래머스 스쿨에서 정답도 볼 수 있고 하니까. 내일은 자료구조 알고리즘 어떻게든 끝내보자!