조이의 개발 다이어리

1. 백준 2504 괄호의 값https://www.acmicpc.net/problem/2504 💡 알고리즘 - 구현, 스택- 보통 올바른 괄호 같이 앞의 원소와 짝지어서 올바른 조합인지 확인하는 문제는 스택을 쓴다. 여는 괄호 (, [는 append, 닫는 괄호 ), ]를 pop 해서 올바른 괄호인지 확인하는 방식이다. ✅ 풀이stack = []answer = 0str = input()flag = Falsetemp = 1for i, w in enumerate(str): if w == "(": stack.append(w) temp *= 2 elif w == "[": stack.append(w) temp *= 3 elif w == ")": if not stack or sta..

1. Combine이란?공식문서: https://developer.apple.com/documentation/combineCustomize handling of asynchronous events by combining event-processing operators이벤트 처리 연산자를 결합하여, 비동기 이벤트 처리를 커스터마이징할 수 있는 프레임워크 즉, Apple에서 만든 RxSwift 와 같은 프레임워크라고 할 수 있고, 더 간결하고 다양한 연산자를 활용해 더 다양한 비동기 처리를 할 수 있도록 도와주는 프레임워크이다. 필자는 기존에 RxSwift를 활용하여 비동기 처리를 하는 데 익숙했기에 RxSwift와 비교하여 그 특징을 정리하고, 사용법을 간단하게 정리해보고자 한다. 2. Combine의 3..

1. 문제 - 백준 16562 친구비https://www.acmicpc.net/problem/16562 💡알고리즘 - DFS or 유니온파인드- "친구의 친구는 친구다" 즉, 친구 무리를 짓는다는 점에서 DFS 혹은 유니온파인드를 이용할 수 있다.- 각 친구 무리 별로 친구비가 가장 적은 친구비를 합쳐 준석이가 가진 비용과 비교한다. ✅ DFS 풀이import syssys.setrecursionlimit(10**8)n, m, k = map(int, input().split())money = [0] + list(map(int, input().split()))graph = [[] for _ in range(n+1)]for _ in range(m): v, w = map(int, input().split()..

1. 문제 - 프로그래머스 퍼즐 게임 챌린지 (PCCP 기출 문제)https://school.programmers.co.kr/learn/courses/30/lessons/340212 💡알고리즘 - 파라메트릭 서치(이분 탐색을 이용한 조건에 맞는 값 찾기)- for문으로 1부터 시작하여 문제 조건에 맞는 숙련도(level)을 찾게 도면, diffs 와 times의 길이는 최대 300,000이고diffs는 최대 100,000 이기 때문에 시간복잡도 O(n^2)에 의해 시간초과가 발생한다.- 이럴때 탐색에 있어 시간을 줄여줄 방법론들을 생각해봐야한다. 이분탐색? 투포인터?- 문제에서 diffs[0]는 1로 고정되어있다. 즉, diffs의 최소, 최대값이 명확하며 특정 조건을 만족하는 level의 최소값을 찾..

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