💻 컴퓨터공학

🔗 문제 링크 1876번: 튕기는 볼링공 💊 문제 요약 지름이 20cm인 볼링공을 폭이 105cm인 볼링 레인에, 레인과 평행한 축을 기준으로 반시계 방향 X도로 레인의 중심에서 던졌다. (10

문제 링크 1167번: 트리의 지름 문제 요약 트리는 사이클 없이 모든 정점이 연결된 그래프이다. 정점의 갯수 V(1 0: graph[start].append((row[i], row[i+1])) def bfs(start): dists=[-1 for _ in range(V+1)] dists[start]=0 visited=[0 for _ in range(V+1)] visited[start]=1 q=deque([(start, 0)]) while q: end, dist=q.popleft() for i in range(len(graph[end])): c_end, c_dist=graph[end][i] if visited[c_end]==0: if dists[c_end]

문제 링크 1916번: 최소비용 구하기 문제 요약 N개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 각 M개의 버스에 대해 '출발 도시, 도착 도시, 비용'이 주어진다. A 도시에서 B 도시로 가는 최소 비용을 구하자. 도시는 1부터 N까지의 자연수로 나타난다. 풀이 설명 출발 지점부터 도착 지점까지의 최소 비용을 구하는 것, 다익스트라(dijkstra) 알고리즘으로 예시 입출력 문제를 풀어보니, 다른 입력들에서도 답을 구할 수 있으리라 생각되었다. visited를 활용한 다익스트라 구현 어제+그제 문제들을 풀면서 visited 배열을 사용하는 것이 비효율적인 중복 탐색을 방지하여 소요 시간 개선에 탁월하다는 것을 느껴서 오늘 다익스트라 문제도 동일하게 visited ..

문제 링크 14502번: 연구소 문제 요약 연구소에 바이러스가 유출되었다. 바이러스는 벽을 뚫지 못하며 가로 또는 세로 한 칸씩 이동할 수 있다. 벽을 3개 세울 때, 확보할 수 있는 안전 공간의 최대 갯수를 구하고 싶다. 이 때 안전 공간은 벽으로 막혀서 바이러스가 오지 못하는 공간이다. 입력으로 N×M 크기의 연구소가 주어진다. 0은 빈공간, 1은 벽, 2는 바이러스를 의미한다. 풀이 과정 예시의 입출력에서 안전 공간을 최대로 확보할 수 있는 최적의 벽 위치를 컴퓨터가 어떻게 알 수 있을까 생각해본 후, 1) 모든 벽을 세우는 경우에 대해서 2) 안전 공간의 넓이를 계산하고 이의 최대값을 구한다. 라는 접근으로 풀 수밖에 없다고 생각이 들었다. 첫 번째 시도: for문으로 조건에 맞는 경우를 찾아 탐..

문제 링크 1010번: 다리 놓기 문제 요약 다리 놓기 문제는 서쪽의 N개 사이트와 동쪽의 M개 사이트를 연결하는 다리 N개를 서로 교차하지 않도록 짓고 싶다. N과 M이 (N ≤ M) 주어질 때, 다리 건설이 가능한 모든 경우의 갯수를 출력하시오. 풀이 설명 다리끼리 교차하지 않아야하므로, 답은 M개의 사이트에서 N개를 고르는 경우의 수=combination(range(M), N)의 길이이다. 이전 문제를 풀면서 itertools의 combination을 배웠던터라 무지성으로 신나게 아래와 같은 코드를 제출했다. print(len(list(combination(range(M), N)))) 결과는 시간초과이다. (제출 번호 71022244) 다시 정신 차리고, 경우의 수만 구하는 것이니 조합 식으로 M!..

문제 링크 15654번: N과 M(5) 문제 요약 N개의 서로 다른 정수가 주어진다. 이 때 서로 다른 정수로 길이가 M인 수열을 사전 순서대로 출력하세요. 풀이 설명 이 문제가 조건 아래에서 가능한 모든 경우를 탐색하는 백트래킹 알고리즘 유형인 것에 맞게, 모든 경우의 수열을 재귀적으로 탐색하여 출력하였다. (DFS) 더욱이 사전 순서대로 출력하는 것이어서 DFS 방식으로 경우를 탐색하는 것이 적절했다. N, M=map(int, input().split()) nums=list(map(int, input().split())) nums=sorted(nums) def dfs(nums_print, nums_left): if len(nums_print)==M: for i in range(M): print(num..

import string print(string.ascii_lowercase) >>abcdefghijklmnopqrstuvwxyz string — Common string operations Source code: Lib/string.py String constants: The constants defined in this module are: Custom String Formatting: The built-in string class provides the ability to do complex variable substitutions ... docs.python.org python 내장 라이브러리 string을 사용하면 쉽게 영어 소문자, 대문자를 불러올 수 있다! 이외에도 string.ascii_l..

문제 링크 28683번: 피타! 피타! 피타츄! 문제 요약 삼각형 한 변 길이의 제곱인 n이 주어진다. sqrt(n) 길이의 변을 가지는 가능한 합동이 아닌 서로 다른 직각삼각형의 갯수를 출력하라. 단, 직각삼각형의 최소한 두 변은 정수여야 한다. 가능한 직각삼각형의 갯수가 셀 수 없이 많다면 -1를 출력한다. (피타! 피타! 피타츄!의 의미를 글을 쓰면서 깨달았다 😅) 풀이 설명 꽤 여러번의 시도와 다른 사람들의 풀이를 참고한 끝에 문제를 풀었다. 첫 번째 시도: 경우의 수를 나누어 접근 (if n==제곱수) (시간 초과) 기존에는 n이 제곱수거나 아니거나의 두 가지 경우로 나누어 생각해보았다. n이 제곱수라면, 다른 한 변의 길이를 임의의 제곱수로 하고, 나머지는 적절한 길이로 두면 쉽게 두 개 변의..