프로그래머스
99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기)
99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기)
2024.11.22https://www.acmicpc.net/problem/9655오늘의 학습 키워드 : DP 공부한 내용DP처음 문제를 보자마자 생각한건.. 이건 무슨 알고리즘인가? 이러고서는 그냥 규칙부터 찾았다.N이 짝수인지 홀수인지에 따라 출력이 달라진다고 생각했다. 짝수인 경우에는 창영이가 이겨서 "CY" 홀수인 경우에는 상근이가 이겨서 "SK이 문제에서 상근이와 창영이는 한 번의 차례에 돌을 1개 또는 3개씩 가져갈 수있는데... 1과 3은 모두 홀수이기 때문에:처음 돌의 개수가 홀수이면, 홀수 차례에 상근이가 마지막 돌을 가져감.처음 돌의 개수가 짝수이면, 짝수 차례에 창영이가 마지막 돌을 가져감.1️⃣ 처음 풀이import sysN = int(sys.stdin.readline().strip())#짝수 lik..
99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기)
99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기)
2024.11.20https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘의 학습 키워드 : 완전탐색공부한 내용처음 문제를 보자마자 생각한건,1. BFS 이용하여 한쪽 서브트리의 노드 개수 계산:간선 하나를 제거하면 트리가 두 개의 서브트리로 나뉜다. 이때, BFS 알고리즘을 사용하여 한쪽 서브트리에 속한 송전탑의 개수를 계산2. 나머지 서브트리의 노드 개수 계산:트리 전체의 송전탑 개수가 n이므로, 나머지 서브트리의 노드 개수는 n에서 앞서 BFS로 계산한 노드 개수를 뺀 값그렇게 계산된 값을 (1-2)를 이용해..
99클럽 코테 스터디 23일차 TIL - 완전탐색(프로그래머스- 소수찾기)
99클럽 코테 스터디 23일차 TIL - 완전탐색(프로그래머스- 소수찾기)
2024.11.20https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘의 학습 키워드 : 완전탐색공부한 내용여러 개의 소수를 구해야 한다면? 에라토스테네스의 체를 사용.단일 숫자의 소수 여부를 판별한다면? 간단한 나눗셈 방식을 사용(숫자 n에 대해 2부터 √n까지 나눠보고, 나누어떨어지지 않으면 소수.)즉, 이문제는 숫자 조합의 범위가 그렇게 크지 않으므로 간단한 나눗셈 방식으로 사용해도 괜찮다..1️⃣ 간단한 나눗셈 방식 사용한 경우def is_prime(n): """소수 판별 함수: n이 소수인지 확인..
99클럽 코테 스터디 22일차 TIL - 완점탐색,백트래킹 (프로그래머스- 피로도)
99클럽 코테 스터디 22일차 TIL - 완점탐색,백트래킹 (프로그래머스- 피로도)
2024.11.18https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘의 학습 키워드 : 완전탐색,백트래킹?공부한 내용 1️⃣ 처음 쓴 풀이법#처음 쓴 풀이법def permutations(elements,k,dungeons,current=[]): if not elements or k =dungeons[elements[i]][0]: print(max_len,current) max_len = max(max_len, permutations( ne..
99클럽 코테 스터디 21일차 TIL - 완점탐색 (프로그래머스- 카펫)
99클럽 코테 스터디 21일차 TIL - 완점탐색 (프로그래머스- 카펫)
2024.11.18https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘의 학습 키워드 : 완전탐색1. 약수 구하기 : total = 24라면 약수는 1, 2, 3, 4, 6, 8, 12, 242. if (width - 2) * (height - 2) == yellow : return [width, height]공부한 내용 def solution(brown, yellow): answer = [] total = brown + yellow for height in range(1,int(total**0..
99클럽 코테 스터디 20일차 TIL - 완점탐색 (프로그래머스- 모의고사)
99클럽 코테 스터디 20일차 TIL - 완점탐색 (프로그래머스- 모의고사)
2024.11.16https://school.programmers.co.kr/learn/courses/30/lessons/42840 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘의 학습 키워드 : 완전탐색1. 수포자 패턴 반복 찾아내기2. 반복 비교하여 점수 +1 : pattern[j % len(pattern)]3. 최고 점수를 가진 사람 찾아내기 공부한 내용 def solution(answers): # 각 수포자의 찍는 패턴 patterns = [ [1, 2, 3, 4, 5], # 1번 수포자 [2, 1, 2, 3, 2, 4, 2, 5], # 2번 수포자 [3, ..
99클럽 코테 스터디 19일차 TIL - 그리디 (백준1374 - 강의실)
99클럽 코테 스터디 19일차 TIL - 그리디 (백준1374 - 강의실)
2024.11.15https://www.acmicpc.net/problem/1374오늘의 학습 키워드 : 그리디문제 설명시작한 시간으로 정렬[3, 2, 14], [1, 3, 8], [8, 6, 27], [5, 6, 20], [2, 7, 13], [4, 12, 18], [6, 15, 21], [7, 20, 25]강의실 12 ~ 1420 ~ 25강의실 23 ~ 812 ~ 18강의실 36 ~ 27 강의실 46~20 강의실 5 7 ~ 1315 ~ 211. 정렬 : 강의의 시작 시간을 기준으로 오름차순 정렬2. 우선순위 큐(힙) 활용: 각 강의실의 가장 빠른 종료 시간을 추적3-1. 강의 시작 시간 ≥ 가장 빠른 종료 시간기존 강의실 재사용 (heappop)-> 강의 종료 시간 추가(heappush)새 강의가 이전 강의 이후에 ..
99클럽 코테 스터디 17일차 TIL - 그리디 (백준31926 - 밤양갱)
99클럽 코테 스터디 17일차 TIL - 그리디 (백준31926 - 밤양갱)
2024.11.13https://www.acmicpc.net/problem/2847오늘의 학습 키워드 : 그리디문제 설명N=28번 : d, a, l, d, i, dal, g, o9번 : d, a, l, d, i, dal, g, o, daldidalgo10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldida11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldida, nN=38번 : d, a, l, d, i, dal, g, o9번 : d, a, l, d, i, dal, g, o, daldidalgo10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldida11번 : d, a, l, d, i, dal, g, ..
99클럽 코테 스터디 16일차 TIL - 그리디 (백준2847 - 게임을 만든 동준이)
99클럽 코테 스터디 16일차 TIL - 그리디 (백준2847 - 게임을 만든 동준이)
2024.11.12https://www.acmicpc.net/problem/2847오늘의 학습 키워드 : 그리디문제 설명예제1번으로 설명하면35553345이런형태로 만들겠다5-3 = 25-4 = 12+1 = 3 이 필요하다.1. 뒤에서부터 순차적으로 접근2. 조건에 맞게 점수 감소 횟수 계산: 각 레벨을 순차적으로 비교하면서, 만약 현재 레벨의 점수가 다음 레벨의 점수보다 크다면, 두 점수의 차이만큼 감소 3. 점수 감소는 최소 : 각 단계에서 현재 레벨의 점수가 다음 레벨보다 하나 작아지도록 조정하는 것( ex. 7 -> 5 이형태면 7--> (5-1)의 값으로 되어야한다. ) 공부한 내용 import sysn = int(sys.stdin.readline().strip())scores = [int(sys.stdin.re..
99클럽 코테 스터디 15일차 TIL - 그리디 (백준13417 - 카드 문자열)
99클럽 코테 스터디 15일차 TIL - 그리디 (백준13417 - 카드 문자열)
2024.11.11https://www.acmicpc.net/problem/13417오늘의 학습 키워드 : 그리디1. 덱 초기화:첫 번째 카드는 그대로 덱(초기값 설정)2. 카드를 덱의 왼쪽 또는 오른쪽에 추가: 2-1. c 2-2. c > queue[0]: 새 카드가 더 크면 덱의 오른쪽에 추가3. 덱을 문자열로 변환 후 출력 : ''.join(queue)를 사용해 문자열로 합치고 출력공부한 내용 - 덱으로 생각했던 이유 : 양쪽 끝에서 빠르게 원소를 추가import sysfrom collections import deque# 테스트 케이스 수를 입력받음T = int(sys.stdin.readline().strip())# 각 테스트 케이스에 대해 처리for i in range(T): # 카드의 개수를 ..
99클럽 코테 스터디 14일차 TIL - 그리디 (백준14916 - 거스름돈)
99클럽 코테 스터디 14일차 TIL - 그리디 (백준14916 - 거스름돈)
2024.11.10https://www.acmicpc.net/problem/14916오늘의 학습 키워드 : 그리디공부한 내용 import sysdef min_coins(n): # 5원짜리 동전의 최대 개수를 구합니다. count_5 = n // 5 while count_5 >= 0: # 5원짜리를 최대한 사용한 후 남은 금액을 2원짜리로 채울 수 있는지 확인 remaining = n - (count_5 * 5) if remaining % 2 == 0: count_2 = remaining // 2 return count_5 + count_2 count_5 -= 1 # 5원과 2원으로 정확히 맞출 수 ..
99클럽 코테 스터디 13일차 TIL - 그리디,이분탐색 (백준27961 - 고양이는 많을수록 좋다)
99클럽 코테 스터디 13일차 TIL - 그리디,이분탐색 (백준27961 - 고양이는 많을수록 좋다)
2024.11.09https://www.acmicpc.net/problem/27961오늘의 학습 키워드 : 그리디..? 이분탐색?공부한 내용 import sys# 최소 동작 수를 계산하는 함수 정의def min_actions(N): actions = 0 # 2의 actions 제곱이 N 이상이 될 때까지 actions 증가 while 2 ** actions import sys# 입력 값 N을 받음N = int(sys.stdin.readline().strip())# 이진 탐색 범위 설정# 2**10 ≈ 10**3 이므로 2**40 ≈ 10**12 정도로 충분히 큰 범위를 잡음start, end = 0, 40result = 0# 이진 탐색을 통해 2의 몇 제곱이 N 이상인지 찾기while start = N: ..
99클럽 코테 스터디 12일차 TIL - BFS (백준7569- 토마토)
99클럽 코테 스터디 12일차 TIL - BFS (백준7569- 토마토)
2024.11.08https://www.acmicpc.net/problem/7569오늘의 학습 키워드 : BFS1. BFS로 최소 일수 계산2. 초기 상태에서 익은 토마토를 큐에 넣기3. 6방향 탐색문제의 조건에 따라 위, 아래, 왼쪽, 오른쪽, 앞, 뒤의 6방향4. 최대 일수 갱신BFS를 진행하면서 days 변수를 매 단계 갱신하며, 모든 토마토가 익을 때까지 걸린 최대 일수를 기록 최종적으로 모든 토마토가 익었을 때 max_days가 최소 일수5. 최종 상태 체크(토마토가 모두 익지 않았는지 익었는지 체크 필요)- 만약 남아있다면, -1을 출력하고 종료하여 불가능한 경우를 처리- 반면 , 모든 토마토가 익었다면, max_days를 출력합니다.공부한 내용 import sysfrom collections import de..
99클럽 코테 스터디 8일차 TIL - DFS&BFS (백준2644- 촌수계산)
99클럽 코테 스터디 8일차 TIL - DFS&BFS (백준2644- 촌수계산)
2024.11.04https://www.acmicpc.net/problem/2644오늘의 학습 키워드 : DFS & BFS공부한 내용 예제1예제2DFS로 푼 경우import sys# 입력 처리n = int(sys.stdin.readline().strip()) # 총 사람의 수a, b = map(int, sys.stdin.readline().strip().split()) # 촌수를 계산할 두 사람m = int(sys.stdin.readline().strip()) # 관계의 수graph = [[] for _ in range(n + 1)] # 각 사람의 관계를 나타내는 인접 리스트# 관계 정보 입력for i in range(m): x, y = map(int, sys.stdin.readline().strip().sp..
99클럽 코테 스터디 7일차 TIL - (프로그래머스 - 모음사전)
99클럽 코테 스터디 7일차 TIL - (프로그래머스 - 모음사전)
2024.11.03프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘의 학습 키워드 : 브루트 포스이론,,?공부한 내용 def solution(word): # 사전 순서대로의 모음 리스트 vowels = ['A', 'E', 'I', 'O', 'U'] # 각 자리에서 한 글자가 바뀔 때 뒤에 따라붙는 가능한 단어의 수 (가중치) # 첫 번째 자리의 가중치는 5^4 + 5^3 + 5^2 + 5^1 + 5^0 = 781 # 두 번째 자리의 가중치는 5^3 + 5^2 + 5^1 + 5^0 = 156 # 세 번째 자리의 가중치는 5^2 + 5^1 + 5^0 = 31 # 네 번째 자리의 ..