유령이 나오는 젤리하우스

Algorithm/Baekjoon

[BOJ 1920][백준 1920번] 수 찾기 (파이썬 풀이)

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 문제는 N개의 수로 이루어진 리스트 A를 주고, M개의 수로 이루어진 리스트 B(가칭)을 줍니다. 그리고 B의 각 요소들이 A에 포함되어있는지를 확인해서, 존재한다면 1을 출력하고, 그렇지 않다면 0을 출력합니다. 보다시피 구현해야할 기능은 매우 간단합니다. 그냥 검색만 잘하면 끝!!!! 그렇다면, 리스트 B의..

Algorithm/Baekjoon

[BOJ 2156][백준 2156번] 포도주 시식 (파이썬 풀이)

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 "이번에 내가 포도주를 마시는게 이득인가? 아니면 존버했다가 다음에 마시는게 이득인가?" 라는 물음에 답할 수 있는 프로그램을 구현하는 것이 목표인 문제입니다. 언제 마시는게 최선의 선택이 되는지를 파악하려면 내가 여태까지 마신 와인의 상태를 저장하고 있어야합니다. 예를 들면 , N 번째 와인에 도달했을 때의 선택지는 아래와 같습니다 N-1번째 와인은 마셨는데..

Algorithm/SWEA

[SWEA 1859번] 백만 장자 프로젝트 (파이썬 풀이)

문제 바로 가기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🤔 문제 설명 및 입출력 ✍ 접근 방법 최초에는 리스트의 앞에서부터 순회하면서, 오늘의 가격이 내일보다 싸다면 구매하고, 아니면 파는 방식으로 구현하려고 했는데, 왠지 단타 한번 쳐볼라고 깝죽대는 내 모습인거 같아서 관뒀다. 그리고 앞에서부터 순회하면 시간 초과가 났다. 하지만 전체 리스트를 순회해야하지 않고서는 문제를 해결할 수 없다고 생각했다. 그래서 발상을 바꿔서, 뒤에서부터 살펴보는 방안을 생각해보았다. 앞에서부터 살핀다면, 오늘보다 비싼 가격이 나올 때까지 값을 계속 저장하고 있어야하는데, 뒤에서부터 살핀다면 지금보다 가격이 낮았을 때만을..

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..