유령이 나오는 젤리하우스

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/Baekjoon

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

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

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 1149][백준 1149번] RGB거리 (파이썬 풀이)

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 DP로 푸는 문제가 확실한데, 아쉽게도 처음 문제를 봤을때는 그런 생각을 못하고 단순한 조합 문제으로 생각했었다. 중복을 허용하는 순열 리스트를 만들어놓고, 매 3번째 입력마다 순열 리스트를 이용해서 최소값을 구하여 지속적으로 결과값에 더해가는 방식으로 접근 했다. 얼핏 보면 괜찮은 접근법이지만, 이 접근법에는 2가지 큰 구멍이 있었다...

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를 매번 계산하는 것이 아니라, 저장된 어..