조이의 개발 다이어리

1. 문제 - 백준 17142 연구소 3 (삼성 SW 역량테스트 기출)https://www.acmicpc.net/problem/17142 💡알고리즘 - BFS + 조합- 연구소에 있는 모든 바이러스들 중, m개를 활성 상태로 변경했을 때의 모든 경우의 수에서 빈칸에 바이러스가 퍼지는 최소 시간 -> 조합(from itertools import combinations 활용)- 그래프 + 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간 -> BFS ✅ 풀이from itertools import combinationsfrom collections import dequeimport sysn, m = map(int, input().split()) # m개의 바이러스를 활성상태로 둘 수 있음board = [] ..

1. 문제 - 프로그래머스 스티커 모으기(2)https://school.programmers.co.kr/learn/courses/30/lessons/12971 💡알고리즘 - DP- 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 라는 문장에서 이전 항목을 활용하여 최적의 해를 만들어낸 다는 점에서 DP 알고리즘을 유추할 수 있다. ✅ 풀이def solution(sticker): answer = 0 n = len(sticker) if n - 2차원 배열을 만들어서 dp[0][i]은 첫 번째 스티커를 뗀 경우, dp[1][i]은 첫 번째 스티커를 떼지 않은 경우의 합이라고 정의했다.2차원 배열을 만들지 않아도 d..

1. 문제 - 프로그래머스 석유 시추(PCCP 기출문제)https://school.programmers.co.kr/learn/courses/30/lessons/250136 💡알고리즘 - DFS/BFS- 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리 ==> 그래프탐색을 통한 영역 짓기 ✅ 풀이import syssys.setrecursionlimit(10**6) # 재귀 깊이를 늘려줘야 런타임 에러가 안뜸def solution(land): answer = 0 n = len(land) # n: 세로길이 - x m = len(land[0]) # m: 가로길이 - y visited = [[False] * m for _ in range(n)] dx = [-1, 1, 0, ..

1. 문제 - 백준 1339 단어수학https://www.acmicpc.net/problem/1339 💡 알고리즘: 그리디예시 2인 사례를 보면,입력: 2GCFACDEB출력:99437 A -> 9, C -> 8, D -> 7 .. 이런식으로 자리수가 가장 큰 알파벳 순서대로 큰 수를 대입한 경우가 곧 그 수의 합을 최대로 만드는 것이고,자릿수가 큰 순서대로 큰 수를 고르는 것이 곧 최적의 답을 보장하므로, (상황마다 가장 큰 수를 선택함) 그리디 알고리즘이라고 생각할 수 있다. ✅ 풀이from collections import defaultdictdic = defaultdict(int) # 각 알파벳의 자리수를 저장할 딕셔너리n = int(input())for _ in range(n): word ..

1. 문제 - 백준 마법사 상어와 파이어볼 (삼성 SW 역량테스트 기출)https://www.acmicpc.net/problem/20056 ✅ 풀이- 파이어볼의 이동을 'infos'라는 배열로 두고 각 상태별로 파이어볼의 좌표, 질량, 방향 등을 저장한다.- 또한 이동하기 전에 remove를 통해 비워준다.N, M, K = map(int, input().split()) # n: 격자크기 m: 파이어볼 갯수, k: 명령한 횟수dx = [-1, -1, 0, 1, 1, 1, 0, -1] # 사진의 0 ~ 8의 방향대로 이동할 offset 배열dy = [0, 1, 1, 1, 0, -1, -1, -1]board = [[[] for _ in range(N)] for _ in range(N)]infos = []..

1. 문제 - 백준 미세먼지 안녕! (삼성 SW 역량테스트 기출)https://www.acmicpc.net/problem/17144 ✅ 풀이answer = 0r, c, t = map(int, input().split())machine = []board = []for i in range(r): board.append(list(map(int, input().split()))) for j in range(c): if board[i][j] == -1: # 공기청정기의 위치 저장 machine.append((i, j))def spread():def purifying(): for _ in range(t): # t초만큼 반복 spread() purifying()for ..

1. 문제 - 백준 아기상어 (삼성 SW 역량테스트 기출)https://www.acmicpc.net/problem/16236 💡 문제 접근 방식 BFS + 시뮬레이션/구현 문제이다.거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값처음에 이부분을보고 "거리"는 아기 상어의 좌표와 물고기가 있는 좌표 거리의 절댓값을 구하면 되지 않나? 생각했지만 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.- 지나갈 수 있는 조건을 명시해줬기에, 아 이 문제는 물고기가 더이..

1. 문제 - 프로그래머스 숫자게임https://school.programmers.co.kr/learn/courses/30/lessons/12987 💡 문제 접근 방식본래라면 A팀의 각 원소마다 더 큰 원소들을 찾아 그 합계를 구하려면, 이중 반복문이 되지만 A와 B는 1이상 100,000 이하이기 때문에 시간초과가 발생한다.따라서 기존 시간초과 발생 코드를 O(N)을 통해 효율적으로 찾을 수 있게 해주는 투포인터 알고리즘을 사용한다. ✅ 풀이def solution(A, B): A.sort() # 차례대로 움직이며 B가 A보다 더 큰 원소를 찾아야하므로, 둘다 오름차순으로 정렬한다. B.sort() answer = 0 idx_A, idx_B = 0, 0 whil..

1. 문제 - 프로그래머스 [1차] 뉴스 클러스터링https://school.programmers.co.kr/learn/courses/30/lessons/17677 💡 문제 접근 방식자카드 유사도란, A와 B 집합의 교집합 크기 / A와 B 집합의 합집합 크기이다.이때 주의할 점은 다중집합이기 때문에 중복되는 원소는 제거되는 것이 아니라 집합에 그대로 남아있다. 문제의 예시를 보면A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면,교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로,자카드 유사도 J(A, B) = 3/7 교집합에는 A와 B 집합 모두 들어있는 원소는 각 집합의 해당 원소의 갯수의 최소값 ..

1. 문제 - 프로그래머스 조이스틱https://school.programmers.co.kr/learn/courses/30/lessons/42860 이 문제는 다른 사람의 풀이를 보고 이해해보고자했다. ✅ 풀이def solution(name): answer = 0 n = len(name) for ch in name: # 1) if (ch != 'A'): min_up_down = min(ord(ch) - ord('A'), 26 - (ord(ch) - ord('A')) answer += min_up_down move = n - 1 # 2) for left in range(n): idx = ..