코딩 테스트/코딩 테스트 문제 검색 결과

해당 글 5건

백준 2887 행성 터널 (파이썬 python)

백준 2887 행성 터널 (파이썬 python) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 및 접근 N-1개의 터널, 양방향, 최소 비용(거리)을 통해 최소 신장 트리 문제임을 알 수 있고, 크루스칼 알고리즘으로 풀이 할 수 있습니다. 이전에 풀었던 문제는 edge의 거리(비용)이 입력 값으로 주어졌는데, 이 문제에서는 edge의 값을 구해야 했습니다. 일반적으로 for문을 두 개 중첩하여 서로 다른 임의의 두 점 사이의 거리를 구할 때 시간 복잡도는 O(N²)..
코딩 테스트/코딩 테스트 문제 2021. 2. 18. 01:13

2019 카카오 실패율 (파이썬 python)

2019 카카오 실패율 (파이썬 python) 문제 풀이 및 접근 input인 stages로 반복문을 돌리는 것과 N을 기준으로 반복문을 돌리는 두 가지 방법으로 풀었습니다. 이 문제의 경우 1,...,N 단계까지의 모든 단계마다 실패율을 구해야했으므로 input 으로 받은 stages를 이용하는 것보다는 range(1,N+1) 사용했을 때 예외 처리가 적고 간결하게 짤 수 있었습니다. 튜플을 원소로 하는 리스트가 있을 때 그 리스트를 정렬하면 첫 번째 원소부터 마지막 원소까지 순서대로 기준이 되어 정렬되는 것을 이용하기 위해 ( 실패율 , stage )의 튜플로 각 stage 마다의 실패율을 담았습니다. Code - N을 기준으로 for문 def solution(N,stages): result = []..
코딩 테스트/코딩 테스트 문제 2021. 2. 3. 14:11

백준 10825 국영수 (파이썬 python)

백준 10825 국영수 (파이썬 python) 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 풀이 및 접근 처음에는 국어 → 영어 →수학 →이름과 같이 맨 윗단 부터 아랫단까지 정렬하는 방식을 생각했었습니다. 국어 점수가 같은 것끼리 한 단위로 정하고 그 단위 내에서 영어 점수 정렬하고 정렬한 것 중에서 영어 점수가 같은 것끼리 또 단위로 묶는 방식을 반복하며 이름까지 정렬하는 방식으로 생각했었습니다. 이렇게 하면 단위가 굉장히 많아지고 이러한 단위를 나누는 idx 정하는 방법을 어..
코딩 테스트/코딩 테스트 문제 2021. 2. 2. 11:23

백준 14502 - 연구소 (파이썬 python)

백준 14502 - 연구소 (파이썬 python) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 및 접근 방법 3개의 벽을 쌓는 경우의 수를 구하기 위해 조합을 썻고, 이를 위해 itertools 의 combinations를 사용했습니다. 3개의 벽을 세우는 경우의 수 마다 graph 변경을 하므로 원본 graph를 deepcopy한 graph_ 를 변화시켰으며, 이를 변화시킨 것으로 방문처리를 하였습니다. deepcopy를 위해 copy library를 사용했습니다. 최단거리를 구하라는 문제가 아니여서 dfs를 사..
코딩 테스트/코딩 테스트 문제 2021. 1. 30. 23:46

백준 18352 - 특정 거리의 도시 찾기 (파이썬 python)

백준 18352 - 특정 거리의 도시 찾기 (파이썬 python) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 및 접근 방법 최단 경로를 구하는 문제이므로 BFS 방법으로 풀이합니다. DFS BFS 비교 deque 쓰지 않고 list와 list method로 풀었을 때 시간 초과였습니다. → queue, stack 관련 문제일 때 deque 사용 기존에 하던대로 내장함수 input()을 사용하니 입력 시간이 길어서 그런지 시간초과..
코딩 테스트/코딩 테스트 문제 2021. 1. 29. 23:53