전체 글

[백준] 1043. 거짓말 - 파이썬

[백준] 1043. 거짓말 - 파이썬 [Gold IV] https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제.. 풀고 보니 Union-Find(Disjoint Set)을 이용해 풀 수 있는 문제였다. 근데 그냥 Set 이용해서 풀린 문제.. ^ㅁ^ 최대 수가 50이라 TLE가 날 일이 별로 없었기에 가능하지 않았나 싶다. 아마 Set의 intersection()과 union()을 이용해서 시간 단축이 좀 된 것 같다. Union-Find를 이용한 풀이..

[백준] 2143. 두 배열의 합 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 부 배열의 합.. -> Prefix Sum! 우선 prefix sum을 구현하기 위해.. Sk (1~k번째 합)를 저장할 배열을 각각 생성. 그 다음이 문제인데... 우선 배열의 원소 조건이 절댓값이 1,000,000을 넘지 않는 정수 이기 때문에.. A[k+1] >= A[k] 가 아니다. 따..

[백준] 17142. 연구소 3 - 파이썬

[Gold III] https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이 문제는... 사실 토마토나, 백조의 호수 같은 문제와 유사한 문제였으나, 시간이 조금 걸렸다. 문제를 푸는 핵심은, '비활성화된 바이러스 또한 전염이 진행될 수 있도록 처리할 것.' 그리고, '비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 고려하지 않아야 할 것.' 이것들을 유념하며 문제를 풀어 나가야 한다. 풀이 1 일단 BFS 문제라..

[백준] 16173. 점프왕 쩰리 (Small) - 파이썬

[Silver IV] https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 풀이 N = int(input()) q = [] board = [] for _ in range(N): board.append(list(map(int, input().split()))) q.append([0, 0]) while q: row, col = q.pop() a = board[row][col] if a == -1: print("HaruHaru") exit() if a == ..

[백준] 9095. 1, 2, 3 더하기 - 파이썬

[Silver III] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 간단한 Dynamic Programming 문제. n이 11보다 작다 는 조건이 걸려 있어, Top-Down 방식으로 재귀를 이용해 풀어도 시간초과나, Recursion 기본 횟수(1000회) 제한에 걸리지 않을 법 한 문제였다. [정수 k를 1, 2, 3의 합으로 나타내는 방법의 수] = [k-1을 나타내는 방법의 수] + [k-2을 나타내는 방법의 수] + [k-3을 나타내는 방법의 수] 라는 것만 캐치한다면, Bottom-Up 방식으로 Memoization 하며..

[프로그래머스] 1,2,3 떨어트리기 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150364. 1,2,3 떨어트리기 [Lv. 4] https://school.programmers.co.kr/learn/courses/30/lessons/150364 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 읽고 처음에는, DFS - Backtracking 문제인가? 생각했음. 일단, 완전히 뇌 빼고 Brute-Force로 풀어내기에는 3^100 이니까 될 수가 없고, 그런데 생각해보니까 Backtracking으로 간다고 해도 [1,1,1, ...] 부터 쭉 시작하는 거니까, com..

[프로그래머스] 표 병합 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150366. 표 병합 [Lv. 3] https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1 일단 50x50 셀이라는 부분에서, UPDATE value1 value2 명령어 자체는 Brute-Force로 해결할 수 있다는 생각이 들었고, 결국 MERGE 와 UNMERGE 를 처리하는 것이 관건인 것 같았다. 사실 보자마자 떠오른 방법은 Union-Find를 이용하는 것이였는데, 그냥 모..

[프로그래머스] 이모티콘 할인행사 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150368. 이모티콘 할인행사 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선, 문제를 다 읽자마자 확인한 것은- "Brute-Force로 해결할 만 한가?" 였다. 이모티콘의 각 할인율은 10%, 20%, 30%, 40% 중 하나이고, 1 ≤ emoticons의 길이 = m ≤ 7 에서 볼 수 있듯, 이모티콘이 최대 7개이므로, 7^4 = 2041가지 경우의 ..