본문 바로가기

Algorithm175

18428. 감시 피하기 (Python) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 리스트에 X의 위치를 담아두고 이를 조합을 사용하여 3개의 위치를 뽑아낸다. 조합으로 뽑아낸 3개의 위치에 장애물을 설치하고 선생님들의 위치에서 상하좌우를 봤을 때 학생을 볼 수 있는지를 체크한다. 코드 from itertools import combinations # 범위 체크 함수 def isRange(x, y): return 0 2022. 2. 12.
14940. 쉬운 최단거리 (Python) 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 풀이 목표지점(2)의 위치를 구해서 해당 위치에서부터 bfs로 탐색을 하면 된다. 정답을 담아주는 배열의 초기 값에는 지도의 값이 1인 좌표에는 -1을 넣어주고 0인 좌표에는 0을 넣어준다. bfs 탐색을 하며 해당 좌표에 도착하는 거리를 정답 배열에 넣어주면 된다. 코드 from collections import deque # 범위 탐색을 위한 함수 def isRange(x, y): return 0 2022. 2. 11.
11725. 트리의 부모 찾기 (Python) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 노드에 연결된 노드들을 담아놓는 배열(nodes)을 만들어준다. 입력으로 5 3을 받으면 nodes[5]에 3을 추가해주고 nodes[3]에 5를 추가해주는 방식으로 nodes 배열을 채워준다. 루트 노드가 1이라고 했으므로 1부터 큐에 담아서 각 노드에 연결되어 있는 노드들에 대해서 탐색한다. nodes[1]에 있는 노드들을 차례대로 큐에 담아주는데 이때 nodes[1]에 있는 노드들의 부모는 1번 노드이므로 부모 노드로 1을 담아준다. 이와 같은 방식으로 큐를 돌면서 노드들의 부모 노드를 찾아주고 마지막에 부모 노.. 2022. 2. 10.
[고득점 Kit(정렬)] H-Index (Python) 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 풀이 일단 입력으로 받은 배열을 내림차순으로 정렬한다. 그 후 인용 횟수로 따졌을 때의 최댓값(citationRes)과 논문의 개수로 따졌을 때의 최댓값(countRes)을 나눠서 최댓값을 구했다. 예를 들어 입력으로 [5, 5, 5, 9]가 주어지면 [9, 5, 5, 5]로 정렬하고 앞에서부터 for문을 통해 현재 논문의 인용 횟수와 지금까지 살펴본 논문의 개수를 카운트한다. for문을 돌면 다음과 같은 순서로 체크한다. -> .. 2022. 2. 8.
[고득점 Kit(정렬)] 가장 큰 수 (Swift, Python) 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 풀이 입력으로 주어진 numbers 배열을 String의 형태로 바꾸어 정렬을 해주는데 이때 새로운 기준이 되는 정렬 함수를 만들어 줘야 한다. 예를들어 예제의 [3, 30, 34, 5, 9]를 String 형태로 바꾸어 내림차순으로 정렬하면 [9, 5, 34, 30, 3]이 된다. 가장 큰 수를 만들기 위해서는 [9, 5, 34, 3, 30]으로 정렬이 되어야 한다. 먼저 가장 앞의 숫자를 비교해.. 2022. 2. 3.
[고득점 Kit(힙)] 이중우선순위큐 (Python) 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 최소힙과 최대힙을 각각 만들어서 값을 넣어줬다. Insert 작업이 들어오면 각각의 힙에 값을 넣어줬고 Delete 작업이 들어오면 각각의 힙에서 값을 pop해줬다. 마지막에 두 힙에 값이 남아있다면 answer 배열에 최댓값과 최솟값을 찾아서 넣어줬다. 코드 import heapq def solution(operations): answer = [0, 0] minHeap = [] # 최소힙 maxHeap = [] # 최대힙 for operation in operations: if operation[0] == 'I': # Insert일 경우 두 힙에 값 push num = int(operation[2:]) heapq.heappush(m.. 2022. 1. 29.

티스토리툴바