느낌표 공장

문제 https://www.acmicpc.net/problem/1325 해킹한 컴퓨터 이므로 방문 개수를 반환 return sum(visited) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): com1, com2 = map(int, input().split()) graph[com2].append(com1) # com2에서 com1을 감염 시킬(방문 할) 수 있다. answer = [] max_v = 0 for i in range(1, n+1): tmp_v = bfs(i) if max_v < tmp_v: # 해킹할 수 있는 컴퓨터 수가 더 많은 경우 answer = [i] # 배열 초기화 max_v =..

문제 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 풀이 과정 1931번 회의실 배정 문제가 떠오르는 문제였다. 처음에는 회의실이 없다면 새로 만들고 회의실마다 시간을 비교해주면서 계산하는 2중 for문을 생각했는데 그렇게 하면 시간 초과가 날 것 같아 고민을 했다. 가장 먼저 끝나는 곳을 찾고 비교하는 것이 관건이었으므로 최솟값과 최댓값을 빠르게 찾는 heap이 생각나 이를 사용하여 해결할 수 있었다. 회의 끝나는 시간을 heap에 넣고..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 처음 단어에서 목표하는 단어까지 주어진 단어들을 활용하여 최소 변환을 해야 하는 문제이다. (변환을 할 수 없다면 0 반환) 따라서 최단 경로 탐색에 적합한 BFS를 활용하여 문제를 해결하였다. 코드 과정은 다음과 같다. 처음 시작 단어와 0(단어 변환 횟수)을 queue에 넣는다. queue에서 맨 처음에 있는 단어와 횟수를 뽑는다. 주어진 단어들의 집합에서 아직 사용하지 않은 ..

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 과정 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구해야 하므로, 공장 두 곳을 이은 다리들 중 중량 제한이 더 큰 다리를 건너는 것이 좋다. 따라서 입력받은 다리 정보들을 다리의 중량 제한을 기준으로 하여 내림차순으로 정렬하고, 다익스트라를 사용하되 힙에 push 할 때, 중량을 마이너스를 붙여 push 하여 최대..

문제 https://www.acmicpc.net/problem/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 과정 동영상과 유사도를 가지고 그래프를 만들어 농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 여기서 주의할 점은 존은 두 쌍 사이의 동영상의 유사도를 그 경로의 모든 연결들의 유사도 중 최솟값으로 한다. MooTube (Silver) (BOJ 15591)에서는 각 노드마다 BFS를 돌려 ..

문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 과정 동영상과 유사도를 가지고 그래프를 만들어 농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 따라서 이어진 동영상의 유사도가 k이상이면 해당 동영상에서 또 이어진 동영상을 탐색해야 하는 과정을 반복해야 하고, 동영상 개수를 세야 하므로 BFS를 활용하였다. 여기서 주의할 점은 존은 두..

문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 풀이 과정 프로그래머스 - 다리 위를 지나는 트럭과 같은 문제였다. 큐를 이용하여 문제를 해결하였다. 트럭이 한 대씩 다리에 올라가게 된다. (다리 => 큐) 이때 다리에 트럭이 올라갈 자리가 있다면 1-1. 그리고 해당 트럭의 무게로 다리에 올라가도 된다면, 다리에 트럭을 추가해주고, 현재 다리의 무게를 기록한다. (시간 + 1) 1-2. 트..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결 과정 캐릭터 위치에서 아이템 위치까지의 최단 경로를 구하는 것이기 때문에 BFS를 이용하여 풀었다. 여기서 주어진 직사각형의 간격이 1일 수 있음에 주의해야 한다. 예) rectangle = [1, 1, 2, 4] 그렇게 되면 테두리가 아닌데도 캐릭터가 지나가게 되므로, 이 경우를 방지하기 위해 크기를 2배로 늘려주었다. (물론 직사각형을 그릴 지형, 캐릭..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 문제 이해가 잘 가지 않아 H-Index에 대해 찾아보게 되었고, H-Index 설명대로 구현하니 해결할 수 있었다. H-Index 구하는 법 : 연구자의 전체 논문을 피인용 순으로 정렬한 후, 논문의 순번과 피인용 횟수를 비교하여 피인용 횟수가 논문의 순번보다 작아지기 시작하는 직전의 순번이 연구자의 H-Index가 된다. 참고 링크 ➡︎ https://www.ibric.org/m..

문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 과정 투 포인터 방식으로 풀었다. 두 개의 포인터를 맨 왼쪽과 맨 오른쪽에 놓고 한 칸씩 이동하면서 회문인지 유사회문인지 일반 문자열인지 판별하였다. 코드 # 회문인지 체크하는 함수 def check_palindrome(l, r): while l < r: if string[l] != string[r]: return False l += 1 r -= 1 return True t = int(input()) for _ in..