Tap to restart

반가산기의 회로도 반가산기의 회로도를 보면 아래와 같다. A와 B 값이 입력되면 S와 C값이 출력된다. S는 합Sum, C는 올림수Carry를 뜻한다. 이진수 한자리수 덧셈 컴퓨터는 기본적으로 이진수로 이루어져 있으니 간단한 덧셈을 해보자. 이진수 덧셈을 해보면 아래와 같다. A+B A B 0 0 0 1 0 1 1 1 0 10 1 1 A+B가 S이면 좋겠지만 S는 오직 1과 0만 표현할 수 있다. 그래서 C가 따로 필요하다. 위 A+B를 나눠서 표현해보자. 아래처럼 나눠서 표현할 수 있다. A+B C올림수 S합 00 0 0 01 0 1 01 0 1 10 1 0 C올림수 C올림수의 결과를 다시 A와 B만 가지고 살펴보자. C A B 0 0 0 0 0 1 0 1 0 1 1 1 A와 B가 모두 1일 때만 1이..

Q. 메모이제이션이란? 글자 그대로 해석하면 ‘메모리에 넣기’라는 의미. 출처. 위키백과 피보나치 구현 예 def fib(n): if n == 1 or n == 2: return 1 return fib(n-1) + fib(n-2) fib(10) 실행결과는 55이다. 메모이제이션을 활용해서 피보나치 구현 예 memo = {} memo[1] = 1 memo[2] = 1 def fib(n): if n not in memo: memo[n] = fib(n-1) + fib(n-2) return memo[n] fib(10) 똑같이 실행결과는 55이다. 속도차이를 비교해보자. 그냥 구현한 경우 50을 구하는데 얼마나 걸릴까. 끝나지를 않는다. 계속 돌고 있다. 메모이제이션을 활용한 경우 금방 끝난다. 이미 구한 경우는..

A. Python v3.8.5, numpy, pandas 사용 가능 프로그래머스 코딩테스트 Python 개발 환경이 궁금했다. 2022년 4월 2일 현재 Python3의 버전은 3.8.5이다. 외부 라이브러리는 어떤 게 사용가능할까? pandas와 numpy는 사용 가능하다. pandas 버전은 v1.3.4, numpy 버전은 v1.21.4이다. 혹시 conda도 설치되어 있는지 확인해봤다. conda는 설치되어 있지 않다. sympy, scipy도 설치되어 있지 않다.

문제 출처: leetcode - 104. Maximum Depth of Binary Tree 문제 Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Input: root = [3,9,20,null,null,15,7] Output: 3 The number of nodes in the tree is in the range [0, 104]. -100 int: if root is None: return 0 queue = collect..

문제 출처: 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버 문제 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 2..

문제 출처: 프로그래머스 코딩테스트 연습 > 탐욕법(Greedy) > 체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수..

문제 출처: 프로그래머스 코딩테스트 연습 > 완전탐색 > 모의고사 문제 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인..

문제 출처: 프로그래머스 코딩테스트 연습 > 정렬 > K번째수 문제 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제..

출처: 프로그래머스 코딩테스트 연습 > 힙(Heap) > 더 맵게 문제 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록..

문제 출처: 프로그래머스 코딩테스트 연습 > 스택/큐 > 기능개발 문제 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도..

문제 출처: 프로그래머스 코딩테스트 연습 > 해시 > 완주하지 못한 선수 문제 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 part..

A. 구현할 수 있다. 재귀함수를 활용해서. 재귀함수로 구현한 구구단 예. max_number1 = 9 max_number2 = 9 def get_multiplaction(number1, number2): print(f'{number1} X {number2} = {number1*number2}') if number2 < max_number2: return get_multiplaction(number1, number2 + 1) else: number2 = 1 print() if number1 < max_number1: return get_multiplaction(number1 + 1, number2) get_multiplaction(2, 1) 클래스로 구현한 예

소수 목록 구하기 소수는 약수가 1과 자기 자신뿐인 수를 말한다. 그래서 소수는 2, 3, 5, 7 등이다. 4는 약수가 1, 2, 4라 소수가 아니다. 10까지 소수를 구하라는 문제가 있을 때, 가장 쉽게 떠오르는 방식은 소수의 정의대로 2부터 시작해서 자기 자신보다 작은 수까지 쭉 나눠보는 거다. 2는 소수 3은 2까지 나눠서 안 떨어지니 소수! 4는 2부터 나눠서, 2로 바로 나눠떨어지니 중지. 5는 2부터 4까지 나눠서 안 떨어지니 소수! 이렇게 구현하면? 코딩 테스트에서 시간초과로 떨어진다. 너무 오래 걸리니까. 이럴 때 검색이 필요하다. 소수 구하기를 검색하다보면 에라토스테네스의 체가 나온다. 에라토스테네스의 체란? 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. (출처: 위..

연결 리스트Linked List란? 각 노드(node)가 데이터와 포인터를 가지고 한 줄로 연결된 자료 구조. 참고: 위키백과 연결 리스트 그렇다면 노드란? 위 그림에서 네모 두 칸이 노드다. 12가 데이터, 다른 노드를 가리키고 있는 화살표가 바로 포인터다. 파이썬 노드 코드 예 노드를 한 줄로 연결하게 되면 연결 리스트가 된다. 연결 리스트 중 포인터가 하나인 경우가 단일 연결 리스트이다. 단일 연결 리스트 파이썬 구현 예 아래는 파이썬으로 구현한 단일 연결 리스트 예이다. 앞에서 살펴본 스택이나 큐보다 훨씬 복잡하다. 노드란 객체를 만들어서 연결하기 때문에 더 복잡해 보인다. 코드를 이해하기 위해서는 천천히 살펴볼 필요가 있다. 그렇다면 왜 연결 리스트를 사용할까? 많은 프로그래밍 언어에서 배열이란..

큐Queue란? 먼저 넣은 데이터가 먼저 나오는 자료 구조를 큐라고 한다. 먼저 들어간 것이 먼저 나온다는 First In First Out, FIFO라고 말하면 큐다. 영어 사전에서 Queue를 찾으면 줄을 서다, 차례를 기다리는 줄을 뜻한다는 것을 확인할 수 있다. 식당에서 줄을 섰다면? 당연히 먼저 줄에 서 있던 사람이 먼저 식당으로 들어가야 한다. 참고: 위키백과 큐 파이썬 큐 예제 아래는 파이썬으로 구현한 큐 예이다. 큐를 구현하는 것 자체는 어렵지 않다. 큐의 의미 그대로 값을 순서대로 넣고 enqueue(), 먼저 넣은 값을 dequeue() 호출 시 꺼내오면 된다.

스택Stack이란? 스택은 한쪽 긑에만 자료를 넣거나 뺄 수 있는 선형 구조. 나중에 들어간 것이 먼저 나온다. Last In First Out, LIFO라고 하면 스택이다. 영어 단어 stack 뜻 자체가 쌓다, 더미이다. 간단히 접시가 쌓여 있는 형태를 떠올리면 된다. 접시를 쌓아 놓았을 때 위에서부터 쓰게 된다. 참조: 위키백과 스택 파이썬 스택 예제 아래는 파이썬으로 구현한 스택 예이다.