문제 (링크) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 나의 코드 import sys input = sys.stdin.readline def find(parent, x): if x != parent[x]: parent[x] = find(parent, parent[x]) return parent[x] # 사실을 아는 사람과 Union시, 해당 사람이 부모노드가 되도록 def union(parent, a, b, know_truth): a = find(..
분류 전체보기
카운팅 정렬, 혹은 계수 정렬은 O(n + k)의 시간복잡도를 가진 정렬이다. 여기서 다소 낯선 k는 정렬을 수행할 배열의 가장 큰 값을 의미한다. k가 단순히 상수로 취급되어 생략되지 않고 남아있는 것은 그만큼 k에 따라 수행시간에 영향을 미치기 때문이다. 만약 k가 n보다 작다면 정렬의 수행시간은 O(n)이 되겠지만, 무한대로 크다면 정렬의 수행시간도 무한대가 된다. 작동 방식 1. 배열을 이용한 방식 계수 정렬은 counting이라는 말 답게 배열에 존재하는 수의 개수를 세어주고, 이 정보를 바탕으로 정렬을 수행한다. 그리고 여기서 수와 수의 개수는 배열 혹은 딕셔너리의 인덱스와 해당 값을 통해서 기록할 수 있다. 먼저 배열을 통한 계수 정렬은 누적합의 개념을 적용하여 구현할 수 있다. 배열을 이용..
매직 메소드 (Magic Method)란? 매직 메소드 혹은 스페셜 메소드라고 불리며, 메소드의 양쪽을 두 개의 언더스코어(__)로 감싼 메소드를 말한다. 일반적으로 파이썬의 클래스 내에 내부적으로 구현되어 있다. 매직 메소드를 적절히 사용하면 클래스를 보다 폭넓게 사용할 수 있고, 사용자가 직접 만든 클래스를 마치 파이썬의 내장 클래스처럼 사용할 수 있다. 아마 파이썬을 사용하며 가장 처음 접하거나 구현하는 매직 메소드는 __init__() 혹은 __str__() 일 것이다. __init__() 해당 메소드는 파이썬 클래스의 인스턴스를 생성할 때 자동으로 호출되며, 일반적으로 인스턴스 생성과 함께 인스턴스 변수를 선언하기 위해 사용된다. class Person: def __init__(self): pr..
문제 (링크) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() target = 1 for num in arr: if target < num: break target += num print(target) 코드 설명 및 풀이법 처음엔 1원부터 모든 무게의 합까지 확..
아스키코드란? 미국정보교환표준부호(영어: American Standard Code for Information Interchange), 또는 줄여서 ASCII( /ˈæski/, 아스키)는 영문 알파벳을 사용하는 대표적인 문자 인코딩이다. 아스키는 컴퓨터와 통신 장비를 비롯한 문자를 사용하는 많은 장치에서 사용되며, 대부분의 문자 인코딩이 아스키에 기초를 두고 있다. - 위키백과 쉽게 말해 아스키코드는 알파벳을 비롯한 문자들을 통신하기 위해 일대일 대응시켜 숫자로 정해둔 코드이다. 아스키코드 테이블은 다음과 같다. 물론 이 표를 다 외우고 있을 필요는 없다. 파이썬에서는 ord()와 chr() 함수를 통해 문자를 아스키코드로, 아스키코드를 문자로 변환할 수 있다. print(ord("A")) print(o..
오늘 오전 미뤄놨던 MAC OS Monterey 업데이트를 한 후, 진행 중인 프로젝트의 로컬 서버를 가동하려는데 얘가 갑자기 가상환경에 설치된 패키지들을 읽어들이지 못했다. ModuleNotFoundError: No module named 'decouple' pip freeze를 해도 패키지를 읽어들이지 못했고, git도 정상적으로 작동하지 않았다. 아마 git이 작동하지 않으니 패키지들 또한 정상적으로 불리지 못하는 상황인 것 같았다. 자세히 보니 터미널에 xcrun: error: invalid active developer path 라는 에러가 찍혀있었고, 검색해본 결과 매번 OS 업데이트 직후 빈번히 발생하는 문제란다. 해결방법은 생각보다 간단했다. xcode-select --install 터미널..
문제 (링크) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n = int(input()) tops = list(map(int, input().split())) stack = [] # 인덱스와 탑의 높이 stack.append([1, tops[0]]) # 맨 왼쪽 탑은 수신되지 않음 ans = [0] for i in range(1, n): while stack: ..
문제 (링크) https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline # 1번 상어는 모두 쫓아낼 수 있음 # N * N 그래프에 M 마리의 상어, k = 냄새 지속시간 n, m, k = map(int, input().split()) graph = [] sharks = [[] for _ in range(m + 1)] # 위, 아래..
