💻 컴퓨터공학

문제 링크 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이 제곱수라면, 다른 한 변의 길이를 임의의 제곱수로 하고, 나머지는 적절한 길이로 두면 쉽게 두 개 변의..

문제 링크 15900번: 나무 탈출 문제 요약 node가 N개, vertex가 N-1개인 tree가 주어진다. 각 leaf에는 말이 있고, 한 턴에 한 번씩 움직여서 root에 도달하면 말을 제거하는데 이런 방식으로 움직일 말이 없어지는 사람이 패배하는 게임을 하고 있다. 주어지는 tree에서 게임을 할 때, 선공을 하는 형석이가 이긴다면 "Yes" 진다면 "No"를 출력하라. 풀이 설명 tree란 순환이 없는 그래프이다. 그중 특히 이진 트리는 leaf node를 제외한 나머지가 두 개씩 자식 노드를 가진 트리를 말하며, 위 문제에서는 그러한 조건이 달려있지 않았기 때문에 일반적인 트리로 가정한다. 문제를 풀 때, 일반적으로 문제에서 제시된 것들을 코드로 구현하고 거기에서 목표로 하는 값을 구하고자 하..

문제 링크 2961번: 도영이가 만든 맛있는 음식 문제 요약 도영이는 재료 N개로 요리를 만들려고 한다. 각 재료의 신맛과(S) 쓴맛(B)을 알고 있고, 요리의 신맛은 각 재료 신맛의 곱이고, 쓴맛은 합일 때, 신맛과 쓴맛의 차이의 최소값을 구하라. ※ 단, 요리를 완성하기 위해 재료는 1개 이상 사용하여야 한다. ※ N(1 ≤ N ≤ 10)이고, 모든 재료의 신맛과 쓴맛의 합은 1,000,000,000 작은 양의 정수이다. 풀이 설명 이 문제의 알고리즘 분류는 브루트포스, 비트마스킹, 백트래킹이었으나, 가지치기 조건을 찾지 못하여(떠올린 모든 가설 조건에 예외가 발생) 브루트포스 방식으로 해결하였다. 이 문제에서 1, 2, ..., N개의 재료를 선택하는 각 경우에 대해, 모든 경우를 탐색해야 하였으며..

Ctrl + Shift + P 누르고, Python: Select Interpreter 선택한 뒤에, Conda interpreter 선택 → Conda 가상환경에 설치한 패키지가 적용된다!