Passwd

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132267 다음과 같은 콜라 문제가 있다. 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가? 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다. 상빈이는 그림과 같은 방법으로 콜라 문제를 풀어냈다. 빈 콜라병 20병을 가져가서 10병을 받는다. 받은 10병을 비우고 5병을 받는다. 5병 중 4병을 비우고 2병을 받고, 또 2병을 비우고 1병을 받는다. 받은 1병과 5병을 받았을 때 남은 1병을 비워서 1병을 또 받는다. 따라서 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받는다. 만약 빈 병 a개를 가져다..

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/178871 얀에서는 매년 달리기 경주가 열린다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부른다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 "soe" 선수가 "mumu" 선수를 추월했다는 뜻이다. 현재 등수 순서대로 선수들의 이름이 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해..

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12909 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다. 예를 들어 - "()()" 또는 "(())()" 는 올바른 괄호다. - ")()(" 또는 "(()(" 는 올바르지 않은 괄호다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 작성하라. 풀이 괄호는 가장 마지막에 열린 것부터 닫힌다. 그리고 Stack은 가장 마지막에 추가된 값이 먼저 삭제된다. 괄호와 Stack의 특징을 ..

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42579 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를..

백준허브(BaekjoonHub) LeetCode의 개인 풀이를 Git 저장소에 자동으로 Push 하는 LeetHub를 포크 해서 개발된 크롬 확장 프로그램. 오픈 소스로, 기존에 풀었거나 풀어낼 문제 풀이를 저장소를 통해 관리하고 싶다면 사용할 수 있다. 설치 및 설정 1. 아래 설치 크롬 웹 스토어 링크로 접근한 뒤 Chrome에 추가 버튼을 클릭한다. 링크 : 백준 허브 크롬 확장 프로그램 2. 브라우저 오른쪽 상단 바에서 확장 프로그램 > BaekjoonHub를 클릭한 뒤, GitHub와 연동하기 위한 Authenticate 버튼을 클릭한다. 3. Github에 로그인하면, 아래와 같이 BaekjoonHub를 통해 관리할 Github 저장소를 설정할 수 있다. 새 저장소를 만들거나 기존 저장소로 연..

메모이제이션 메모이제이션은 메모리에 넣기라는 의미로 기억되어야 할 것이라는 뜻의 라틴어 memorandu에서 파생되었다. 프로그램이 같은 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장함으로써 같은 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 방법이다. 동적 계획법의 핵심이 되는 기술로 메모리라는 공간 비용을 사용하여 계산에 필요한 시간 비용을 줄이는 방법이다. 캐싱이라고 표현하기도 한다. 예시 - 피보나치 수열 아래와 같이 재귀함수를 이용한 피보나치 수열 함수가 있다고 하자. def fib(n): if n == 1: return 0 if n == 2: return 1 return fib(n - 1) + fib(n - 2) fib 함수의 재귀호출을 트리 형태로 나타내면 아래와 ..

문제 https://www.acmicpc.net/problem/9546 n명의 승객을 태우고 있는 3000번 버스는 버스 정류장마다 문을 연다. 정류장마다 타고 있는 승개의 수의 절반과 반 명의 승객이 내린다. k개의 정류장에서 승객이 내렸고, 마지막 정류장에서 승객이 없었다면 맨 처음 타고 있던 승객이 몇 명인지 구하여라. 풀이 t번째 정류장에서의 승객의 수를 \( n_t \)라고 하자. 정류장마다 내리고 남은 승객의 수는 아래와 같이 계산할 수 있다. $$ \begin{matrix} n_t - (0.5n_t + 0.5) = n_{t+1} \\ 0.5n_t - 0.5 = n_{t+1} \end{matrix} $$ 마지막 정류장에서의 승객이 0명이므로, 정류장이 1개인 경우, 2개인 경우, 3개인 경우…..

에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 즉, 2부터 n까지의 모든 수를 나열한다. 지우지 않은 수 중 가장 작은 수를 찾는다. 이 수는 소수이다. 자기 자신을 제외한 소수의 배수를 모두 지운다. 더 지울 수가 없을 때까지 2 ~ 3 과정을 반복한다. 또는 \( \sqrt{n} \)의 정수부보다 작은 소수의 배수를 지우고 남는 수는 모두 소수이다. 그림의 경우, \( 11^2 > 120 \)이므로, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다. 구현 Python으로는 아래와 같이 구현할 수 있다. def prime_list(n): # 에라토스테네스의 ..

문제 https://www.acmicpc.net/problem/2998 창영이는 2진법 수를 8진법 수로 변환하려고 한다. 창영이가 사용한 방법은 아래와 같다. 1. 2진수의 길이가 3으로 나누어 떨어질 때까지 수의 앞에 0을 붙인다. 2. 그 다음, 3자리씩 그룹을 나눈다. 3. 아래의 표를 참고해 8진수로 바꾼다. 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 창영이가 사용한 방법을 이용해 2진수를 입력받아 8진수를 바꾸는 프로그램을 작성하라. 입력의 첫번째 줄에 2진수가 주어진다. 풀이 Python에서 2진수를 입력받는 방법과 정수를 8진수를 변환하는 방법을 알면 간단하게 해결할 수 있다. 1. int(x, base=10) int 함수의 base는 x의 진수에..

문제 https://www.acmicpc.net/problem/9081 단어를 입력받아, 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하라. 입력 첫 줄은 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 알파벳 대문자로만 이루어진 단어로 공백은 없다. 풀이 파이썬에서 문자(chr)는 대소 관계 비교가 가능하므로 직전에 풀었던 2022.05.10 - [BOJ] 10972 - 다음 순열(next permutation) 문제를 활용하면 쉽게 풀어낼 수 있다. 차이가 있다면 값의 중복 여부인데, 이는 값을 교환할 위치 i - 1과 j를 찾아내려 갈 때의 조건을 크거나 같을 때 반복하도록 수정하면 된다. import sys..