수리링의 데이터교실

한동안 코테를 잠시 안풀었더니

효율성 테스트를 통과하는데 조금 헤맸던 문제입니다..!

Stack 알고리즘을 활용하지 않고 문제를 풀었을 때 테스트 케이스 정확성은 통과하는 데 문제가 없으나, 효율성 테스트를 통과하기 어려우실 수 있습니다. 효율성 테스트까지 통과할 수 있는 문제 풀이 방법을 알려드릴게요 :)

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제 상황 : 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

1.

먼저 빠른 탈출을 위해 다음 4가지 경우에는 함수를 False로 얼리 리턴하도록 설정해주겠습니다.

• 주어진 문자열이 ")" 로 시작하는 경우
• 주어진 문자열이 "(" 로 끝나는 경우
• 주어진 문자열의 길이가 홀수인 경우
• 주어진 문자열이 ")" 또는 "(" 한 종류로만 이루어진 경우

def solution(s):
    if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
        return False

2.

다음으로 stack 리스트를 선언해주도록 하겠습니다.

    stack = []

우리는 stack 리스트에 "(" 열기 괄호만 넣어줄 것입니다.

왜 열기 괄호만 넣어줄까요? 예시를 통해 한번 확인해 봅시다.

문자열 s = "(((())"가 있다고 합시다. 딱 봐도 열기 괄호는 4개인데 닫기 괄호는 2개여서 짝이 맞지 않는다는 것을 알 수 있습니다. 우리는 for루프를 통해 0번째 자릿값부터 차례대로 돌면서 해당 자리의 값이 "("이면 stack에 넣어주고, ")"이면 stack에 있는 열기괄호를 하나 빼 줄 것입니다.

    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()

s = "(((())"

1. 첫 번째 자리 "(" -> stack = "(" 
2. 두 번째 자리 "(" -> stack = "(", "("
3. 세 번째 자리 "(" -> stack = "(", "(", "("
4. 네 번째 자리 "(" -> stack = "(", "(", "(", "("
5. 다섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop()
   -> stack = "(", "(", "("
6. 여섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop()
   -> stack = "(", "("

    if stack:
        return False
    else:
        return True

이터레이션을 다 돌고 났을 때

stack이 비어 있으면 짝이 맞으므로 True

stack에 남은 값이 있다면 짝이 맞지 않는 것이므로 False를 리턴합니다.

결국 "("의 갯수와 ")"의 갯수가 동일한지 확인하는 것과 다름 없습니다. 다른 방법으로도 정확성 문제는 통과하는 데 어려움이 없으나, 효율성에 문제가 생기는 관계로 stack 알고리즘을 통해 효율성을 높여준 것이라고 보시면 되겠습니다.

3.

마지막으로 한 번에 코드를 보겠습니다.

def solution(s):
    if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
        return False

    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    
    if stack:
        return False
    else:
        return True

감사합니다!

프로그래머스 코딩테스트 1단계에 수록되어있는 카카오 인턴십 '키패드 누르기' 문제를 풀었습니다. 풀고 나서 코드가 좀 길다고 생각했는데 다른 사람들의 풀이를 보니 다들 비슷한 길이라서 안심이 되었습니다. (한심...ㅎ) 길다고 무조건 나쁜 코드, 짧다고 무조건 좋은 코드는 아니긴 합니다. 그래도 최대한 니트하고 간결하게 작성하고싶은 욕심이 드는 건 어쩔 수가 없네요 ㅎ_ㅎ (그럼에도 불구하고 제 코드는 항상 긴 편인거 같아요.)

저는 키패드에 좌표 개념을 도입하여 간단하게 문제를 풀어보았습니다. 문제 풀이 시간은 5분-10분정도로 그래도 최근에 연습했던 알고리즘 문제들에 비교하면 비교적 수월했던 문제였던 것 같습니다. 그럼 풀어보겠습니다!

문제 상황 : 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 1. 엄지손가락은 상하좌우 4가지 방향... (중략....) 자세한 문제 상황과 조건, 입출력, 테스트 케이스 등은 꼭 프로그래머스에서 확인해 보세요! https://school.programmers.co.kr/learn/courses/30/lessons/67256

1. 문제의 이해

먼저 정수로 이루어진 리스트 numbers가 인풋으로 주어집니다. 문제 조건을 보면, 정수가 1, 4, 7일 때에는 바로 왼손을, 3, 6, 9일때는 바로 오른손을 쓰면 되기 때문에 아무런 제약이 없어서 굉장히 쉽습니다. 우리가 고민해야 할 부분은 정수가 2, 5, 8, 0일 때입니다.

2, 5, 8, 0이 주어졌을 때 조건에 맞게 손가락을 움직이기 위해서는

 1)  그 전의 손가락 위치를 알고 있어야 합니다.

 2)  그 전의 손가락 위치와 2/5/8/0 사이의 거리를 숫자로 나타낼 수 있어야 합니다.

 3)  왼손, 오른손과 2/5/8/0 사이의 거리를 비교할 수 있어야 합니다.

그럼 위 세 가지를 고민하면서 문제를 풀어보겠습니다.

2. 풀이

[1] 변수와 좌표 설정

def solution(numbers, hand):
    answer = ""
    current_left_thumb = (4, 1)
    current_right_thumb = (4, 3)

저는 키패드 1이 있는 곳을 좌표 (1, 1)으로, 

키패드 3이 있는 곳을 좌표 (1, 3)으로,

키패드 *이 있는 곳을 좌표 (4, 1)으로,

키패드 #이 있는 곳을 좌표 (4, 3)으로 놓았습니다.

첫줄을 파이썬 인덱싱과 같이 0부터 시작할까 하다가 보다 직관적으로 하기 위해 1부터 시작해줬는데, 0부터 시작해도 큰 상관은 없습니다.

current_left_thumb, current_right_thumb라는 변수명을 사용하여 왼손/오른손을 구분하여 현재 손가락이 어디 있는지를 좌표값으로 표현했습니다. 변수명이 조금 길고 번잡하긴 하지만 직관적으로 이해할 수 있어서 스스로 코드 이해하기가 편했습니다. 이 두 가지 변수는 앞으로 numbers에 주어진 정수값에 따라 손가락이 움직일 때 함께 업데이트가 되어 갈 예정입니다!

[2] 1/4/7, 3/6/9 처리

    for number in numbers:
        if number == 1:
            answer += "L"
            current_left_thumb = (1, 1)
        elif number == 4:
            answer += "L"
            current_left_thumb = (2, 1)
        elif number == 7:
            answer += "L"
            current_left_thumb = (3, 1)
        elif number == 3:
            answer += "R"
            current_right_thumb = (1, 3)
        elif number == 6:
            answer += "R"
            current_right_thumb = (2, 3)
        elif number == 9:
            answer += "R"
            current_right_thumb = (3, 3)

다음으로 numbers 리스트의 값(value)를 가지고 하나씩 살펴보면서 이터레이션을 돌려줍니다. 리스트 이터레이션은 습관적으로 인덱스로 하게 되는데, 이번 문제에서는 굳이 인덱스로 조회할 필요가 없어서 편했습니다.

만약 number가 1/4/7중에 하나라면 answer 스트링에 L을 추가하고 해당 좌표값으로 왼손을 움직입니다(current_left_thumb 변수의 좌표를 업데이트합니다.). 만약 number 3/6/9중에 하나라면 answer 스트링에 R을 추가하고 해당 좌표값으로 오른손을 움직입니다(current_right_thumb 변수의 좌표를 업데이트합니다.). 

이 부분의 문법이 어쩔수없이 위처럼 길어지게 되었는데, 어떻게 하면 더 짧게 쓸 수 있을까 잠깐 고민했어요. 하지만 지금 이대로도 아주 직관적이고 이해하기 편하기 때문에 굳이 줄이지 않아도 되겠다고 판단하고 다음 단계로 넘어갔습니다.

[3] 2/5/8/0 처리

        elif number in [2, 5, 8, 0]:
            if number == 2: x = 1
            if number == 5: x = 2
            if number == 8: x = 3
            if number == 0: x = 4

다음으로 가장 중요한 2, 5, 8, 0입니다. 저는 2, 5, 8, 0이 모두 같은 세로줄에 있다는 점에 착안하여 아이디어를 얻어서 2/5/8/0의 열(y)을 2로 고정하고 행(x)만 변수로 각각 1/2/3/4를 할당해 주었습니다. 더 자세히 설명해보겠습니다.

숫자 2의 좌표값은 (1, 2)입니다.

숫자 5의 좌표값은 (2, 2)입니다.

숫자 8의 좌표값은 (3, 2)입니다.

숫자 0의 좌표값은 (4, 2)입니다.

따라서 숫자 2, 5, 8, 0의 좌표를 (x, 2)와 같이 표현하고 x에만 각각 1/2/3/4를 할당해 주어 반복을 줄이겠다는 의미입니다.

distance_r = abs(current_right_thumb[0] - x) + abs(current_right_thumb[1] - 2)
distance_l = abs(current_left_thumb[0] - x) + abs(current_left_thumb[1] - 2)

# 가독성을 위해 인덴트를 없앴습니다

이제 거리 구하기로 넘어갑니다. 우리는 current_left_thumb와 current_right_thumb 라는 변수에 각각 왼손과 오른손 엄지의 직전 좌표값을 저장해 두고 있어요. 우리가 가고자 하는 2/5/8/0의 좌표값과 왼손, 오른손 사이의 거리를 각각 구해보도록 하겠습니다.

일반화된 식을 쓰기 전에 예시를 가지고 생각을 열어 볼게요. 키패드 2와 6 사이의 거리는 2입니다. 좌표로 어떻게 구할 수 있을까요? 키패드 2의 좌표는 (1, 2), 키패드 6의 좌표는 (2, 3)입니다. x값의 차이 1과 y값의 차이 1을 더해 주면 간단히 2가 나오는 것을 알 수 있어요. 키패드 8과 키패드 1의 경우는 어떨까요? 우선 거리는 3입니다. 좌표로 확인해 봅니다. 키패드 8의 좌표는 (3, 2)입니다. 키패드 1의 좌표는 (1, 1)입니다. x값의 차이 2와 y값의 차이는 1이며 둘을 더해 주면 3이 됩니다. 이제 일반화가 되었습니다.

abs(current_right_thumb[0] - x) : 오른손 엄지손가락의 행좌표와 2/5/8/0의 행좌표(x)의 차(절댓값)

abs(current_right_thumb[1] - 2) : 오른손 엄지손가락의 행좌표와 2/5/8/0의 열좌표(2)의 차(절댓값)

이 두개를 더해 주면 오른손이 움직이는 거리(distance_r)가 되고,

같은 방법으로 왼손이 움직이는 거리(distance_l)도 구해준 거예요.

            if distance_r < distance_l:
            # 오른손이 가야 하는 거리가 더 짧을 때
                answer += "R"
                current_right_thumb = (x, 2)
            elif distance_r > distance_l:
            # 왼손이 가야 하는 거리가 더 짧을 때
                answer += "L"
                current_left_thumb = (x, 2)
            else:
            # 왼손 = 오른손 거리가 같을 때
                if hand == 'right':
                # 오른손잡이라면
                    answer += "R"
                    current_right_thumb = (x, 2)
                else:
                # 왼손잡이라면
                    answer += "L"
                    current_left_thumb = (x, 2)

이제 거리를 비교합니다. 오른손이 가야 하는 거리가 더 짧을 때, 왼손이 가야 하는 거리가 짧을 때, 왼손과 오른손이 가야할 거리가 같을 때로 크게 셋으로 나누어 생각합니다. 특히 왼손, 오른손 거리가 같다면 왼손잡이인지 오른손잡이인지를 판단하는 것이 중요합니다.

이제 제가 작성한 함수를 한 번에 보겠습니다.

def solution(numbers, hand):
    answer = ""
    current_left_thumb = (4, 1)
    current_right_thumb = (4, 3)

    for number in numbers:
        if number == 1:
            answer += "L"
            current_left_thumb = (1, 1)
        elif number == 4:
            answer += "L"
            current_left_thumb = (2, 1)
        elif number == 7:
            answer += "L"
            current_left_thumb = (3, 1)
        elif number == 3:
            answer += "R"
            current_right_thumb = (1, 3)
        elif number == 6:
            answer += "R"
            current_right_thumb = (2, 3)
        elif number == 9:
            answer += "R"
            current_right_thumb = (3, 3)
        elif number in [2, 5, 8, 0]:
            if number == 2: x = 1
            if number == 5: x = 2
            if number == 8: x = 3
            if number == 0: x = 4

            distance_r = abs(current_right_thumb[0] - x) + abs(current_right_thumb[1] - 2)
            distance_l = abs(current_left_thumb[0] - x) + abs(current_left_thumb[1] - 2)
            if distance_r < distance_l:
                answer += "R"
                current_right_thumb = (x, 2)
            elif distance_r > distance_l:
                answer += "L"
                current_left_thumb = (x, 2)
            else:
                if hand == 'right':
                    answer += "R"
                    current_right_thumb = (x, 2)
                else:
                    answer += "L"
                    current_left_thumb = (x, 2)
    return answer

숫자가 2, 5, 8, 0일 때 열 좌표가 2로 모두 동일하다는 점에 착안하여 행 좌표만 x로 변수 할당을 해줌으로써 반복을 줄일 수 있었습니다. 비록 엄청 짧은 코드는 아니지만 깔끔하고 직관적으로 풀이할 수 있어서 좋았습니다!

부족한 풀이었지만 도움이 되었으면 좋겠네요~ 감사합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/159994

프로그래머스 코딩테스트 1단계에 수록되어 있는 '카드 뭉치' 문제를 풀었습니다. 다른 사람의 풀이와 비교해보니 제가 조금 독특하게 풀었더라구요. 제 코드가 좀 지저분하긴 하지만 남들과 다른 아이디어로 푼 게 마음에 들어 sorted 문법 정리할 겸 풀이과정을 작성해보고자 합니다.

우선 제출한 답안은 다음과 같습니다.

def solution(cards1, cards2, goal):
    cards1_sorted = sorted(enumerate(cards1), 
    	key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
    cards2_sorted = sorted(enumerate(cards2), 
    	key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
                           
    index_1 = [index for index, value in cards1_sorted]
    index_2 = [index for index, value in cards2_sorted]
    
    if index_1 != sorted(index_1) or index_2 != sorted(index_2):
        return "No"
    else:
        return "Yes"

하나씩 쪼개어 정리해 보겠습니다.

테스트케이스의 2번째 예시로 설명해 보겠습니다.

1. 먼저, cards1과 cards2에 enumerate() 함수를 이용해서 (인덱스, 카드)값이 되도록 만들어 줍니다. list()함수를 씌워 결과값을 눈으로 확인하면 다음과 같습니다.

cards1 = ["i", "water", "drink"]
cards2 = ["want", "to"]	
goal = ["i", "want", "to", "drink", "water"]	

list(enumerate(cards1))
# [(0, 'i'), (1, 'water'), (2, 'drink')]

list(enumerate(cards2))
# [(0, 'want'), (1, 'to')]

2. 저는 이렇게 추출한 이뉴머레이트 결과값을, sorted()를 이용해서 정렬을 해줄 거에요. 이 때 정렬을 해 주는 기준으로 goal을 넣어 주어서, goal에 있는 순서대로 정렬되도록 하겠습니다.

cards1_sorted = sorted(enumerate(cards1), key = lambda x: goal.index(x[1])
cards2_sorted = sorted(enumerate(cards2), key = lambda x: goal.index(x[1])

cards1_sorted
# [(0, 'i'), (2, 'drink'), (1, 'water')]

cards2_sorted
# [(0, 'want'), (1, 'to')]

key = lambda x: goal.index(x[1]) 와 같이 정렬 조건을 걸어줌으로써, cards1의 이뉴머레이트 결과값의 인덱스 1번 벨류가 goal에 어떤 순서대로 있느냐?를 기준으로 정렬한 값을 반환하도록 하였습니다. 결과값을 확인해보니 cards2는 그대로이지만 cards1은 drink가 앞으로 온 것을 확인할 수 있습니다. 그런데 이 문법에는 문제가 있습니다. 만약 cards1에 있는 단어가 goal에 없다면 어떻게 될까요?

2 - (1)

cards1 = ["i", "water", "drink", "apple"]
cards1_sorted = sorted(list(enumerate(cards1)), key = lambda x: goal.index(x[1]))

# ValueError: 'apple' is not in list

cards1에 'apple'을 추가해 보니, 벨류 에러가 발생합니다. 따라서 이렇게 없는 값이 있을 경우에는 cards1_sorted의 맨 뒤에다가 값을 추가해주도록 조건을 걸어주겠습니다.

cards1_sorted = sorted(list(enumerate(cards1)), 
             	   key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
cards2_sorted = sorted(list(enumerate(cards2)), 
            	   key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))

만약 x[1]이 goal에 있다면 기존대로 정렬을 하고, 없다면 뒤에 추가하도록 if else 구문을 사용하여 조건을 걸어줬습니다. 이 부분은 챗지피티의 도움으로 완성할 수 있었습니다^_ㅠ 엄청 직관적인 문법이 아닌것 같긴 합니다만 그래도 자주 사용해서 자유자재로 구사할 수 있도록 하려고 합니다.

다시 apple이 없었던 원래의 예시문제로 돌아가서 계속해서 설명해보겠습니다.

3.

index_1 = [index for index, value in cards1_sorted]
index_2 = [index for index, value in cards2_sorted]


index_1
# [0, 2, 1]
index_2
# [0, 1]

이제 cards1_sorted와 cards_2sorted에서 인덱스만 뽑아서 깔끔한 리스트 index_1, index_2로 뽑아냅니다. 저는 이 index 리스트의 결과값이 0-2-1처럼 순서에 맞지 않을 경우 카드를 앞에서부터 차례로 사용하는 조건에 어긋난다는 점을 발견했습니다. 

따라서 index_1, index_2가 오름차순으로 정렬되어 있다면 "Yes"를, 그렇지 않다면(순서가 뒤죽박죽이라면) "No"를 리턴하도록 함수를 작성했습니다.

def solution(cards1, cards2, goal):
    cards1_sorted = sorted(enumerate(cards1), key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))
    cards2_sorted = sorted(enumerate(cards2), key = lambda x: (goal.index(x[1]) if x[1] in goal else len(goal) + 1))

    index_1 = [index for index, value in cards1_sorted]
    index_2 = [index for index, value in cards2_sorted]
    
    if index_1 != sorted(index_1) or index_2 != sorted(index_2):
        return "No"
    else:
        return "Yes"

최근에 sorted() 함수에 대해서 리뷰를 했으며 특히 key 뒤에 lambda 함수를 어떻게 활용할 수 있는 지 여러번 살펴보았기 때문에 위와 같은 아이디어로 문제를 풀 수 있었습니다. 다른 사람의 풀이를 확인해보니 이런 방식으로 풀이를 하신 분은 찾아보기 어려웠고 더 짧고 깔끔하고 반듯하게 푸신 분이 많아서 존경스러웠습니다! 아주 깔끔한 코드는 아니지만 그래도 재밌는 아이디어로 풀어낸 점을 스스로 높게 평가하고자 합니다 ^_^!

감사합니다.

graph_45 = [
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]

n = 4
m = 5

첫째 / BFS 방식으로 풀기

출발점에서부터 점진적으로 진행해가는 방식으로 접근하는 경우 BFS를 고려해볼 수 있습니다.

일단 BFS니까 아묻따 디큐부터 임포트해주고 시작합니다.

from collections import deque

1. 함수를 작성합니다. 입력받은 출발점 좌표로부터 시작하여 출발점 좌표가 1이면 바로 False를 리턴하고, 출발점 좌표가 0이면 주변을 탐색하면서 0이 있으면 1로 바꾸고, 더이상 바꿀 0이 없는 경우에는 True를 리턴하는 함수를 작성합니다.

2. 함수 작성 이후, 주어진 그래프의 (0, 0)부터 시작하여 n*m 좌표마다 함수를 적용하도록 이터레이션을 돌립니다. True가 반환되는 갯수가 곧 음료수 얼음 덩어리의 갯수가 됩니다.

def ice_bfs(row_init, col_init):
    # 만약 주어진 좌표가 0이라면 가보자고!
    if graph[row_init][col_init] == 0:
        q = deque([[row_init, col_init]])
        # ---------------------------------------- 무한 루프 
        while True:
            if not q:
                return 1

            row, col = q.popleft()
            for [dx, dy] in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                # 이동한 값이 지도 안에 있고
                if 0 <= row + dx < n and 0 <= col + dy < m:
                    # 얼릴 수 있다면
                    if graph[row+dx][col+dy] == 0:
                        # 1번 도장을 찍고, 그 다음 할일 추가하세요
                        graph[row+dx][col+dy] = 1
                        q.append([row+dx, col+dy])
        # ---------------------------------------- 무한 루프 
    else:
        return 0

result = 0

for row in range(n):
    for col in range(m):
        result += ice_bfs(row, col)

print(result)
# 3

둘째 / DFS 방식으로 풀기

위에서 작성한 함수를 DFS방식을 활용한 재귀함수로 바꾸어 작성해 봅시다. (같은 기능!)

def dfs_recursive(row, col):
    # 주어진 점이 틀 밖이라면 바로 함수 종료
    if row <= -1 or row >= n or col <= -1 or col >= m:
        return False
    
    # [1] 주어진 점이 0이라면 True를 반환
    if graph[row][col] == 0:
        
        graph[row][col] = 1  # 일단 True 반환 전에 0->1로 바꾸고
        dfs_recursive(row, col-1)
        dfs_recursive(row-1, col)
        dfs_recursive(row, col+1)
        dfs_recursive(row+1, col) # 상하 좌우도 전부 점검해주기!

        return True

    # [2] 주어진 점이 1이라면 False를 반환
    else:
        return False

같은 방식으로 모든 좌표점에 작성한 함수를 돌려주면서 True가 반환되는 개수를 세어 주면 끝~

result = 0

for row in range(n):
    for col in range(m):
        result += dfs_recursive(row, col)

print(result)
# 3

짱짱 재밌군!

BFS도 DFS도 자유자재로 활용할 수 있도록 열심히 반복!

다음 문제로는 카카오 2022 블라인드 공개채용 <양과 늑대> 문제를 풀어봅시다...

탐색으로 풀어보려고 했으나 경우의 수를 모두 나누기가 어려웠습니다. 다른사람들의 풀이를 참고해 보니 direction 값을 right부터 시작하여 순차적으로 바꾸어나가는 이터레이션을 돌리면 간단하게 해결이 가능했습니다.

문제 설명 : 양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

코드로 작성해 봅시다.

# 예시 (n=3일 때)

n = 3
graph = [[0] * n for _ in range(n)]

graph
# [[0, 0, 0],
#  [0, 0, 0],
#  [0, 0, 0]]

먼저 함수 초반에 그래프의 초기값은 다음과같이 세팅해줍니다. 확실히 리스트 컴프리핸션은 자유자재로 쓸 수 있어야 합니다.

# 기본 뼈대

for i in range(1, n**2+1):
    if dir == 'r':
        y += 1
    elif dir == 'd':
        x += 1
    elif dir == 'l':
        y -= 1
    elif dir == 'u'
        x -= 1

방향의 값은 오른쪽부터 시작해서 나선형으로 오른쪽 -> 아래 -> 왼쪽 -> 위 -> 오른쪽 ...(반복) 순서로 뱅글뱅글 돌아가게 해줄 겁니다. 그럼 완성된 함수로 작성해 보겠습니다.

def solution(n):
	# 만약 n이 1인 경우 빠르게 종료
    if n == 1:
    	return [[1]]
        
    # 초기값 세팅 : (0, 0)으로부터 오른쪽 이동부터 시작한다.
    graph = [[0] * n for _ in range(n)]
    x = 0
    y = 0
    direction = 'R'
	
    # n의 제곱번 이터레이션을 돌려 준다.
    for i in range(1, n**2 + 1):
    	graph[x][y] = i
        
        # right : x값 고정, y값만 1 증가
        if direction == 'R':
            y += 1
            # 만약 끝까지 갔거나 그 다음 값이 0이 아니라면 방향 변경
            if y == n-1 or graph[x][y+1] != 0:
            	direction = 'D'

        # down : y값 고정, x값만 1 증가
        elif direction == 'D':
        	x += 1
            # 만약 끝까지 갔거나 그 다음 값이 0이 아니라면 방향 변경
            if x == n-1 or graph[x+1][y] != 0:
            	direction = 'L'

        # left : x값 고정, y값만 1 감소
        elif direction == 'L':
        	y -= 1
            # 만약 끝까지 갔거나(y값이 0) 그 다음 값이 0이 아니라면 방향 변경
            if y == 0 or graph[x][y-1] != 0:
            	direction = 'U'
                
        # up : y값 고정, x값만 1 감소
        elif direction == 'L':
        	x -= 1
            # 만약 끝까지 갔거나 그 다음 값이 0이 아니라면 방향 변경
            if x == n-1 or graph[x-1][y] != 0:
            	direction = 'R'
                
        return graph

완성된 함수에는 더이상 갈 곳이 없거나 가야할 곳에 0이 아닌 숫자가 있는 경우 방향을 변경해주는 기능이 추가되었습니다. 25번 이터레이션을 돌면서 각각의 순서에 맞게 번호가 부여됩니다.

아휴 재밌다

백준 2178번 미로탐색

https://www.acmicpc.net/problem/2178

n = 4
m = 6

graph = [
	[1, 0, 1, 1, 1, 1],
 	[1, 0, 1, 0, 1, 0],
 	[1, 0, 1, 0, 1, 1],
 	[1, 1, 1, 0, 1, 1]
 ]

0과 1로 이루어진 n * m 크기의 미로 그래프가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

먼저 상하좌우로 움직일수 있는 x, y 델타값을 리스트로 작성한다.

def dfs_escape(start = (0, 0)):
	# x, y의 현재 포지션을 정해 준다. 
    x_pos = start[0]
    y_pos = start[1]
    
    # 할 일을 기록할 디큐 리스트 q를 작성한다.
    q = deque()
    
    # 가장 처음 초기값을 세팅해준다. x, y의 좌표값 위치를 튜플로 집어넣는다.
    q.append((x_pos, y_pos))
    
    # 할 일이 없을 때까지 반복!
    while q:
    	now_x, now_y = q.popleft()
        
        # 상하좌우 4번 반복
        for i in range(4):
        	next_x = now_x + dx[i]
        	next_y = now_y + dy[i]
            
            # 만약 다음으로 갈 좌표값이 미로를 벗어나지 않는다면
            if 0 <= next_x < n and 0 <= next_y < m:
                if graph[next_x][next_y] == 1:
                    graph[next_x][next_y] = graph[now_x][now_y] + 1
                    q.append((next_x, next_y))

bfs_miro()


graph
# [[3, 0, 9, 10, 11, 12],
#  [2, 0, 8, 0, 12, 0],
#  [3, 0, 7, 0, 13, 14],
#  [4, 5, 6, 0, 14, 15]]


graph[n-1][m-1]
# 15

https://www.acmicpc.net/problem/18352

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 

[ 입력 조건 ] 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

[출력조건] X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다. 이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예시 2번으로 문제를 풀어보자.

n, m, k, x = map(int , input().split())
# 4 4 1 1


graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input("출발 도착").split())
    graph[a].append(b)
    
    
graph
# [[], [2, 3], [3, 4], [], []]

먼저 입력을 받아 n, m, k, x값을 할당받고,

graph 리스트를 만들어 각 도시별로 연결된 도시들을 표시해준다.

INF = float("inf")
[INF] * (n + 1)
# [inf, inf, inf, inf, inf]

앞으로 출발 도시 x로부터 각각의 모든 도시까지 거리를 distance로 계산해줄 것이다.

(n+1)을 곱해주는 이유는 가상의 0번 도시를 설정하여 인덱스를 편하게 계산해주기 위함이다.

앞으로 distance에서 자기 자신과의 거리는 0으로, 자기 자신을 제외한 다른 도시는 모두 INF로 시작하는 점을 기억하자.

def solution(start):
    # 앞으로 방문해야할 도시 리스트는 디큐 리스트 q로 둔다.
    q = deque()
    # 출발점 도시 x로부터의 거리를 나타내는 디큐 리스트 distance를 만든다.
    distance = deque([INF] * (n+1))
    
    # 초기값 세팅
    q.append(start)
    distance[start] = 0
    
    # 더이상 방문할 도시가 없을 때까지 반복하기
    while q:
    	# 지금 방문하는 도시 now
    	now = q.popleft()
        for next_city in graph[now]:
        	# 만약 아무도 오지 않았던 신규 방문지라면
            if distance[next_city] == INF:
            	# 본 문제에서는 도시간의 거리가 1이므로 1을 더하지만
                # 문제 조건 따라 1이 아니게 될 수 있음
            	distance[next_city] = distance[now] + 1
                q.append(next_city)
                
     # 디스턴스 리스트를 리턴
     return distance

dis_result = bfs_city(x)
dis_result
# deque([inf, 0, 1, 1, 2])

dis_k = [i for i, v in enumerate(dis_result) if v == k]
dis_k
# [2, 3]

if dis_k == []:
    print(-1)
else:
    while dis_k:
        print(dis_k.pop(0))
# 2
# 3

연습으로 미로 탐색 백준 2178번 문제를 풀어보자.

from collections import deque

디큐는 속도가 빠른 리스트로 생각해도 좋다.

코딩 테스트에서 파이썬으로 Queue, BFS, FIFO 방식의 알고리즘 접근이 필요할 때 리스트를 디큐로 바꾸어주면 속도 이슈 해결이 가능하다.

a_list = [1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5]

a_dq = deque(a_list)
# deque([1, 2, 3, 4, 5])

이렇게 간단하게 디큐 함수로 바꾸어주기만 하면 된다.

a_dq.pop()
a_dq.popright()
# 5

a_dq.popleft()
# 1

a_dq
# deque([2, 3, 4])

a_dq.append(1004)
# deque([2, 3, 4, 1004])

• 디큐 맨 마지막 값을 뺄 때 : .pop()
• 디큐 맨 처음 값을 뺄 때 : .popleft()
  • 주의 / .pop(0)과 같이 사용하면 에러 발생!
• pop과 popleft 모두 기존의 디큐를 수정, 업데이트하는 파괴적 함수!
• 디큐 맨 뒤에 값을 추가할 때 : .append()

디큐를 활용한 bfs

graph_list = [
    [],
    [2,3,8], 
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]


def bfs(graph, start):
    need_visit = deque([])
    visited    = deque([])
    need_visit.append( start )
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            temp = graph[node]
            temp_reverse = list(reversed(temp))
            need_visit.extend( temp_reverse )
    return visited
    
    
  bfs(graph_list, 1)
  # deque([1, 8, 3, 2, 7, 5, 4, 6])

1. 선택정렬

# 0번째 아이템이 가장 작다고 가정하고 시작한다. 
# 만약 0번째 아이템보다 더 작은 아이템이 있다면 그중 가장 작은 놈과 0번째 아이템을 swap 한다.

arr = [20, 12, 10, 15, 2]

for i_step in range(len(arr)):
    # 현재 이터레이션에서 가장 작은 값의 인덱스가 무엇인지 min_step에 기록한다.
    # 앞으로 계속 갱신해 나간다.
    min_step = i_step

    for i in range(i_step+1, len(arr)):
        if arr[i] < arr[min_step]:
            min_step = i
        else:
            pass

    arr[min_step], arr[i_step] = arr[i_step], arr[min_step]

arr
>>> [2, 10, 12, 15, 20]

def my_sorted(arr) :
    arr_dup = [i for i in arr]
    for i_step in range(len(arr_dup)):
        # 현재 이터레이션에서 가장 작은 값의 인덱스가 무엇인지 min_step에 기록한다.
        # 앞으로 계속 갱신해 나간다.
        min_step = i_step

        for i in range(i_step+1, len(arr_dup)):
            if arr_dup[i] < arr_dup[min_step]:
                min_step = i
            else:
                pass

        arr_dup[min_step], arr_dup[i_step] = arr_dup[i_step], arr_dup[min_step]
    return arr_dup

my_sorted(arr)
>>> [2, 10, 12, 15, 20]

arr
>>> [20, 12, 10, 15, 2]

2. 삽입정렬

선택 정렬이 아닌 삽입정렬로 리스트를 정렬해보자.

arr = [9, 5, 1, 4, 3]

for step in range(1, len(arr)):
    for i in range(step, 0, -1):
        if arr[i-1] > arr[i]:
            arr[i-1], arr[i] = arr[i], arr[i-1]

arr
>>> [1, 3, 4, 5, 9]

arr = [9, 5, 1, 4, 3]

def my_sorted(arr):
    arr_dup = [i for i in arr]

    for step in range(1, len(arr_dup)):
        for i in range(step, 0, -1):
            if arr_dup[i-1] > arr_dup[i]:
                arr_dup[i-1], arr_dup[i] = arr_dup[i], arr_dup[i-1]
    return arr_dup

my_sorted(arr)
>>> [1, 3, 4, 5, 9]

arr
>>> [9, 5, 1, 4, 3]

3. 버블정렬

arr = [-2, 45, 0, 11, -9]

for i in range(len(arr)):
    for k in range(len(arr)-i-1):
        print(i, k)

arr = [-2, 45, 0, 11, -9]

for i in range(len(arr)):
    for k in range(len(arr)-i-1):
        if arr[k] > arr[k+1]:
            arr[k], arr[k+1] = arr[k+1], arr[k]

arr
>>> [-9, -2, 0, 11, 45]

for i in range(len(arr)):
    for k in range(len(arr)-i-1):
        if arr[k] > arr[k+1]:
            print(i, k, 'swap!')
            arr[k], arr[k+1] = arr[k+1], arr[k]
            print(arr)
        else:
            print(i, k, 'pass!')
            print(arr)