Cloud.log

[Programmers/알고리즘 고득점 KIT] 포켓몬

[Programmers] 포켓몬Level 1 | #해시문제 바로가기 🔗1. 문제 요약N마리의 포켓몬 중에서 N/2마리를 가져갈 수 있다. 이때 최대한 다양한 종류의 포켓몬을 선택하는 것이 목표이다.포켓몬의 종류 번호가 담긴 배열 nums가 주어질 때, 선택할 수 있는 포켓몬 종류 개수의 최댓값을 구하는 문제이다.2. 접근 방식 및 포인트가장 많은 종류를 선택하려면 중복된 종류를 제거한 뒤, 내가 가져갈 수 있는 수(N/2)와 비교해야 한다.✅ 자료구조: 중복을 허용하지 않는 set을 사용하여 포켓몬의 종류를 파악한다.✅ 로직: 포켓몬 종류의 수(len(set(nums)))가 내가 가질 수 있는 수(len(nums) // 2)보다 크면 N/2를 반환하고, 작으면 종류의 수를 그대로 반환한다.3. 구현 코..

[Programmers/알고리즘 고득점 KIT] 완주하지 못한 선수

[Programmers] 완주하지 못한 선수Level 1 | #해시문제 바로가기 🔗1. 문제 요약수많은 마라톤 선수들이 마라톤에 참여하였다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.참가자 명단(participant)과 완주자 명단(completion)이 주어질 때, 완주하지 못한 선수의 이름을 반환하는 문제이다.2. 접근 방식 및 포인트참가자 중 동명이인이 있을 수 있다는 점이 핵심이다. 단순히 존재 여부만 체크해서는 안 되며, 각 이름별 인원수를 관리해야 한다.✅ 자료구조: Python의 dict(Hash Table)를 활용하여 이름별 인원수를 저장한다.✅ 시간 복잡도: O(n) 이내에 해결해야 한다. participant와 completion을 각각 한 번씩 순회하므로 O(n..

[문제 링크] 👇 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krSolutiondef solution(n): dp = [0] * (n + 1) dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i - 2] + dp[i - 1] return dp[n - 1] % 1234567

[문제 링크] 👉 https://www.acmicpc.net/problem/1303풀이 방법💡 DFS, BFS 이용 📌 주의할 점가로, 세로 확인하가Solutionfrom collections import dequedx = [1, 0, -1, 0]dy = [0, -1, 0, 1]N, M = map(int, input().split())war = [input().strip() for _ in range(M)]visited = [[0] * N for _ in range(M)]W, B = 0, 0def dfs(i, j, color): cnt = 1 visited[i][j] = 1 queue = deque() queue.append((i, j)) while queue: ..

[문제 링크] 👇  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법💡Queue 이용cards1와 cards2를 각각 큐처럼 사용하여, 앞에서부터 단어를 꺼냄goal 배열의 각 단어에 대해해당 단어가 cards1의 맨 앞에 있다면 cards1에서 제거그렇지 않고 cards2의 맨 앞에 있다면 cards2에서 제거두 곳 모두에 없다면 "No"를 반환모든 단어를 성공적으로 처리했다면 "Yes"를 반환Solutionfrom collections import dequedef solution(cards1, cards2, goal): answer = "Yes" cards1 = deque(car..

[문제 링크] 👇  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법photo 에서 한 행씩 꺼내고, 해당 행의 열을 하나씩 꺼내서 이름 리스트에 이름이 있는 경우 점수에 누적시킨다.한 행을 다 돌았으면 점수를 결과 리스트에 추가한다. Solutiondef solution(name, yearning, photo): answer = [] for i in photo: score = 0 for j in i: if j in name: # 해당 이름이 있는 경우 score += yearning[name.index(j)] ..

최소 힙 최소 힙(Min Heap)은 이진 트리 형태의 자료구조로, 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 특성을 갖는 구조이다. O(logn)의 시간 복잡도로 삽입/삭제 가능작은 값을 효율적으로 관리 가능특정 값 삭제, 임의 인덱스 접근이 비효율적. O(n)이 소요됨특징부모 ≤ 자식모든 부모 노드의 값은 자식 노드의 값보다 작거나 같다.가장 작은 값이 루트 노드에 위치.완전 이진 트리트리의 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워져야 함.활용최소 힙은 최솟값을 효율적으로 찾거나 관리해야 하는 상황에서 유용하다.우선순위 큐 구현정렬되지 않은 데이터에서 최솟값 추출데이터 스트림에서 k번째 작은 값 유지 연산삽입 O(log⁡n) 새 데이터를 트리의 가장 아래(왼쪽부터 채움)에..

[문제 링크] 👇 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법1️⃣ 명예의 전당 유지명예의 전당은 k 개의 점수를 유지하며, kkk개를 초과하면 가장 낮은 점수를 제거우선순위 큐(최소 힙)를 활용하면 효율적으로 관리 가능2️⃣ 최하위 점수 추출매번 명예의 전당에서 최하위 점수를 확인하여 기록3️⃣ 점수 처리점수를 하나씩 추가하며 명예의 전당을 업데이트명예의 전당이 가득 차면 최저 점수와 비교 후 대체Solution최소 힙 구현import heapqdef solution(k, score): hall_of_fame = [] # 명예의 전당 (최소 힙) result = [] f..

[문제 링크] 👇 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법1️⃣ 귤의 종류별 개수 파악귤의 크기별로 몇 개씩 있는 개수를 센다. (Counter() 함수 이용)from collections import Countertangerine = [1, 3, 2, 3, 2, 4, 4, 4, 4]print(Counter(tangerine))출력 결과 : Counter({4: 4, 3: 2, 2: 2, 1: 1})2️⃣ 개수를 기준으로 정렬귤의 개수를 내림차순으로 정렬한다. 이는 개수가 많은 종류부터 선택하도록 하기 위함이다.위 예시에서 내림차순으로 정렬하면 [(4, 4), (3, 2), (2, 2)..

투 포인터배열이나 리스트를 탐색할 때, 두 개의 포인터를 사용하여 효율적으로 문제를 해결하는 알고리즘 기법이다. 주로 정렬된 배열에서 특정 조건을 만족하는 값을 찾거나, 구간 합을 계산하는 문제 등에 사용된다.효율적 : 정렬된 배열에서 탐색 시 O(n) 으로 해결 가능간단한 구현 : 포인터 이동만으로 문제 해결 투 포인터 개념포인터(Pointer) : 배열의 특정 인덱스를 가리키는 변수두 개의 포인터를 배열의 양 끝 또는 특정 시작점과 끝점에 두고, 포인터를 이동시키며 문제를 해결 사용 조건배열이 정렬된 경우가 많을 때특정 구간이나 두 값의 합을 계산할 때 효율적으로 탐색할 필요가 있을 때 대표적인 동작 방식시작과 끝 포인터 사용 (양 끝에서 이동)배열의 가장 왼쪽과 오른쪽 끝에 포인터를 둔 뒤, 조건에..

[문제 링크] 👇 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법1️⃣ 정렬  (O(nlog⁡n)시간) 사람들의 몸무게 리스트를 오름차순으로 정렬한다.이렇게 하면 가장 가벼운 사람과 가장 무거운 사람을 효율적으로 짝지을 수 있다.2️⃣ 투 포인터 사용 (O(n) 시간) 리스트의 가장 가벼운 사람(왼쪽 포인터)과 가장 무거운 사람(오른쪽 포인터)을 확인한다.두 사람의 몸무게 합이 보트의 무게 제한을 초과하지 않으면, 두 사람을 한 보트에 태운다(양쪽 포인터를 이동).3️⃣ 혼자 태우기두 사람의 몸무게 합이 무게 제한을 초과하면, 가장 무거운 사람만 보트에 태우고 오른쪽 포인터를 이동한다.4️⃣ ..

[문제 링크] 👉 https://www.acmicpc.net/problem/2460풀이 방법내릴 때는 빼고, 탈 때는 더한다.그리고 연산 결과를 max() 함수를 통해 최댓값을 갱신한다. 최댓값 갱신result = max(result, max_on) Solutionget_off, get_on = [], []for _ in range(10): off, on = map(int, input().split()) get_off.append(off) get_on.append(on)result, max_on = 0, 0for off, on in zip(get_off, get_on): max_on -= off max_on += on result = max(result, max_on)p..

[문제 링크] 👉 https://www.acmicpc.net/problem/3460풀이 방법1️⃣ 이진수 변환format(int(input()), 'b')변환 결과 타입은 정수형이 아닌 str 이다.2️⃣ 뒤집기문자열[::-1]슬라이싱을 이용해 전체를 한번에 뒤집는다. [[파이썬] 이진법, 이진수, 2진수 변환 방법] 🔗 https://dev-cloud.tistory.com/416SolutionT = int(input()) # 테스트 케이스 수for test_case in range(1, T + 1): n = format(int(input()), 'b')[::-1] # 양의 정수 n -> 이진수 변환 -> 뒤집기 result = [] # 결과를 담을 리스트 for i in ..

[문제 링크] 👉 https://www.acmicpc.net/problem/2501풀이 방법약수 구하기N의 약수를 모두 찾기 위해 1부터 N의 제곱근 까지의 수 i를 확인한다.만약 i가 N의 약수라면 i 와 N / i 를 약수 리스트에 추가한다. 이때, i와 N / i 가 같지 않으면 중복을 피하기 위해 둘 다 추가한다.예를 들어 N이 36일 때, 약수로 6이 두 번 나올 수 있기 때문이다.정렬약수를 모두 찾은 후, 작은 순서로 정렬하여 K번째 작은 약수를 찾는다.출력약수의 개수가 K 보다 크거나 같다면, 정렬된 리스트에서 K 번째 약수를 출력한다.약수의 개수가 K 보다 적다면 0을 출력한다.✔️ 정렬 방법sorted(divisor)리스트 혹은 문자열 등을 내장함수로 이용해 정렬할 수 있다.sort()..

[문제 링크] 👇 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com풀이 방법💡 테스트 케이스마다 출력하지 말고 결과를 모아서 한번에 출력하기 (시간 초과 문제) 테스트 케이스 번호와 함께 리스트에 담는 방법results.append(f"#{test_case} DRAW") 저장한 결과를 개행문자와 함께 출력하는 방법print("\n".join(results))SolutionT = int(input()) # 테스트 케이스 수results = [] # 결과를 저장할 리스트for test_case in range(1, T + 1): A, B, C, D = map(int, input().split()) al..