최근 자료구조와 알고리즘 강의를 듣고 있다.이 강의를 듣고 나면 백준 알고리즘 문제도 조금씩 풀어볼 예정이다.오늘 들은 강의 중, 이진 트리(BST)를 구현해보는 부분이 있었는데, 기본적인 내용이라 그런가 걱정했던 것과 달리 재밌었다.아래의 코드는 강의에서 알려준 코드를 참고해 다시 나름대로 다시 작성해본 코드다.기록 겸 남겨본다.class Node: def __init__(self, value): self.value = value self.left = None self.right = Noneclass NodeMgmt: def __init__(self, value): self.head = Node(value) # 노드 추가 d..
1. 문제 - 6588번 2. 접근법 기존에 풀었던 에라토스테네스의 체를 활용해 풀 수 있었다. (참고 : 백준 문제 11653) 풀이 과정은 다음과 같다. - 우선 에라토스테네스의 체를 이용해 문제에서 주어진 범위(6 소수 집합 구하기 primes = [True]*n primes[0] = False primes[1] = False for i in range(2, int(n*0.5)+1): if primes[i]: for j in range(2*i, n, i): primes[j] = False return primes def test_goldbach(n, prime_list): for index, prime in enumerate(prime_list): # 짝수 n = 소수 a + 소수 b 일때, a와 ..
1. 문제 - 2004번 2. 접근법 이전 1676번 문제를 풀 때처럼 문자열을 활용한 방법으로 풀려 하니 도저히 풀리지 않았다. 계속 고민해봐도 방법을 모르겠어서 찾아보니, 다른 분들의 블로그에서 아래와 같은 원리를 활용해 문제를 풀 수 있었다. 1676번을 빠르게 푸는 방법을 알아야 이 문제를 풀 수 있다. 특히, 다음 블로그의 글이 이해하는데 도움이 되었다. https://lucian-blog.tistory.com/84 이 문제의 경우, - 문제가 의마하는 바는 n과 m의 조합 값이 가지는 0의 개수를 구하는 것 - 0의 개수를 구하기 위해서는 2와 5의 지수의 개수로 각각 0의 개수를 구할 수 있으며 그 중 작은 값을 찾아주면 됨(일종의 교집합) - n과 m의 조합 값에서의 0의 개수는 n!의 0..
1. 문제 - 1676번 2. 접근법 팩토리얼의 결과값에서 1의 자리부터 0이 아닌 수가 나올 때까지 0의 개수를 구하는 문제다.가령,5! = 120으로 0이 1개, 10! = 3628800으로 0이 2개 이런 식으로 계산된다. def factorial(num): factorial = 1 for i in range(num, 0, -1): factorial *= i return f'{factorial}'[::-1] def count_zero(num): fac = factorial(num) cnt = 0 for i in fac: if int(i) == 0: cnt += 1 else: break return cnt n = int(input()) print(count_zero(n)) 우선 첫번째 함수로 팩토리얼..
1. 문제 - 10872번 2. 접근법 기초적인 팩토리얼 문제다.반복문을 사용하면 간단하게 해결 가능하다. def factorial(num): factorial = 1 for i in range(num, 0, -1): factorial *= i return factorial n = int(input()) print(factorial(n))
1. 문제 - 11653번 2. 접근법 소인수분해를 하는 문제의 경우, 고민해보며 두가지 방법을 찾았다. - 주어진 수 n을 2부터 순차적으로 나누며 확인하는 방법으로 풀거나 - 에라토스테네스의 체로 n 이하의 소수 집합을 구한 후 소수를 순차적으로 나누거나 def prime_factor(num): if num == 1: print("") for i in range(2,num+1): while num != 1: if num%i == 0: print(i) num //= i else: break if n == 1: break n = int(input()) prime_factor(n) import sys from math import sqrt input = sys.stdin.readline def prime_..
1. 문제 - 1929번 2. 접근법 처음에 이전의 소수 구하기 문제처럼 생각하고 풀었다가, 몇번이고 시간 초과가 나왔다. 찾아보니 최대 공약수에 유클리드 호제법이 있는 것처럼, 소수 문제의 경우 에라토스테네스의 체라 불리는 일종의 노가다식 풀이법이 있다는 것을 알게 되었다. 노가다이지만, 가장 빠른 알고리즘이라는 것도. 왜 노가다인가 하면, 특정 조건( 2부터 √n 까지 의 수 중 하나라도 약수로 가진 수)을 걸어 소수에 해당하지 않는 수를 뭉텅이로 지워나가는 논리이기 때문이다. 내가 에라토스테네스의 체의 논리를 이해한 바는 이렇다. - 현재까지 검증된 방법 중, 소수를 찾는 가장 빠른 방법 - 특정 범위(ex. 1~n)까지의 소수를 알고 싶다면, n까지의 모든 수의 배수가 아니라 √n 까지만 나누어 ..
1. 문제 - 1978번 2. 접근법 주어진 수들 중에서 소수를 출력하는 문제다. 먼저 소수의 정의를 생각해보자. 소수란 '1과 자기 자신만을 약수로 가지는 수'이다. 이 점에 착안에 코드를 작성하면 아래와 같다. import sys input = sys.stdin.readline def prime_number(nums): prime_list = [] for num in nums: divs = [i for i in range(1,num)] cnt = 0 for i in divs: if num%i == 0: cnt += 1 if cnt == 1: prime_list.append(num) return len(prime_list) n = int(input()) numbers = list(map(int, inp..
1. 문제 - 11576번 2. 접근법 특정 진법이 먼저 주어지지 않고, 임의의 진법들이 주어졌을 때 상호 변환이 가능한 코드를 작성하는 문제다. 변환 전인 A진법의 각 숫자는 0으로 시작하는 경우가 없다고 했으므로, 이번 경우에는 0에 대한 처리는 생각하지 않아도 괜찮다.진법 간 변환을 쉽게 해주기 위해, A진수를 우선 10진수로 변환해준 뒤, 10진수를 나머지 원리를 이용해 B진수로 바꿔주는 코드를 작성했다.2초라는 제한 시간이 있으므로 빠른 속도를 위해 input 대신 sys 모듈을 사용해 표준입력값을 받았으며, append 메서드가 아닌 insert메서드를 사용해 출력 값을 첫 인덱스부터 삽입해주어 출력시 reversed등으로 뒤집을 필요가 없도록 했다. import sys input = sys...
1. 문제 - 2089번 2. 접근법 -2진법이란 개념에서 고민하다 찾아보니, 처음 생각한대로 원리는 가장 기본적인 진법 변환을 활용한 것이었다. 진법 변환은 나누는 수, 몫, 나머지의 관계애서 출발하므로, 이 문제도 -2를 나누는 수로 하고 나머지를 0 또는 1로 갖는 식으로 계속 나누어 주면 된다. 규칙을 좀더 직관적으로 파악하기 위해, 문제에서 주어진 수 중 9와 -13을 예시로 분석해보았다. 나머지를 반드시 0 또는 1로 만들면서, -2로 계속 나누어 보면 그 과정은 다음과 같다. -13 = -2*7 + 1 7 = -2*-3 + 1 -3 = -2*2 + 1 2 = -2*-1 + 0 1 = -1*1 + 1 1 = -2*0 + 1 13 의 결과값 : 1101119 = -2*-4 + 1 -4 = -2*..
1. 문제 - 1212번 2. 접근법 파이썬에서는 진법 변환이 가능한 내장 함수를 제공하기에 매우 간단하게 풀 수 있다. 2진법의 경우, bin 함수를 사용하면 된다. print(bin(int(input(), 8))[2:])
1. 문제 - 1373번 2. 접근법 1) 내장 함수 파이썬에서는 진법 변환이 가능한 내장 함수를 제공하기에 매우 간단하게 풀 수 있다. 8진법의 경우, oct 함수를 사용하면 된다. print(oct(int(input(),2))[2:]) 2) 진법 변환 원리를 코드로 구현 2진수의 세자리가 8진수의 한 자리가 된다는 원리에서 착안. 예를 들어, 문제에서 주어진 2진수 11001100을 끊어보면 11 / 001 / 100 이며 이걸 8진수로 나타내면 314가 된다. (계산은 0*2^2+1*2^1+1*2^0 / 0*2^2+0*2^1+1*2^0 / 1*2^2+0*2^1+0*2^0) 이런 원리를 코드로 구현하면 된다고 판단했다. import sys input = sys.stdin.readline def bin..
앞선 글을 통해 법률이 국회에서 처리되는 과정(링크)에 대해 간략히 살펴보았습니다. 거대 조직인 대한민국의 뼈대를 튼튼하게 만들기 위해서는, 각각의 분야에 필요한 전문지식이 필요합니다. 때문에 분야를 나눠 검토하는 것이 여러모로 효율적이죠. 이러한 필요에 의해 생겨난 것이 상임위원회라고 할 수 있습니다. 우리나라에는 총 17개의 상임위가 존재하고 있습니다. 국회 본회의보다는 소관 상임위에서 분야별 안건에 대한 실질적인 심사가 이루어지며 이를 상임위원회 중심주의라고 합니다. 상임위의 주요 업무는 법률안의 심사와 정부의 예·결산안에 대한 예비심사이며, 각 상임위의 역할은 다음과 같습니다. 앞으로도 항상 양질의 정보를 전달하기 위해 노력하겠습니다. 궁금하신 점이 있으시면 언제든 댓글 남겨주시기 바랍니다. 여러..
앞서 살펴본 국회 용어(이동 링크)를 바탕으로, 국회에서 법률안이 처리되는 과정을 정리해보면 다음과 같습니다. 1) 법안 발의(제출) 현역 국회의원 10명 이상의 찬성에 의해 법률안이 발의되며, 발의된 법안은 본회의 보고 후, 소관 상임위원회(상임위)에 회부돼 심사를 받게 됩니다. 2) 상임위 회부 및 심사 발의된 안건은 각각의 의제를 주관하는 소관 상임위에 회부되어 심사를 받게 됩니다. 심사에 통과된 안건은 본회의에 부의, 상정됩니다.(상임위원회에 대한 내용은 링크를 참고해 주시기 바랍니다.) 3) 본회의 심의, 의결 부의된 안건은 본회의 심의 당일 상정되어, 심사보고 및 질의 토론을 거쳐 재적의원 과반수의 출석과 출석의원 과반수의 찬성으로 의결(가결)됩니다. 의결된 법안은 정부로 이송되고, 부결된 안..
법률은 알게 모르게 일상과 밀접한 관련이 있습니다. 가까운 사례만 봐도 중대재해처벌법, 검경수사권 조정, 유치원3법, 최근의 간호법과 같은 주요 법률의 경우 논의가 이루어지면 큰 이슈가 되곤 합니다. 이런 식으로 이슈가 될 때마다 항상 뉴스에 등장하는 난해한 용어들이 있습니다. 국회의 법률안 처리와 관련한 '의안', '발의', '회부', '부의', '상정' 등의 용어가 그것이죠. 이런 용어들의 의미와 쓰임에 대해 알아보겠습니다. 1) 의안(議案) 제출된 안건. 즉, 회의에서 논의하고 심사할 의제를 의미합니다. 국회의 경우 법률 제정안, 개정안, 동의안 등이 주요 의안이 됩니다. 2) 발의(發議) 회의에서 심의할 안건(의안)을 제출하는 일로, 국회에서 국회의원이 의안을 내는 것을 의미합니다. 3) 회부(回..