조이의 개발 성장 다이어리

[Python] 프로그래머스 그리디 문제 (체육복, 단속 카메라, 큰 수 만들기, 기지국 설치)

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

[Python] 프로그래머스 섬 연결하기

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

1. 문제 - 백준 20058 마법사 상어와 파이어스톰https://www.acmicpc.net/problem/20058 시뮬레이션, 빡구현 문제는 먼저 기능 별로 함수로 나누는게 중요하다. * 문제에서 설명하는 파이어스톰 분석1) 단계 L 을 입력받는다. 마지막 줄에 L1, L2, ... LQ가 Q개만큼 주어지고, Q번만큼 마법을 시전함2) 2^N X 2^N 격자의 얼음판에서 2^L X 2^L 격자로 나누어, 각 격자의 모든 부분을 90도 회전시킨다.3) 이후 얼음이 있는 칸 3개 또는 그 이상과 인접하지 않은 칸은 얼음의 양이 1 줄어든다. 여기서 반복하는 기능을 함수화하면 된다.1. 2^L X 2^L 격자로 나누어, 각 격자의 모든 부분을 90도 회전하기, 2. 인접한 칸이 얼음이 있는 칸이 3개 ..

1. 문제 - 프로그래머스 등굣길https://school.programmers.co.kr/learn/courses/30/lessons/42898 해당 문제는 DP로 풀이할 수 있다. 이유는- 완전 탐색으로 풀기에는 경우의 수가 너무 많고,- 집에서 학교까지 도착하기까지의 시작과 종료 지점이 명확히 존재하며- 최단경로의 개수는 이전 경로에서 가져와서 해를 구할 수 있기 때문이다. ❌ 틀린 풀이def solution(m, n, puddles): dp = [[0] * m for _ in range(n)] for i in range(n): for j in range(m): if [j+1, i+1] in puddles: continue..

1. 문제 - 프로그래머스 가장 큰 정사각형 찾기https://school.programmers.co.kr/learn/courses/30/lessons/12905# 해당 문제는 다이나믹 프로그래밍(DP)로 풀이할 수 있다. 1) 행과 열이 각각 최대값이 1000임--> 행과 열을 반복하며 1을 마주칠때마다 정사각형을 이루는지 판단하려면 반복문이 하나 더 들어가야하는데, 최악의 경우 시간복잡도가 1000^3 = 10^9이 넘어갈 수 있다.--> 코딩테스트에서는 일반적으로 1억 = 10^8번 연산을 기준으로 판단하므로, 시간초과가 발생한다.--> 완전탐색으로 풀이할 수 없어서 다른 알고리즘을 생각해야함 2) 만들 수 있는 최대 정사각형이므로 예를들어 3x3인 정사각형을 만들 수 있는 위치의 경우 2x2인 정..

1. 문제 - 백준 1283https://www.acmicpc.net/problem/1283 ✅ 풀이n = int(input())keys = []for _ in range(n): words = input() answer = "" for i, w in enumerate(words): # 1. 단어의 첫글자가 이미 단축키로 지정되어있는지 확인하고 # 여기서 단축키는 대소문자를 구분하지 않으므로 upper 혹은 lower로 통일하여 key 리스트에 추가한다. if (i == 0 and w.upper() not in keys) or (words[i-1] == " " and w.upper() not in keys) and "[" not in answer: # "[" not ..

안녕하세요 ~! SwiftUI를 공부하던 중, NavigationView가 iOS 16 이후로 deprecated 되고NavigationStack으로 대체된 것을 알게되어 어떤 점이 다르고, 어떻게 바뀌었는지를 정리해보고자 합니다. * 공식문서: https://developer.apple.com/documentation/swiftui/navigationview NavigationView | Apple Developer DocumentationA view for presenting a stack of views that represents a visible path in a navigation hierarchy.developer.apple.com 1. NavigationView란?- 기존 UIKit의 U..

1. 문제 - 프로그래머스 할인행사https://school.programmers.co.kr/learn/courses/30/lessons/150368 ✅ 풀이모든 이모티콘마다 모든 할인률을 적용하여 케이스를 따지면 된다.users의 길이는 최대가 100, 할인율은 10/20/30/40으로 4개, emotion의 길이는 7개이므로 완전탐색이 가능하다. def solution(users, emoticons): answer = [] discount_list = [10, 20, 30, 40] # 할인율은 10, 20, 30, 40으로 설정 combinations = [] # 각 이모티콘 별 모든 할인률 조합 def dfs(arr, depth): if len(..

1. 문제 - 백준 5052 전화번호 목록https://www.acmicpc.net/problem/5052 ✅ 내 풀이from collections import defaultdictt = int(input())for _ in range(t): dic = defaultdict(int) words = set() # 15번째 줄에서 단어 찾을떄 시간복잡도 줄이기 위해 set 사용 (탐색 -> O(1)) flag = False n = int(input()) for _ in range(n): number = input() words.add(number) # 단어들 set에 추가 for i in range(1, len(number)+1): # 가능한 모든 ..

1. 문제 - 프로그래머스 기둥과 보 설치https://school.programmers.co.kr/learn/courses/30/lessons/60061 ❌ 틀린 풀이- 테스트 케이스는 통과하는데 제출했을 때 테스트 6, 7만 통과함import copydef solution(n, build_frame): board = [[-1] * (n+1) for _ in range(n+1)] def isValid(board): for i in range(n+1): for j in range(n+1): if board[i][j] == 0: # 기둥일 경우 # 바닥 위에 있거나 보의 한쪽 끝 부분 위에 ..