유령이 나오는 젤리하우스

Algorithm/Baekjoon

[BOJ 2512][백준 2512번] 예산 (파이썬 풀이)

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 목표로 하는 어떠한 값이 있고, 그 값을 찾기 위해서 많은 trial && error 가 있을거 같다??? ➡ 이분탐색을 고려해봐라 이분탐색을 사용하기로 결정했으면, 어느 타이밍에 시작값과 끝값을 줄일지를 결정하면 된다. 가편성된 예산을 지방의 예산요청과 비교해보고, 가편성 예산이 크다면 원래 값을 국가예산에서 빼고, 지방예산이 크면 가편성된 예산을 국..

Algorithm/Baekjoon

[BOJ 1629][백준 1629번] 곱셈 (파이썬 풀이)

https://www.acmicpc.net/problem/1629 🤔 문제 설명 및 입출력 ✍ 접근 방법 눈에 보이는대로 풀면 이렇게 쉬운 문제가 없다. 그냥 A*B%C 하면 되는 문제니까 말이다. 근데 정답률을 보아하니 나처럼 생각했다간 큰 코 다치는 문제임이 확실하다. 괜히 S1 난이도를 단게 아닌거 같다. 그래서 구글링을 좀 해보니, O(N) 곱셈을 O(logN)으로 줄여주는 방법인, 분할정복을 이용한 방법으로 해결해야한다고 한다. 단순 곱셈에 어떻게 분할 정복을 적용하나 싶었는데, 생각보다 간단한 아이디어였다. 2^8 계산을 해야한다 해보자. 여태까지 우리는 컴퓨터에게 2*2*2*2*2*2*2*2 를 시켰다. 근데 이 식을 잘 살펴보자. 2^8은 2^4 * 2^4 가 아니던가??? 그럼 2^8 =..

Algorithm/Baekjoon

[BOJ 1043][백준 1043] 거짓말 (파이썬 풀이)

https://www.acmicpc.net/problem/1043 🤔 문제 설명 및 입출력 ✍ 접근 방법 생각보다 고려해야할 사항이 많은 문제이다. 단순히 진실을 아는 사람이 있는 파티에서 거짓말을 안하는게 아니라, 진실이 아는 사람이 있던 파티에 있던 사람이 있는 파티에서도 거짓말을 하면 안된다. 그럼, 진실을 알고 있는 사람의 목록(이하 진알목) 이 지민이가 하나의 파티를 갈때마다 계속 업데이트가 되는 것이다. 하지만 여기서 문제가 발생하는게, 진알목이 업데이트 되었을때, 이전에 진알목에 따라 구라를 말했던 파티에서도 진실을 말해야하게 된다. 그렇다면, 지민이가 한번 파티에 갈 때마다 모든 파티 리스트를 쭉 살펴본 다음, 파티의 멤버와 진알목이 서로 공통분모를 가지고 있나 확인 한 다음, 공통분모를 ..

Algorithm/Baekjoon

[BOJ 1966][백준 1966번] 프린터 큐 (파이썬 풀이)

https://www.acmicpc.net/problem/1966 🤔 문제 설명 및 입출력 ✍ 접근 방법 구현 자체보다 문제를 이해하는게 더 헷갈리는거 같습니다. 문제 자체는 특별한 기교가 있는게 아니라 걍 시키는거 잘하면 됩니다 N의 최대값도 100으로 작으니, 따로 시간 복잡도 고려하지 않고, 생각가는데로 구현하면 되겠다는 생각도 했습니다. 👨‍💻 소스 코드 파이썬 def resort(printer:list)->list: cnt = 0 while True: max_priority = max(printer)[0] first = printer.pop(0) if first[0] != max_priority: printer.append(first) else: # first == max_priority 임 c..

Algorithm/Baekjoon

[BOJ 10989][백준 10989번] 수 정렬하기 3 (파이썬 풀이)

https://www.acmicpc.net/problem/10989 🤔 문제 설명 및 입출력 ✍ 접근 방법 그냥 정렬 문제라고 .sort() 한번 쓰고 출력하면 되는 문제는 절대 아니다. 백준 문제는 항상 단순해보이는 문제가 꼬림한 부분을 감추고 있기 때문이다. 보면 N이 최대 10,000,000개 들어올 수 있다. sort()를 이용하려면 일단 저 10,000,000개의 입력을 받을 리스트를 만들어야하는데, 그 리스트 만들다가 메모리가 터지는 꼴이 눈에 선하다. 그래서 여기서는 꼼수를 쓴다. 주어지는 N개의 숫자를 숫자 그대로 저장하는게 아니라, 이 숫자가 몇개가 들어왔는지 카운트만 하는 용도로만 사용하는 것이다. 이후, 그 카운터에 위치에 맞는 숫자를 카운터의 크기만큼 반복하면서 출력하는 것이다. 말..

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 🤔 문제 설명 및 입출력 ✍ 접근 방법 최초에는 리스트의 앞에서부터 순회하면서, 오늘의 가격이 내일보다 싸다면 구매하고, 아니면 파는 방식으로 구현하려고 했는데, 왠지 단타 한번 쳐볼라고 깝죽대는 내 모습인거 같아서 관뒀다. 그리고 앞에서부터 순회하면 시간 초과가 났다. 하지만 전체 리스트를 순회해야하지 않고서는 문제를 해결할 수 없다고 생각했다. 그래서 발상을 바꿔서, 뒤에서부터 살펴보는 방안을 생각해보았다. 앞에서부터 살핀다면, 오늘보다 비싼 가격이 나올 때까지 값을 계속 저장하고 있어야하는데, 뒤에서부터 살핀다면 지금보다 가격이 낮았을 때만을..