목록파이썬 (40)
DevKim
programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr [ 알고리즘 ] 단순구현 [문제 접근] 이 문제의 관건은 나 자신을 제외한 모든 사람과의 이기고,짐의 결과를 알고 있어야된다는 것이다. 이김 =1, 짐 =-1, 알 수 없음 =0으로 나타낸 리스트를 생성시켜주고 한 명의 정보에 대해서, 만약 a가 b,c,d 에게 지고 , e에겐 이겼다면, 1 ) e는 b,c,d에게 무조건 질 것이고, 2 ) b,c,d는 무조건 e를 이길 것이라는걸 알 수 있다. 이렇게 한명씩 모두 정보를 업데이트 시켜준 후, 각 행에서 0이 하나만 포함된 행을 co..
www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [ 알고리즘 ] BFS,구현 [문제 접근] 이 문제는 방향에 대한 규칙만 찾으면 해결할 수 있는 문제이다 동,서,남,북을 편하게 오른쪽,왼쪽,아래쪽,위쪽이라고 했을 때, - 문제에 주어진 방향 0: 위쪽 1: 오른쪽 2: 아래쪽 3: 왼쪽 1. 가는 방향을 기준으로 무조건 왼쪽으로 회전임을 주의 - 위쪽을 바라보고 있는 경우 : 왼쪽으로 이동 - 아래쪽을 바라보고 있는 경우 : 오른쪽으로..
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [ 알고리즘 ] BFS, 브루트포스 [문제 접근] 브루트포스 + BFS를 이용하여 해결하는 문제이다. N과 M의 범위가 크지 않은 경우라 브루트포스 방법을 생각해내었다. 벽은 3개만 추가로 설치할 수 있으므로 벽이 설치될 수 있는 경우의 수를 구하고, 이를 Counter 을 이용하여 안전지대의 개수를 counting 한 후 Max 값만 업데이트 해주면 된다. [코드] from collections import deque f..
www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [ 알고리즘 ] 구현 [문제 접근] 이 문제는 세가지의 경우로 나눠야한다 1. 경사가 감소하는 경우 (한칸만) --> 그 전의 경사 높이-1 = 그 다음의 경사 높이 일땐 감소하는 경사의 개수가 L 이상이 되어야함 2. 경사가 증가하는 경우 (한칸만) --> 그 전의 경사 높이+1 = 그 다음 경사 높이 일땐 증가하기 전에 까지의 높이가 연속적으로 L개 이상이 되어야함 3. 경사가 같은 경우 --> 단순 check 증가 [코드] N,..
programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr [ 알고리즘 ] DP [문제 접근] 코드는 굉장히 간단하지만, 이걸 생각해내기는 정말정말 쉽지 않음이 분명하다. 점화식을 한번에 찾아내기 어려웠던 문제, 개수로 따져서 그런 것 같다 간단히 설명해보자면.. dp[0] 은 아무것도 포함하지 않을 때, 즉 자기 자신만을 이용해 만들 수 있는 경우이다. 예시의 n=5, money=[1,2,5] 로 생각해보자 초기 상태의..
programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr [ 알고리즘 / 자료구조 ] 해시 [문제 접근] defaultdict으로 list 형태의 딕셔너리를 생성해주고, 제한 사항에 맞춰 하나씩 정렬해주고 조건을 달아주면 된다 [코드] from collections import defaultdict def solution(genres, plays): answer = [] dic=defaultdict(list) max_g=defau..
programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 문제 자체는 어렵지 않으나, 하나씩 다 구해서 최대값 구하면 안되는 문제이고, 아이디어가 딱 떠오르면 풀리는 문제 중 하나이다. 두 수의 차가 적어야 곱이 큰 것만 깨달으면 빠르게 풀어나갈 수 있는 문제 [코드] def solution(n, s): answer = [] if n > s: # 존재하지 않는 경우 ret..
programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 처음에 row와 col을 뒤집는 과정이 이 문제의 핵심키라고 생각한다. 이 문제를 통해 zip을 사용하여 한줄로 row와 col을 뒤집는 코드를 배웠다. 집합 set을 이용하여 2*2의 겹치는 캐릭터들을 합쳐주며 중복은 없애주고, 중복되어 없어진 부분을 임의의 문자로 채워주었다. 더 이상의 삭제되는 프렌즈가 없을 때까..