조이의 개발 다이어리

[Python] 백준 미세먼지 안녕!

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 ..

[Python] 백준 아기상어

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

[Python] 프로그래머스 숫자게임, 백준 청소년 상어

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..

[Python] 프로그래머스 - [1차] 뉴스 클러스터링

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 = ..

1. 문제 - 프로그래머스 외벽 점검https://school.programmers.co.kr/learn/courses/30/lessons/60062 ✅ 풀이from itertools import permutationsdef solution(n, weak, dist): answer = 9 # 1) _len = len(weak) for i in range(_len): # 2) weak += [weak[i] + n] # 3) 모든 취약점 위치를 시작점으로 하여 각 친구가 취약 지점들을 커버할 수 있는지 확인함 for i in range(_len): for friend in permut..

1. 문제 - 백준 2011 암호코드https://www.acmicpc.net/problem/2011 이 문제는 DP (다이나믹 프로그래밍, 동적 계획법) 로 풀 수 있다.첫번째 예시인 25114를 고려해보면 2, 25, 251, 2511, 25114.. 로 진행하면서 각각 암호화할 수 있는 문자가 이전 문자를 사용해서 만들 수 있다는 점에서 짐작할 수 있다. ✅ 풀이 과정1) 첫번째 예시인 25114의 정답이 6으로 나오는 과정을 살펴보면, 2/5/1/1/425/1/1/425/11/425/1/142/5/11/42/5/1/14 여기서 반복문을 통해 차례대로 수를 방문했을 때,현재 인덱스에서 10부터 26까지의 수로 만들 수 있는지 없는지에 따라서 경우의 수가 추가됨을 알 수 있다.이를 유의하며 경우의 수..

1. 문제 - 프로그래머스 다리를 지나는 트럭https://school.programmers.co.kr/learn/courses/30/lessons/42583 해당 문제는 큐를 활용하여 푸는 문제다.예시에서 대기 트럭 - 다리를 건너는 트럭 - 다리를 지난 트럭으로 움직이는 상황을 보면 먼저 들어간 데이터가 먼저 빠져나오는 (선입선출) 형태에서 큐 자료구조를 활용하는 문제임을 짐작할 수 있다. ✅ 풀이from collections import dequedef solution(bridge_length, weight, truck_weights): bridge = deque([0] * bridge_length) # 다리 위 상태 (처음엔 트럭 없음 → 0으로 채움) answer = 0 # 경과 ..

1. 문제 - 프로그래머스 체육복https://school.programmers.co.kr/learn/courses/30/lessons/42862 ❓해당 문제가 그리디인 근거1) 최대한 많은 학생에게 체육복을 빌려주어야한다 --> "최대 이익" 키워드2) 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다 --> 잃어버린 학생과 여벌이 있는 학생을 둘다 정렬함으로써, 빌려줄 수 있는 체육복을 순차적으로 빌려주는 것이 곧 최대 이익을 보장한다def solution(n, lost, reserve): _reserve = sorted([r for r in reserve if r not in lost]) # 1 _lost = sorted([r for r in lost if r not..

1. 문제 - 프로그래머스 섬 연결하기https://school.programmers.co.kr/learn/courses/30/lessons/42861 해당 문제는 유니온-파인드, 그리디 알고리즘을 사용하여 풀이할 수 있는 문제이다. 1) 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소 비용으로 모든 섬이 서로 통행할 수 있도록 함 --> 그리디2) 섬과 섬 간의 연결관계가 있을 때, 모두를 통행(하나의 집합으로 만들기)하도록 한다 --> 유니온-파인드3) 비용을 최소화 하기 위해, 다리를 추가 시 사이클을 형성하지 않도록 한다 --> 파인드를 통해 사이클 판단 *사이클이란, 집합 내 노드끼리 순환하는 구조를 의미한다.- 집합 내 각 노드의 부모 노드가 모두 같을 경우, 사이클을 이룬다고 말할 수 ..