Algorithm

백준 10844번 쉬운 계단수n(자릿수)가 1일 경우, 0을 제외한 모든 숫자(0으로 시작하는 수는 없다고 적혀있다)가 맨 뒷자리에 있을 경우는 각 1이다.n이 2일 경우 맨뒷자리가 0일 때 경우는 10, 1이 오는 경우는 21, 2가 오는 경우는 12, 21이다.이렇

백준 2156번 "포도주 시식"연속으로 놓여져 있는 세잔을 연속해서 마실 수 없다에 주목해야하는 문제이다.이 조건으로 3가지 경우를 고려해야 하는것을 알 수있는데i-1번째 잔을 마시지 않고 i번째 잔을 마신경우arri + dpi-2i-1번째 잔을 마시고 연속해서 i번째

백준 11053번 가장 긴 증가하는 부분수열'LIS'동적 계획법을 이용해 풀어야 한다.수열을 순차적으로 반복하여 현재 순서의 숫자와 앞 숫자들을 비교하여 현재 숫자의 k값(현재 숫자가 부분 수열에 들어갈 때 순서)을 수정해나가야 한다.ex) arr = 10, 20, 1

백준 11054번 가장 긴 바이토닉 부분수열LIS의 응용문제.11053번과 비슷하게 문제를 풀면된다.11053번과 다른 것이 있다면 내림차순 수열을 구하고, 오름차순 수열과 내림차선 수열이 만나 최대 길이를 이루는 특정 위치를 구해야 한다.입력받은 수열을 뒤집어 내림차

백준 2565번 '전깃줄'LIS 응용문제.전봇대 하나를 정렬해주고 다른 전봇대에서 LIS를 구하면 된다.나머지는 11053번을 참조하자.

백준 9184번 신나는 함수 실행문제에 유사코드가 적혀있어 어려운 문제는 아니였다.다만 유사코드 그대로 코드를 구현하면 무조건 시간초과가 뜨게되니 메모이제이션을 이용하자.메모이제이션동일한 계산을 반복해야 할 경우 한번 계산한 결과를 메모리에 저장해 두었다가 꺼내쓰는 방

백준 1912번 연속합dp 배열의 첫 인덱스에 arr0을 넣어 비교할 수 있도록 하고,dpi-1 + arri과 arri 중 최대값을 dpi에 넣는 것을 반복한다.답은 dp배열의 최댓값에 해당한다.

백준 12865번 평범한 배낭유명한 01 배낭(01 Knapsack) 문제.배낭 문제는 물건을 쪼개는게 가능한 Fraction Knapsack과 물건을 쪼갤 수 없는 01 Knapsack 두가지로 분류된다.Fraction Knapsack의 경우는 가치가 큰 물건부터 선

백준 11047번 동전 0K보다 작은 Ai의 최대값을 K를 나누어 그 몫을 count에 추가하고, K에 다시 나머지를 저장한다.K의 값이 0이 될 때까지 반복하면 된다.

백준 1931번 회의실 배정처음엔 시작 시간값을 정렬하고 2중 반복문을 이용하여 각 시작 시간에 대하여 최대 회의수를 구한 다음 그 중 최댓값을 구하는 방식으로 코드를 짰었는데, 이게 시간초과가 나왔다....회의 시작시간의 정렬 후 종료시간을 한번 더 정렬하는 방식으로

백준 11399번 ATM입력받은 배열을 오름차순으로 정렬하고, 누적값을 차례로 더해준다.문제만 이해하면 코드작성은 1분정도 걸리는 쉬웠던 문제

백준 1541번 잃어버린 괄호\-를 기준으로 괄호를 치면 최솟값을 구할 수 있다.사실 문제의 규칙을 구하는 것보다 코드내에서 문자열처리가 더 오래 걸렸던 문제....

백준 5086번 배수와 약수a, b를 입력받아 두 수에 대한 조건문을 걸어주면 되는 쉬운 문제

백준 13305번 주유소반복문을 진행하면서 가격의 최솟값을 저장하고(tmp), 각 도시의 가격을 순서대로 비교하여가격이 더 낮다면 tmp에 저장한 후 거리와 곱한 후 ans에 더해주고,가격이 더 높다면 tmp값 그대로 거리와 곱한 후 ans에 더해주면 된다.

백준 1037번 약수진짜 약수의 최솟값 \* 진짜 약수의 최댓값 = N

백준 2609번 최대공약수와 최소공배수유클리드 호제법을 이용하면 소인수분해 없이 최대공약수와 최소공배수를 구할 수 있다.유클리드 호제법은 a, b 두 수가 있으면, a, b의 최대공약수와 b와 a를 b로 나눈 나머지 r의 최대공약수는 같다는 점을 이용한다.이를 반복하여

백준 1934번 최소공배수여기를 참조!

문제 백준 2981번 검문 풀이 오름차순의 입력값 a, b를 받았을 때, a와 b의 최소공약수에 관한 식을 정리하면 다음과 같다. 이걸로 b-a는 a, b의 최소공약수의 배수라는 것을 알 수 있다. 또한 같은 나머지 R을 가지게 하는 숫자 M에 대한 정리를 하면

백준 3036번 링첫 원의 둘레/각 원의 둘레를 계산하여 기약분수로 표현하면 된다.(최대공약수를 이용한 풀이도 있다. 검색 ㄱㄱ)분수의 표현은 Fraction()을 이용하여 표현하였다.

백준 11050번 이항 계수1C(n, k) = n!/k!(n-k)! 점화식을 사용하여 이항 계수를 풀면 된다.파이썬의 math 라이브러리의 factorial() 함수를 사용하여 팩토리얼 계산을 하였다.

문제 백준 11051번 이항 계수2 풀이 이항 계수1 Python 코드

백준 1010번 다리놓기n개의 사이트에서 m개의 사이트로 다리를 놓는 경우의 수를 찾는 문제이다.m >= n인 점을 이용하여 반대로 생각해 m개의 사이트에서 n개의 다리를 놓는 경우의 수를 찾게 되면 C(m, n)을 계산하면 된다.

백준 1676번 팩토리얼 0의 개수입력받은 N을 팩토리얼 함수로 연산한 후, 그것을 문자열로 바꿔 끝에서 부터 0의 개수를 카운트 해준다.임의의 수 N을 인수분해해보면, 5가 곱해질 때 마다 0의 개수가 하나씩 늘어난다는 것을 알 수 있다.N의 범위는 0부터 500사이

백준 2004번 조합 0의 개수뒷자리에서 0의 개수는 10이 곱해진 횟수와 같다.10은 2 \* 5이므로, nCm에서 2의 개수와 5의 개수의 최소값을 구하면 된다.(10이 되려면 2와 5의 쌍이 맞아야 하므로...)

백준 10828번 스택자료구조 '스택'의 구현 문제파이썬 리스트를 이용하여 구현하였다.

백준 10773번 제로스택 문제. 10828번보다 훨씬 쉬웠고, 리스트로 스택을 구현하였다.

백준 4949번 균형잡힌 세상9012번과 비슷한 문제.다만 소괄호와 대괄호의 순서를 고려해야 하는 문제이다.따라서 반복중 가장 최근에 나왔던 괄호가 소괄호인지 대괄호인지를 검사하여 짝이 맞는지 확인하는 방식으로 코드를 짜면 된다.

백준 1874번 스택수열문제풀이도 문제풀이지만 문제를 이해하는 데 더 시간을 썼던 문제.1부터 n까지 오름차순으로 들어오는 숫자들을 차례대로 스택에 넣으며주어진 수열과 비교하여 주어진 수열의 순서와 같이 pop해준다.연산의 결과 스택이 비어있으면 주어진 수열과 같은 수

백준 17298번 오큰수문제 자체는 어렵지 않지만 시간을 줄여야해서 신경쓰이던 문제.처음엔 이중 for 반복을 이용하여 풀었으나 계속해서 시간초과가 뜨길래 찾아보니 스택을 이용하여 풀어야 한다더라...다른 스택 관련 문제와 다른 점은 인덱스를 스택에 넣어야 하는 점이다

백준 18258번 큐2큐 구현 문제.시간 제한이 걸려있으므로 que.pop(0)보단deque 라이브러리를 사용하여 popleft()를 사용하는게 더 빠르다.

백준 2164번 카드 2큐를 응용하면 쉬운 문제.1 ~ N 까지의 정수를 가진 큐에서 pop을 두번하고 두번째 pop한 정수를 다시 push해준다.이를 큐의 정수가 하나 남을 때까지 반복해주면 된다.

백준 11866번 요세푸스 문제 01 ~ N까지의 큐를 계속 해서 pop하고 push하는 과정에서K번째 pop되는 수를 다시 push하지 않고 요세푸스 수열에 차례대로 넣어주면 된다.

백준 1966번 프린터 큐큐를 돌리면서 가중치가 높은 순서대로 인덱스를 정답 리스트로 빼준다.이 후 정답 리스트에서 해당 인덱스의 순서를 찾아서 출력

백준 10866번 덱18258문제에서 appendleft()와 pop()을 추가해 주면 된다.

백준 1021번 회전하는 큐덱을 이용해 푼 문제.원하는 원소를 덱에서 뽑아내려면 해당 원소를 덱의 첫번째로 위치시켜야 한다.이를 위해 덱을 왼쪽에서 오른쪽 혹은 그 반대로 회전시켜야 하는데,덱을 회전시키는 수를 최소로 줄이기 위해서 해당 원소의 현재 위치가 덱의 가운데

백준 5430번 AC시간 복잡도를 줄일 필요가 있는 문제이다.replace()를 이용하여 R연산이 두번 연속일 경우 연산을 행하지 않도록 명령어를 고쳐야하며,연산중 R연산이 나온다고 그때 그때 reverse()를 실행하지 않고 isReversed 불린 변수를 만들어큐의

백준 2630번 "색종이 만들기"쿼드트리를 이용한 문제.계속해서 4개의 단말로 나누어진다고 해서 쿼드트리이다.배열의 전체를 검사하여 하나라도 틀리면 4개의 분면으로 나누고 재귀를 이용해 반복한다.1 혹은 0이 정사각형을 이루면 해당 변수에 1을 더해주고 재귀를 멈추고

백준 1992번 쿼드트리쿼드트리를 이용한 분할 정복 문제.2630번과 전체적으로 비슷한 문제지만 다른점이 있다면,4분면으로 나누고 재귀에 들어가기 전, 괄호를 열고 해당 순서의 재귀가 끝나면 괄호를 닫아주어야 한다.

백준 1629번 곱셈문제를 있는 그대로 접근해서 (a^b)%c를 계산하면 시간초과가 뜬다.시간을 줄이기 위해선 분할 정복을 이용하여 문제를 해결해야 한다.b가 홀수일 경우,(a^(b//2))^2 \* ab가 짝수일 경우 (a^(b//2))^2 와 같이 나누어 주어 계산

백준 2740번 행렬곱셈이미지 출처 : 위키백과3중 반복문을 이용하여 행렬곱셈을 처리하면 된다.

프로그래머스 체육복그리디알고리즘을 이용하여 풀었다.중복을 없애기위해 set을 사용하였고, 여벌체육복을 가져온 학생이 도난을 당했을 수 있으므로도난자와 여벌 체육복 휴대자의 집합을 서로 빼주었다.

프로그래머스 K번째 수슬라이실을 통해 리스트를 잘라주고 sorted()를 이용해 정렬하면 되는 쉬운 문제.

백준 6549번 히스토그램에서 가장 큰 직사각형굉장히 오랜시간 걸려서 푼 문제....스택을 활용하여 문제를 풀었다.인덱스를 차례대로 스택에 넣어주다가 arri값이 arr\[stack-1](스택의 최상위)보다 작은 경우 stack에서 pop을 하고 그 값을 이용해 해당

백준 1920번 수찾기기본적인 이분 탐색으로 풀 수 있는 문제파이썬의 경우 set자료형을 이용하여 풀면 더 쉽고 효율적으로 풀 수 있지만연습을 위해 이분 탐색으로 문제를 풀었다.

프로그래머스 크레인 인형뽑기 게임moves값에 해당하는 board의 열을 확인하여 0이 아닌 값이 나오면 스택에 그 값을 넣어주고 board의 해당자리에 0을 다시 넣어준다. moves 값의 반복이 끝날 때 마다 스택 최상단의 두 수가 같은지 확인하여 answer값을

문제 프로그래머스 모의고사 풀이 완전 탐색 문제. 반복에 앞서 수포자 1, 2, 3의 정답배열을 answers만큼 늘려줄 필요가 있다. 수포자의 정답 배열 * (문제 정답 수//수포자 정답 배열의 수 + 1)을 해주면 된다. 이 후 완전탐색으로 3명의 문제가 얼마나

프로그래스 메뉴 리뉴얼조합을 이용하여 문제를 풀어야 한다.itertools의 combinations 라이브러리를 이용하여 코스 수와 동일한 크기의 각 주문의 부분집합을 전부 sets에 넣어주고, Counter 라이브러리를 이용하여 코스의 크기마다 가장 많이 중복된 부분

백준 10816번 숫자카드2처음에는 이분 탐색을 진행하다 mid값과 찾으려는 수가 같다면 mid값 전 후에 같은 숫자들이 있을 것이니 해당 반복의 리스트에서 카운팅을 하는 방법으로 코드를 작성했다.허나 이 방식으로는 시간 초과가 떳고 다시 생각해보니 최악의 경우(첫 반

백준 1654번 랜선자르기이분탐색 문제이분 탐색을 진행하며 잘라진 선의 개수가 n값이 될 때 right값이 각 줄의 최대 길이가 된다.

백준 2805번 나무 자르기이분 탐색으로 푼 문제.1654번문제와 비슷하게 풀었는데 python3로 돌렸을 땐 시간 초과가 뜨고 pypy3로 돌렸을 땐 돌아가는 코드를 작성했다....나중에 시간이 되면 python3에서도 시간초과가 안뜨도록 수정해봐야 곘다.

백준 2110번 공유기 설치전에 풀었던 이분탐색보다 좀 더 어려웠던 문제.공유기를 설치할 수 있는 최소거리와 최대거리를 가지고 시작하여중간값을 통해 특정 거리를 두고 얼만큼의 공유기를 설치할수 있느냐를 알아내어야 한다.공유기 설치 숫자에 따라서 다른 이분탐색 문제와 같

프로그래머스 1단계 폰켓몬 처음에 문제를 봤을 땐 조합문제인가 싶었는데 생각해보면 간단한 문제이다.N개의 포켓몬의 종류를 파악하고(코드에선 set()으로 중복을 제거), 포켓몬 수 N의 절반보다 종류수가 적으면 종류수가 정답이 되고, 종류수가 N/2보다 많으면 N/2가

프로그래머스 1단계 키패드 누르기문제 자체는 쉬웠지만 푸는 시간은 생각보다 오래걸렸던 구현 문제였다.기본적으로는 numbers 리스트의 순서대로 반복하며 왼손이 누를 경우 answer 문자열에 'L', 오른손이 누를 경우 'R'을 추가해 주고 누른 손의 위치를 저장해

프로그래머스 2단계 짝지어 제거하기스택을 사용하면 쉬운 문제!

백준 1300번 K번째 수처음 문제를 보고선 바로 반복문 두개 돌려서 2차원 배열만들고 오름차순으로 정렬해서 문제풀었는데, 메모리 초과가 뜨더라....여튼 이런 방식이 너무나도 비효율적이란 걸 깨닫고 검색 좀 해보니깐 이 문제도 이분탐색 문제였다.1차원 배열을 오름차순

백준 12015번 가장 긴 증가하는 부분 수열 211053번과 같은 문제지만 시간을 더 빡빡하게 보는거 같다.문제해결법 자체는 같으니 참고 하시라.11053번과 같이 DP를 활용하여 문제를 풀 경우 반복을 진행하며 배열의 뒤에 있는 수들의 순서를 재확인 할때 전부 확인

프로그래머스 2단계 오픈채팅방카카오 2019 공채 출제 문제.문제 자체는 어렵진 않은거 같은데 구현이 약간 노가다라서 실전에 나오면 어지러울거 같은 문제이다...출력 로그를 담당하는 log리스트와 사용자의 닉네임을 관리하는 uid 딕셔너리를 만들어서 record값을 순

백준 11279번 최대 힙파이썬의 heapq 라이브러리를 이용해 우선순위 큐를 구현하였다.heapq가 최소 힙만을 지원하기 때문에 입력하는 x값을 음수로 처리하여 최대 힙처럼 사용하여야 한다.

백준 1927번 최소 힙11279번과 같이 힙을 이용하여 우선순위 큐를 구현하면 된다!

백준 번 절대값이 가장 작은 수를 출력해야하는 최소 힙.힙에 x의 절대값, x쌍으로 이루어진 튜플을 넣어줌으로 써 절대값을 바탕으로 정렬을 할 수 있도록 한다.

프로그래머스 2단계 타겟 넘버재귀를 이용, DFS를 구현하여 풀었다.다음 숫자를 계산할 때 더하는 경우와 빼는 경우를 분기로 삼아 재귀를 계속하다가, 마지막 숫자의 연산이 끝날 때 타겟넘버와 연산값이 같은 경우 1을 리턴하여 결과값을 전부 더해주는 식으로 코드를 작성하

프로그래머스 2단계 기능개발큐의 개념을 이용하여 푼 문제.주어진 리스트의 순서대로 소요되는 날짜를 구한다.앞 작업이 끝나지 않으면 해당 작업이 출시되지 못하므로,앞 작업이 소요되는 시간이 해당 작업이 소요되는 시간보다 길다면 앞 작업의 출시일에 +1을 해주고,반대의 경

프로그래머스 2단계 더 맵게가장 작은 수와 그 다음 작은 수를 스코빌 계산하여 이를 모든 수가 k값을 넘을 때까지 반복하여야 한다.다만 처음 풀었을 땐 리스트에서 min값 두개 빼와서 사용하였더니 효율성 검사를 통과하지 못하였다.힙을 사용하여 문제를 풀었더니 해결!

프로그래머스 2단계 "전화번호 목록"먼저 주어진 phone_book을 정렬해주어 시작이 비슷한 번호끼리 인접하게 해두고, booki가 booki+1의 접두어인지를 확인해 주면 된다.startswith()는 어떤 문자의 처음이 특정 문자로 시작될 때 True를 반환하는

프로그래머스 2단계 위장백준 9375번 문제와 같은 문제각 옷 종류의 수 + 1(해당 옷종류를 안입는 경우)를 전부 곱해준 다음1을 빼준 것(전부 안입는 경우)이 답이다.

프로그래머스 2단계 프린터백준 1966번과 동일한 문제가중치큐와 인덱스큐를 같이 돌려가면서 출력된 순서대로 인덱스가 나열되있는 리스트를 만들고,location에 해당하는 값의 인덱스+1(출력된 순서)을 반환해주면 된다.

프로그래머스 2단계 다리를 지나는 트럭작성중...

프로그래머스 "주식 가격"백준 17298번유사한 문제.스택에 차례대로 가격을 넣어주고 빼주며 스택에 존재했던 시간 만큼 answer배열에 1씩 더해준다.다만 스택을 단순하게 이용하는 것이 아니라 인덱스를 스택에 넣는 방식으로 풀었으며, 단순히 for문 도배 후 반복하여

프로그래머스 '이중우선순위 큐'문제를 일반적인 리스트의 max 및 min을 사용해도 문제없이 풀수 있지만 문제 분류가 힙으로 되어있는 만큼 힙을 이용하여 문제를 풀었다.파이썬의 heapq가 기본적으로 최소힙으로 이루어져 있어 최대값을 pop해주는데 있어 손을 좀 써야했

프로그래머스 '가장 큰 수'기본적인 문제의 풀이는 간단하다.어떻게 이어붙이든 만들어진 수는 모두 같은 자리수를 가지고 있으니 앞자리가 큰 수부터 순서대로 이어붙이면 된다.파이썬에서 sorted() 혹은 .sort()로 문자열을 정렬할 때, 아스키 코드값에 기반하여 첫째

프로그래머스 'H-Index'(https://programmers.co.kr/learn/courses/30/lessons/42747?language=python3문제 이해하는데 1시간정도 걸린 문제.먼저 citations을 정렬한다.citations\[i]가

프로그래머스 '큰 수 만들기'그리디 알고리즘을 이용하여 문제를 풀었다.answer문자열을 스택처럼 사용하여 number의 숫자를 하나씩 넣어주며 반복을 한다.이 때 전에 들어갔던 문자열 answer\[-1]이 number\[i]보다 작을 경우 answer\[-1]을 a

프로그래머스 '구명 보트'people을 정렬한 후 people에서 보트에 타지 않은 무게가 가장 낮은 사람과 무게 합이 limit이하인 사람중 가장 limit에 가까운 사람을 조합하여야 한다.다만 위 풀이처럼 리스트와 pop()을 이용할 시 효율성테스트에서 탈락하게 된

프로그래머스 Level3 정수 삼각형각 층마다 좌측과 우측은 바로 위 숫자 하나와 계산을 하면 되니 각각triangle\[i-1]\[j] triangle\[i-1]\[j-1]과 계산을 하면 되고,중간에 있는 숫자는 위 두개의 숫자중 값이 더 큰 값과 계산을 하면된다.

프로그래머스 Level3 '등굣길'최소 동선으로 움직이기 위해선 왼쪽에서 오른쪽 혹은 위에서 아래 두가지 방향으로 움직이게 되니, 해당 위치로 가는 최소 동선은 해당 위치의 위쪽과 왼쪽으로 가는 최소동선의 합이 된다.즉, 반복문을 돌리면서 dp\[i]\[j] = dp\

프로그래머스 'N으로 표현'예제와 같이N = 5일 경우 N\[2]는 N\[1]과 N\[1]을 이어붙이거나 사칙연산한 것이고, N\[3]는 N\[1]과 N\[2]를 이어붙이거나 사칙연산한 것이다.즉, N\[i]는 N\[1] ~ N\[i-1]의 세트리스트를 가지고 만들수

프로그래머스 '입국심사'분류가 이분탐색으로 되었있었는데 어떠한 방식으로 이분탐색을 이용해야되는지 오래 고민했던 문제.나는 심사관들에게 시간을 주고 이 시간동안 심사관들이 몇명의 사람들을 심사하는지 체크하고,각 심사관들이 심사한 사람수의 합이 n명인 최소값을 찾는 방식을

프로그래머스 '징검다리'주어지는 distance의 범위가 1 ~ 1,000,000,000인걸 확인하고 이분탐색을 써야될거라고 알긴 했지만,이분탐색의 기준을 잡는데 한 세월 걸린 문제. (과연 level4....)이 문제에서 mid값은 돌 사이 거리간 최소값중 최대값이

프로그래머스 '섬 연결하기'Kruskal 알고리즘을 이용하여 최소신장트리(MST)를 만들어야 한다.Kruskal 알고리즘은 비용이 가장 낮은 간선부터 선택하는 그리디 알고리즘을 사용하되,간선간의 사이클이 발생하지 않게 하는 것이 핵심이다.이 문제에선 비용이 낮은 간선부

프로그래머스 소수찾기itertools의 permutations(순열)을 이용하여 글자를 조합하는 경우의 수를 찾아내고,set 자료형을 이용하여 중복을 제거한다.그 뒤 소수인지 판별하면 되는 문제!소수는 에라토스테네스의 체를 이용하여 구하였다.출처 : 위키백과이런 식으로

문제 백준 번 풀이 Python 코드

백준 9375번 패션왕 신혜빈각 종류의 의상을 입는 경우의 수를 곱해주면 된다.즉, 해당 종류의 의상 수 + 1(해당 종류를 입지 않는 경우)를 의상의 종류 모두 곱해준 뒤,1을 빼주면 된다(알몸인 경우 제외를 위해 -1을 해준다.).

문제 프로그래머스 '네트워크' 풀이 3단계 문제라고 쫄았지만, 기본적인 dfs문제였다.... 모든 노드를 반복하며 네트워크 순회를 위한 함수 dfs를 실행한다. dfs를 통해 방문한 노드들은 isVisited 배열을 통해 해당 노드에 방문했었는지를 저장하고, 해당

프로그래머스 '단속카메라'그리디 알고리즘을 사용하여 풀어야하는 문제.첫 카메라 위치를 -30001에 놔두고(고속도로 진입위치의 최소값이 -30000이기 때문),카메라 위치가 진출 위치보다 뒤에 있으면 카메라 위치를 진출 위치로 옮기는 것을 반복한다.이와 같은 반복으로