Algorithm

[백준] 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가지 경우의 ..

[프로그래머스] 개인정보 수집 유효기간 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150370. 개인정보 수집 유효기간 [Lv. 1] https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 딱히 설명할 부분은 없는 Lv. 1 문제. String Slicing과, 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며, 1 이상 100 이하입니다. 라는 설명에 주의하며, month -= 12, year += 1 을 만족할 때까지 반복해줘야 함에만 신경써주면 될 것..

[프로그래머스] 미로 탈출 명령어 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150365. 미로 탈출 명령어 [Lv. 3] https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선, 'impossible'을 출력해야 하는 경우를 먼저 알아보자.. 간단하게 생각해 보면, 출발지에서 도착지까지 도달할 수 있는 최소 거리를 h라 했을 때, k = h+(0을 포함한 짝수) 여야 어떻게든 도달할 수 있다. 따라서, k보다 h가 작은 경우나, k = h + (홀수) 인 경..