Psychogrammer

🐍 Python/🤔 Algorithm 검색 결과

해당 글 6건

백준 1931번 회의실 배정

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제의 핵심: 회의를 많이 진행하려면 명시적 조건을 뭐로 내걸까? 명시적 조건이란 눈에 '확연히' 보이는, 단순한 조건을 말한다. 생각보다 명시적 조건이 많지 않다. 처음에 생각했던 방법: Brute Force로 모든 경우를 배치해볼까? -> 배치해도 그게 답으로 먀기는 방법은 따른 문제다. 방법1. 회의시간이 가장 짧은 것들을 우선배치할까? -> 순서를 알 수 없기에 기각 방법2. 회의시간이 빠른 것들을 정렬해볼까? -> (1,1000) (2,3) 처럼 회의시간은 빠른데 늦게 끝나면 말짱 도로목 방법3. 회의시..

🐍 Python/🤔 Algorithm 2021. 10. 1. 17:34

탐욕법(Greedy): 체육복

https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr def solution(n, lost, reserve): lost = set(lost) reserve = set(reserve) common = lost & reserve lost = list(lost-common) reserve = list(reserve-common) for i in reserve: if i-1 in lost: lost.remove(i-1) e..

🐍 Python/🤔 Algorithm 2021. 9. 22. 16:17

여행경로: DFD풀이

문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. from collections import defaultdi..

🐍 Python/🤔 Algorithm 2021. 8. 27. 18:00

단어변환: DFS, BFS 풀이

문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로..

🐍 Python/🤔 Algorithm 2021. 8. 26. 21:40

네트워크 DFS, BFS풀이

문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 풀이1 - DFS def DFS(n, computers, visited, i): visited[i] = True for j in range(n): if computers[i][j..

🐍 Python/🤔 Algorithm 2021. 8. 25. 21:33

타겟넘버: DFD풀이

타겟 넘버 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 풀이1 answer = 0 def calc(index, numbers, target, value): global answer; if(index==len(numbers)): if(value==target): answer += 1 return return calc(index+1, numbers, target, value+numbers[index]) calc(inde..

🐍 Python/🤔 Algorithm 2021. 8. 25. 12:41