목록python (18)
DevKim
https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr [ 알고리즘 ] BFS [ 접근 방법 ] * 조건 * 1. 벽이 없는 경우에 2. 맨해튼 ..
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/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] bigin부터 덱에 넣어주고, 한글자만 다른지 여부를 판별해준뒤 한글자만 다르다면 덱에 넣어준다 (target이 될 때까지 반복) [코드] from collections import deque def solution(begin, target, words): cnt = 0 que=deque() n=l..
programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [ 알고리즘 ] DFS [문제 접근] 아 이 문제 때문에 애를 많이 먹었다.. 사전 순으로 정렬을 시켜야하나, 또 그것이 타고타고 갔을 때 끊겨버리면 안되기 때문에, 하나의 공항에서 끝까지 갔을 때 이어지는지 여부를 따로 체크하려고하다보니 많이 복잡해졌다.. DFS를 이용하여 항공편이 더이상 남아있지 않았을 경우에만 pop하여 answer에 ..