유령이 나오는 젤리하우스

Algorithm/일반

[알고리즘 일반] 재귀 함수

들어가는 말 알고리즘 공부를 하다보면 어느 순간 턱 막히는 지점이 있습니다. 분명 배우긴 배웠는데도 뭔 소리인지도 모르겠고, 공부할 때는 알겠는데 막상 구현해보라면 손이 안 움직이는 크고 작은 고비들이 알고리즘의 세계에는 존재합니다. 그 많은 고비 중에서 재귀 함수가 가장 먼저 등장합니다. 저도 재귀함수를 공부할 적에는 정말 이해가 안되서 혼자서 벽도 쳐보고, 소리도 질러보고 오만 생쑈를 다했습니다. "그렇게 복잡한 개념이라면, 아예 다음으로 미루면 되지 않느냐?" 라고 생각하실 수 있겠습니다. 맞습니다. 사실 재귀적 구현으로 풀 수 있는 문제들은 다른 방법으로도 충분히 풀 수 있습니다. 그럼에도 불구하고 우리가 재귀 함수를 배워야하는 이유는, 프로그래밍 세계에서 통하는 하나의 황금률 때문입니다. " 모..

Algorithm/Baekjoon

[BOJ 16236][백준 16236번] 아기상어 (파이썬 풀이)

https://www.acmicpc.net/problem/16236 🤔 문제 설명 및 입출력 ✍ 접근 방법 문제의 핵심은 "상어가 먹을 수 있는 물고기 중 가장 가까운 물고기를 찾아라" 이다. "가장 가까운 대상 찾기 + 입력이 행렬 꼴 " 이면 대부분의 문제는 BFS를 활용하여 풀이한다. 얼핏 보면 문제에 조건이 엄청 바리바리 달려있어서 복잡해보이지만, 상어의 크기가 커지는건 크게 어려운 부분이 아니라, 주어진 입력에 대해 다음 시퀀스를 반복하면 된다. 잡아먹을 수 있는 물고기를 찾는다 찾은 물고기들 중 가장 가까운 놈들 잡아먹는다 행렬을 갱신한다. ( 잡아 먹은놈 행렬에서 삭제) 크기를 키울 수 있으면 키운다 더 이상 잡아 먹을 수 없을 때까지 반복한다. 여기서 포인트는 잡아먹을 수 있는 "물고기 중..

Algorithm/SWEA

[SWEA 5203번] 베이비진 게임 (파이썬 풀이)

문제 바로 가기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🤔 문제 설명 및 입출력 - 문제의 저작권은 SWEA에 있습니다 - ✍ 접근 방법 탐욕 알고리즘이 언제나 그렇듯 푸는 방법도 참 다양하고, 유형도 참 다양하다. 근데 놀랍게도 대부분의 경우 머리 속에 즉흥적으로 떠오른 생각을 그대로 구현하면 해결되는 경우가 많다. 이번 문제를 풀면서 떠오른 생각은 플레이어 1 / 2에게 카드패를 한장 씩 나누어주다가, triplet이나 run이 발생하면 check를 하여 승리자로 만들게 하는 것이다. 그러기 위해서 아래와 같은 접근을 취했다. 1. 입력을 각 플레이어가 받을 카드 리스트로 변환함 2. 리스트를 fo..

Algorithm/SWEA

[SWEA 1251번] 하나로 (파이썬 풀이)

문제 바로 가기 🤔 문제 설명 및 입출력 - 문제의 저작권은 SWEA에 있습니다 - ✍ 접근 방법 이 문제는 시작 노드에서 도착 노드까지 도달하는 최소 비용을 구하는 문제가 아니라 ( 만약 문제가 이렇다면 다익스트라 계열 알고리즘으로 접근해야한다), 시작 노드에서 모든 노드를 순회하는데, 그 경로 중 최소 비용 경로를 구하는 문제이다. 모든 노드를 순회하는데, 최소 비용이 나오는 경로를 MST (Minimum Spanning Tree , 최소 신장 트리)라고 한다. MST를 구하는 대표적인 알고리즘으로는 프림 알고리즘과, 크루스칼 알고리즘이 있는데, 크루스칼 알고리즘은 union-find 개념을 적용해야하는데, 내가 이것에 익숙치 않아 프림 알고리즘으로 구현하기로 결심했다. 프림 알고리즘은 MST를 찾기..

Algorithm/Baekjoon

[BOJ 1181][백준 1181번] 단어 정렬 (파이썬 풀이)

https://www.acmicpc.net/problem/1181 🤔 문제 설명 및 입출력 ✍ 접근 방법 앞서 풀었던 10814번과 완전 동일한 유형의 문제이다. 참고 : https://spookyjelly.tistory.com/15 1순위 : len(x) / 2순위 : x 로 두고 sort with lambda를 사용하여 정렬 후, 출력한다. 👨‍💻 소스 코드 파이썬 N = int(input()) words = [] for _ in range(N): words.append(input()) words = list(set(words)) # 길이 순 정렬 / 2순위 : 사전 순 정렬 words = sorted(words,key= lambda x : [len(x),x]) for word in words: pr..

Algorithm/Baekjoon

[BOJ 10814][백준 10814번] 나이순 정렬 (파이썬 풀이)

https://www.acmicpc.net/problem/10814 🤔 문제 설명 및 입출력 ✍ 접근 방법 파이썬은 sort 함수가 매우매우매우 잘 만들어져 있다. 팀 소트를 사용해서 속도도 굉장히 빠르고, 정렬의 key 값으로 익명함수 lambda를 적용해서 개발자 입맛대로 정렬을 시킬 수 있다. 쉽게 말해서, 입력을 하나의 리스트로 몰아넣은 다음, sort와 lambda를 이용해서 깔끔하게 정리하면 된다. 👨‍💻 소스 코드 파이썬 N = int(input()) lst = [] for idx in range(N): age,name = input().split() age = int(age) lst.append((age,name,idx)) lst = sorted(lst,key= lambda x : [x[0..

Algorithm/Baekjoon

[BOJ 1865][백준 1865번] 웜홀 (파이썬 풀이)

https://www.acmicpc.net/problem/1865 🤔 문제 설명 및 입출력 ✍ 접근 방법 음수 가중치가 들어가는 그래프 탐색 문제이다 ➡ 벨만-포드 알고리즘을 적용해서 풀자. 사실 이렇게 알고리즘을 뭔가 공식화해서 풀어재끼는게 썩 유쾌하지는 않지만, 그래도 코딩 테스트를 염두해보았을 때,머리 속을 스쳐지나가는 생각들을 단숨에 훅 잡아채는게 유리하다는 생각이 든다. 하지만, 이 문제는 시작점에서 도착점까지의 최소 경로비용을 구하는 순수 벨만-포드 문제가 아니다. 문제의 요지는 백준이가 시간이 줄어들면서, 출발 위치로 돌아오는 것이 가능한지를 물어보기 때문에, 우리는 주어진 그래프에서 벨만-포드 알고리즘이 무한히 반복되는 경우 ( 음수 사이클에 빠지는 경우)를 찾아야한다. 그럼 그 음수 사이..

Algorithm/Baekjoon

[BOJ 10826][백준 10826번] 피보나치 수 4 (파이썬 풀이)

https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 피보나치 수열을 구하는 방법은 여러가지가 있는데, 그 중 가장 대표적인 방법이 재귀 함수로 구현하는 방법과 메모이제이션을 활용한 풀이이다. 나는 DP를 이용해서 풀어봤다. 점화식에 따라, n번째 피보나치 수를 구하기 위해 n-1번째 수와 n-2를 더하는데, n-1번째 수와 n-2를 매번 계산하는 것이 아니라, 저장된 어..