문제 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 bfs로 그래프를 탐색하여 그림의 개수와 가장 큰 그림을 찾아내는 문제. 첫 시도에서 Value Error가 발생. input : 1 1 0 이라는 케이스에서 max(cnt_list)에서 에러가 발생하여 예외처리를 했더니 문제 해결. 코드 from collections import deque direction = [(-1, 0), (0, -1), (1, 0), (0, 1)] def bfs(graph, node): queue = deque() queue..
문제 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 풀이 지인들 중 연결고리가 가장 긴 사람을 기준으로 그 길이로 점수를 매기고, 해당 점수가 가장 작은 사람을 회장 선출한다. 다익스트라 알고리즘으로 문제를 해결해도 될 것 같지만, 해당 문제의 입력 크기가 50으로 매우 작으므로 단순하게 그래프로 구현하여 bfs로 가장 연결고리가 긴 사람을 구했다. 코드 from collections import deque def bfs(graph,root,members): queue = deque([root]) fr..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 단순 구현 문제 코드 from collections import deque def solution(priorities, location): answer = 0 priorities = deque(priorities) while priorities: now_printing = priorities.popleft() location -= 1 print(now_printing,location) if len(priorities) > 0 and max(priorities) > now_printing: pr..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 단순 구현으로는 시간초과 때문에 해결할 수 없다. 2차원 배열을 살펴보면 (i,j)의 원소는 max(i,j)임을 알 수 있다. 따라서 2차원 배열을 직접 구현할 필요 없이 1차원 배열의 인덱스만으로도 해당 원소를 알 수 있게 된다. 코드 def solution(n,left,right): answer=[] for i in range(left,right+1): x,y = i//n+1,i%n+1 answer.append(max(x,y)) return answer
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 단순 구현 문제이다. 시키는 대로 따라가면 해결되는 문제. 하지만 cacheSize가 0인 특이 케이스를 생각하지 못하면 헤맬 수 있다. 코드 def solution(cacheSize, cities): answer = 0 cache_hit = 1 cache_miss = 5 cache = dict() if cacheSize == 0: return len(cities) * 5 for index,i in enumerate(cities): i = i.lower() if len(cache) < cach..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 논문의 수가 1,000편 이하이고, 인용 횟수는 10,000 이하이므로 어렵게 생각할 것 없이 단순 반복으로 해결 가능한 문제 코드 def solution(citations): answer = 0 for i in range(max(citations),-1,-1): cit_count = 0 for j in citations: if i = i: return i
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 전형적인 다이나믹 프로그래밍의 문제로 점화식만 잘 세우면 쉽게 문제를 풀 수 있다. 어떤 순서의 모든 경우의 수는 1) 직전의 결과에 1을 더하고 2) 직전의 직전의 결과에 2를 더하는 결과를 합치면 경우의 수가 완성이 된다. 그러므로 점화식은 dp[n] = dp[n-1] + dp[n-2] 가 된다. n 이 1일때와 2일 때의 경우는 쉽게 알 수 있으므로 미리 초기값으로 설정하고 점화식을 반복한다. 코드 def solution(n): answer=0 if n == 1: return 1 if n..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 N을 2로 나눈 나머지를 결과값에 더해주다 보면 값을 구할 수 있는 문제 코드 def solution(n): ans = 0 while n: ans += n % 2 n //= 2 return ans
