본문 바로가기
반응형

Python51

[이취코] 숫자 카드 게임 출처 : 이것이 취업을 위한 코딩테스트다 with python 유형 : 그리디 1. 문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다. 룰은 다음과 같다. 1) 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2) 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3) 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4) 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 낮은 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 예시 3 3 3 1 2 4 1 4 2 2 2 예시 출력 2 2. .. 2022. 2. 8.
[이취코] 큰 수의 법칙 출처 : 이것이 취업을 위한 코딩 테스트다 with python p.92 1. 문제 배열의 크기 N, 숫자가 더해지는 횟수 M, K가 주어질 때 큰수의 법칙에 따른 결과를 출력하시오. (단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다) 예시 5 8 3 # N,M,K 2 4 6 4 6 예시 출력 46 2. 내 코드 N, M, K = map(int, input().split()) data = list(map(int, input().split())) data.sort() max1, max2 = data[-1], data[-2] _list = M * [max1] for i in range(K,M,K+1): _list[i] = max2 print(sum(_list)) _list.. 2022. 2. 8.
[이취코] 미로 탐색 출처 : 이것이 취업을 위한 코딩 테스트다 with python 같은 문제 : https://www.acmicpc.net/problem/2178 문제는 링크에 있는 백준에 들어가서 보면 된다. 이 문제 같은 경우는 경로의 길이를 세는 것이기 때문에, BFS로 해야 효과적으로 해결할 수 있다. BFS는 너비우선탐색으로 시작 지점에서 가까운 노드부터 차례대로 모든 노드를 탐색하기 때문이다. DFS는 재귀를 이용해 깊이 우선 탐색을 한다면, BFS는 큐로 어느 정도 탐색하는 지를 볼 수 있다. 여기 풀이에서 특이한 점은 경로의 길이가 원래 노드 값(0,1)을 대체하게끔 푼다는 점이다. 경로의 길이가 노드 값을 대체하기 때문에 마지막 (N-1, M-1) 좌표에서 대체된 값을 출력하면 원하는 결과를 얻을 수 있다.. 2022. 2. 8.
[이취코] 음료수 얼려 먹기 출처 : 이것이 취업을 위한 코딩 테스트다 with python P. 149 유형 : DFS 1. 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다. 4 5 # N, M 00110 00011 11111 00000 2. 문제 설명 3 3 001 010 101 3. 코드 N, M = map(int,input().split()) graph = [] for _ in range(N): g.. 2022. 2. 8.
[해커랭크] Journey to the Moon 문제 링크 : https://hackerrank.com/challenges/journey-to-the-moon 참고 : https://www.snoopybox.co.kr/1766 유형 : Algorithms > Graph Theory 난이도 : Medium 1. 문제 설명 문제는 링크타고 들어가면 자세히 볼 수 있고, 나중에 다시 볼 나를 위해 대략 설명하겠다. 4 1 0 2 위와 같은 예시가 있다고 했을 때, 결과는 5가 나와야 하는데 왜 5가 나와야 하는지 알아보자! 첫 번째 줄에 있는 숫자 2개 중 첫 번째(4)는 우주비행사 수를 나타내고, 두 번째(1)는 그 다음 줄을 몇 번 입력받을 지를 알려준다. 먼저 우주비행사 수가 4이므로 우주비행사가 [0,1,2,3] 이렇게(?) 있다. 첫 번째 줄을 제.. 2022. 2. 8.
[백준] 1715번 : 카드 정렬하기 유형 : 힙, 자료구조, 그리디 [예제 입력] 3 10 20 40 [예제 출력] 100 1. 아이디어 처음에 예제를 잘못 이해했다. 2개씩 묶어서 결국 가장 적은 비교 횟수를 구하고자 하기 위해 작은 크기부터 정렬을 해야 한다고 생각했다. 여기까지는 방향을 맞게 왔으나.. 카드 묶음을 비교하고 난 결과값을 다시 카드 더미에 넣는 부분을 빼먹었다. 그래서 테스트케이스 값이 계속 다르게 나와 어디서 틀린지조차 몰랐었다. 알고리즘은 다음과 같다. (풀이 참고) ① 총 비교 횟수(result)를 0으로 둔다. ② 현재 카드 더미(card) 중 가장 작은 2개의 카드 묶음(first, second)을 고른다. ③ _sum = first + second 값이 현재 단계에서 비교한 횟수를 의미한다. ④ _sum 값을.. 2022. 1. 25.
반응형