바쁜 일상에서도 필요하다고 생각되는 알고리즘 공부를 하기 위해서 하나씩 리트코드를 풀어나가야겠다..!
리트코드isalnum(): 영문자, 숫자 여부를 판별하는 함수 해당하는 문자만 추가lower(): 모두 소문자로 변환pop(): 제일 마지막에 들어간 것 빼내기, 인덱스 지정가능
리트코드투포인터를 이용한 스왑
리트코드로그의 가장 앞 부분은 식별자다.문자로 구성된 로그가 숫자 로그보다 앞에 온다.식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.숫자 로그는 입력 순서대로 한다.
https://leetcode.com/problems/most-common-word/데이터 클렌징: 입력 값에 대한 전처리 작업정규식 사용\\w는 단어문자(word character)를 의미하며, ^은 not을 의미한다위 코드의 정규식은 단어 문자가 아닌 모든
리트코드일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다.애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것으로 애너그램 관계인 단어들을 정렬하면, 서로 같은 값을 가게 되기 때문이다.sorted() 는 문자열도 잘 정렬하며 결과를
리트코드값 또는 변수 엘리먼트의 집합으로 구성된 구조하나 이상의 인덱스 또는 키로 식별된다.배열은 어느 위치에나 O(1)에 조회가 가능하다는 장점이 있다.물리 메모리에 순서대로 배치된다.int의 사이즈는 컴파일러와 프로세서의 구조에 따라 상이하다.메모리에 대한 접근은
리트코드가장 높은 막대를 살펴보면 최대 높이는 3이지만 100이어도 상관이 없다.막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다.최대 높이의 막대까지 각각 좌우 기둥 최대 높이 left_max, right
리트코드배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라앞뒤로 같은 값이 있을 경우, 이를 쉽게 처리하기 위해 먼저 sort() 함수를 사용해 정렬한다.정렬의 시간 복잡도는 O(nlogn)이며, 파이썬의 팀소트는 정렬 속도가 매우 빠르다.그림에서 i
리트코드n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라페어의 min()을 합산했을 때 최대(Argmax)를 만드는 것은 결국 min()이 되도록 커야 한다는 것이고, 뒤에서부터 내림차순(Descending Order)으로 집어넣으면
리트코드배열을 입력받아 outputi가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라제약사항: 나눗셈을 하지 않고 O(n)에 풀이하라(미리 전체 곱셈 값을 구해놓고 각 항목별로 자기 자신을 나눠서 풀이하는 방법은 안된다는 뜻이기도 하다.)자기 자신을 제
리트코드한 번의 거래로 낼 수 있는 최대 이익을 산출하라하지만 이 방식은 타임 아웃으로 풀리지 않는다.range는 range(시작숫자, 종료숫자, step)의 형태로 리스트 슬라이싱과 유사합니다.range의 결과는 시작숫자부터 종료숫자 바로 앞 숫자까지 컬렉션을 만듭니
연결 리스트가 팰린드롬 구조인지 판별하라파이썬의 리스트는 q.pop(0) != q.pop() 형태로 얼마든지 인덱스를 지정해서 비교가 가능하기 때문에 이 문제는 리스트만으로도 충분히 풀이가 가능하다.q.pop(0)과 같이 동적 배열로 구성된 리스트는 맨 앞 아이템을 가
리트코드정렬되어 있는 두 연결 리스트를 합쳐라첫번째 부터 비교하면서 리턴하면 쉽게 풀 수 있다.그러나, 이 짧은 코드에 너무 많은 내용이 함축되어 있어서 이해하기가 쉽지 않을 뿐더러, 재귀가 포함되어 있어 더욱 어렵다.일단 l1, l2의 값을 비교해 작은 값이 왼쪽에
연결 리스트를 뒤집어라 이 문제는 매우 일반적이면서도 활용도가 높은 문제로, 실무에서도 빈번하게 쓰인다. 다음 노드 next와 현재 노드 node를 파라미터로 지정한 함수를 계속해서 재귀 호출한다.node.next에는 이전 prev 리스트를 계속 연결해주면서 node
리트코드역순으로 저장된 연결 리스트의 숫자를 더하라
리트코드연결 리스트를 입력받아 페어(pair) 단위로 스왑하라진관적인 방법인 풀이로, 다소 변칙적인 방법이기도 하다.연결리스트의 노드를 변경하는게 아닌, 구조는 그대로 유지하되 값만 변경하는 방법이다.대개 연결 리스트는 복잡한 여러가지 값들의 구조체로 구성되어 있고,
리트코드다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제다.여기서는 투포인터가 중앙을 중심으로 확장하는 형태로 풀이한다.슬라이싱과 s3처럼 인덱스로 직접 조회하는 것은 숫자를 표기하는 방식이 다르므로 주의가 필요하다.예: s = '12345'일 때 s1:3은 23이 나
리트코드연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라.공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라이런 문제는 제약이 없을 경우 연결 리스트를 리스트로 바꾸고 파이썬 리스트가 제공하는 슬라이싱과 같은 다양한 함수를 사용하면 좀 더 쉽고 직관적이
리트코드인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.
스택: LIFO ( Last-In-First-Out, 후입선출 )마지막에 쌓은 접시가 맨 위에 놓일 것이라, 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 된다.큐: FIFO (First-In-First-Out, 선입선출)가장 먼저 줄을 선 사람이 가장 먼저 입장한다.파
리트코드중복된 문자를 제외하고 사전식 순서(Lexicographical Order)로 나열하라사전식 순서: 글자 그대로 사전에서 가장 먼저 찾을 수 있는 순서bcabc에서 중복 문자를 제외하면 사전에서 가장 먼저 찾을 수 있는 문자열은 abc가 될 것이다.만약, 앞에
리트코드매일의 화씨 온도(℉) 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라설명화씨 73도인 첫째 날에서 더 따뜻한 날을 위해서는 하루만 기다리면 된다. 바로 다음날인 둘째 날은 화씨 74도다.마찬가지로 더 따뜻한 날을 위해서
리트코드큐를 이용해 다음 연산을 지원하는 스택을 구현하라push(x): 요소 x를 스택에 삽입한다.pop(): 스택의 첫 번째 요소를 삭제한다.top(): 스택의 첫 번째 요소를 가져온다.empty(): 스택이 비어 있는지 여부를 리턴한다.스택이나 큐 ADT를 실제로
리트코드스택을 이용해다음 연산을 지원하는 큐를 구현하라push(x): 요소 x를 큐 마지막에 삽입한다.pop(): 큐 처음에 있는 요소를 제거한다.peek(): 큐 처음에 있는 요소를 조회한다.empty(): 큐가 비어 있는지 여부를 리턴한다.앞서와는 다른 중요한 차이
리트코드원형 큐를 디자인하라.원형큐를 구현하는 방법에는 여러가지가 있으나 여기서는 가장 일반적인 방법인 배열로 구현해본다.배열로 구현했을 때 공간을 재활용한다는 원형의 이점을 내세울 수 있기도 하다.먼저 초기화 시에는 큐의 크기 k를 입력값으로 받는다.k 값은 당연히
리트코드다음 연산을 제공하는 원형 데크를 디자인 하라MyCircularDeque(k): 데크 사이즈를 k로 지정하는 생성자다insertFront(): 데크 처음에 아이템을 추가하고, 성공할 경우 true를 리턴한다.insertLast(): 데크 마지막에 아이템을 추가하
리트코드k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.이 문제의 난이도는 '어려움'으로 표기되어 있지만 사실 이 문제는 우선순위 큐를 사용하면 매우 쉽게 풀이할 수 있다.대부분의 우선순위 큐 풀이에 거의 항상 heapq 모듈을 사용하므로 잘 파악해두자. lis
리트코드다음으 기능을 제공하는 해시맵을 디자인하라.put(key, value): 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다.get(key): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.remove(key): 키
리트코드J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까?대소문자는 구분한다.
리트코드중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 리턴하라.문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p",
리트코드k번 이상 등장하는 요소를 추출하라요소 값을 키로하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, 우선순위 큐(Priority Queue)를 이용해 k번 만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출할 수 있다.먼저 빈도수는 collections
리트코드1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.연결되어 있는 1의 덩어리 개수를 구하라이 문제는 반드시 그래프 모양이 아니더라도 그래프형으로 변환해서 풀이할 수 있음을 확인해보는 좋은 문제다.입력값이 정확히 그래프는 아니지
리트코드2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.이 문제는 전체를 탐색하여 풀 수 있다. 항상 전체를 탐색해야 하고 가지치기 등으로 최적화할 수 있는 문제가 아니기 때문에 어떻게 풀이하든 결과는 비슷하다.가능한 경우의 수를 모두
리트코드서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.순열의 수 추출(경우의 수) : nPr = n!/(n-r)!이 문제는 모든 결과를 생성해내야 하는데 생성하는 문제일 때, 경우의 수만 계산하는 것에 비해서는 다소 까다로운 편이다.순열이란 결국 모든 가능한
리트코드전체 수 n을 입력받아 k개의 조합(Combination)을 리턴하라.nCr = n! / r! (n-r)!이 문제의 경우 입력값이 너무 단순하므로 1을 더 늘려보자. 즉 n=5, k=3일 때, 5! / 3!(5-3)! = 10이다.10가지 경우를 모두 나열해보면
리트코드숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.합 tartget을 만들 수 있는 모든 번호 조합을 찾는 문제이다.입력값의 중복 조합 그래프를 풀이하는 문제로 도식화 할 수 있다.모든 중복 조
리트코드모든 부분 집합을 리턴하라.이 문제는 트리를 구성하고, 트리를 DFS하는 문제로 풀이할 수 있다.입력값이 1,2,3 일 때 다음과 같이 간단한 트리를 구성할 수 있다.이를 DFS하여 원하는 결과를 출력할 수 있다.DFS 코드를 구현해보자.경로 path를 만들어
리트코드from, to 로 구성된 항공원 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라.여러 일정이 있는 경우 사전 어휘 순(Lexical Order)으로 방문한다.
리트코드0을 완료하기 위해서는 1을 끝내야 한다는 것을 0,1 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.이 문제는 그래프가 순환(Cyclic) 구조인지를 판별하는 문제로 풀이할 수 있다. 순
리트코드K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다.입력값 (u, v, w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.이 문제에서는 다음과 같은 2가지 사항을 반별해야 한
리트코드시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다.가격을 시간이라고 가정한다면 최단 시간을 계산하는 경로는 앞서 다익스트라 알고리즘으로 동일하게 구현할 수 있다. 다만
리트코드이진 트리의 최대 깊이를 구하라.깊이를 측정하는 방법은 다양하지만 여기서는 BFS (너비 우선 탐색)으로 풀이한다.BFS는 재귀가 아닌 반복 구조로 풀이할 수 있다. 먼저 큐를 선언하고 풀이할 준비를 한다.파이썬에서 큐는 일반적인 리스트로도 모든 연산이 가능하다
리트코드이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라1\. 상태값 누적 트리 DFS
리트코드동일한 값을 가장 긴 경로를 찾아라.트리의 말단, 리프노드까지 DFS로 탐색해 내려간 다음, 값이 일치할 경우 다음과 같이 거리를 차곡차곡 쌓아 올려가며 백트래킹하는 형태로 풀이할 수 있다.<동일한 값의 이동거리 계산>예제의 첫 번째 입력값을 기준으로 트리
리트코드이 문제는 파이썬 다운 방식으로 정말 쉽게 풀 수 있다. 막상 설명은 쉽지 않다.<재귀를 이용한 이진 트리 반전>이 그림에서는 루트 노드인 4에서 시작하되, 지금까지와는 달리 여기서는 오른쪽부터 재귀 탐색을 진행한다. self.invertTree의 파라미터
리트코드두 이진 트리를 병합하라. 중복되는 노드는 값을 합산한다. 각각 이진트리의 루트부터 시작해 합쳐 나가면서 좌, 우 자식 노드 또한 병합될 수 있도록 각 트리 자식 노드를 재귀 호출한다.만약 어느 한쪽에 노드가 존재하지 않는다면 not (root1 and root
리트코드이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라. 즉 다음과 같은 트리는 1,2,3,null,null,4,5 형태로 직렬화할 수 있을 것이다.직렬화를 제대로 구현하기 위해서는 우선 이진 트리의 특징과 표현(Representation)에 대해
리트코드이진 트리가 높이 균형(Height-Balanced)인지 판단하라.높이 균형은 매우 중요한 개념이다. 균형이 맞아야 효율적으로 트리를 구성할 수 있으며, 탐색 또한 훨씬 더 효율적으로 처리할 수 있기 때문이다. 높이 균형을 매번 맞추는 AVL 트리는 대표적인 자
리트코드노드 개수와 무방향 그래프를 입력받아 트리가 최소 높이가 되는 루트의 목록을 리턴하라.
리트코드오름차순으로 정렬된 배열을 높이 균형(Height Balanced) 이진 탐색 트리로 변환하라.이 문제에서 높이 균형이란 모든 노드의 두 서브 트리 간 깊이 차이가 1 이하인 것을 말한다. 정렬된 배열 -10,-3,0,5,9이 주어졌을 때, 가능한 답변은 0
리트코드BST의 각 노드를 현재값보다 더 큰 값을 가진 모든 노드의 합으로 만들어라.
리트코드이진 탐색 트리(BST)가 주어졌을 때 L 이상 R 이하의 값을 지닌 노드의 합을 구하라.1\. 재귀 구조 DFS로 브루트 포스 탐색
리트코드두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라값의 차이가 가장 작은 노드를 찾으려면 어디와 어디 노드를 비교해야 하는지 생각해보자. BST의 왼쪽 자식은 항상 루트보다 작고, 오른쪽 자식은 항상 루트보다 크다.이 경우 루트 D와 가장 차이가 작
리트코드트리의 전위, 중위 순회 결과를 입력값으로 받아 이진 트리를 구축하라.순회에는 크게 전위, 중위, 후위 순회가 있으며 이 셋 중 2가지만 있어도 이진 트리를 복원할 수 있다. 이 문제는 여기서 2가지 결과인 전위와 중위 결과를 받아 이진 트리를 만들어보는 문제다
리트코드정렬되지 않은 배열에서 k번째 큰 요소를 추출하라31번 문제 '상위 K 빈도 요소'와 비슷한 문제다. 다른 점이라면 가장 큰 값이냐, 가장 빈번한 값이냐의 차이 정도라 하겠다. 여기서 함수명을 수정하고, Cunter()로 빈도 수를 계산해 삽입했던 예전 풀이 대
리트코드트라이의 insert, search, startsWith 메소드를 구현하라.트라이를 직접 구현해보는 문제다. 여기서는 딕셔너리를 이용해 가급적 간결한 형태로 풀이해본다. 먼저 트라이를 저장할 노드는 별도 클래스로 선언한다.메소드를 포함해 같은 클래스로 묶을 수도
리트코드단어 리스트에서 words\[i] + words\[j]가 팰린드롬이 되는 모든 인덱스 조합 (i, j)를 구하라.각각의 모든 조합을 구성해보고 이 구성이 팰린드롬인지 여부를 판별하면, O(n2) 시간 복잡도로 브루트 포스 풀이가 가능할 것 같다. '유효한 팰린드
리트코드연결 리스트를 O(nlogn)에 정렬하라이 문제는 연결 리스트를 입력값으로 주기 때문에 직접 정렬을 구현해야 하는 좋은 문제이다. 그러나, 시간 복잡도 O(nlogn)으로 풀어야 하는 제약사항이 있다. 연결 리스트 입력에 대해서는 파이썬에서 정렬할 수 있는 별도
리트코드겹치는 구간을 병합하라.이 문제를 풀기 위해서는 먼전 정렬을 수행한다.정렬 순서는 첫 번째 값을 기준으로 한다.람다를 이용하면 첫 번째 값을 키로 이용하라는 지시를 할 수 있다.두 번째 값을 사용할 경우에는 당연히 x\[1]로 지정하면 된다.그렇게 했을 때 현재
리트코드연결 리스트를 삽입 정렬로 정렬하라.
리트코드항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하라.각 요소 단위로 크기 순으로 정렬하면 된다. 단 여기서는 다소 특이한 정렬 기법을 적용해야 하는데 맨 앞에서부터 자릿수 단위로 비교해서 크기 순으로 정렬한다.9는 30보다 맨 앞자리수가 더 크므로 9가 더
리트코드t가 s의 애너그램인지 판별하라.애너그램 여부를 판별하려면 양쪽 문자열을 모두 정렬하고 그 상태가 일치하는지 확인하면 된다. 이 문제는 5번 '그룹 애너그램' 문제의 간략 버전으로 볼 수 있다. 굳이 어렵게 풀이할 필요는 없다.그때는 입력값을 그대로 정렬해 딕셔
리트코드빨간색을 0, 흰색을 1, 파란색을 2라 할 때 순서대로 인접하는 제자리(In-Place) 정렬을 수행하라.이 문제는 다익스트라가 1976년에 제안한 '네덜란드 국기 문제(Dutch National Flag Problem)' 문제와 동일한 문제로, 퀵 정렬의 개
리트코드평면상에 points 목록이 있을 때, 원점 (0, 0)에서 K번 가까운 점 목록을 순서대로 출력하라. 평면상 두 점의 거리는 유클리드 거리로 한다.유클리드 거리(Euclidean Distance)는 유클리드 공간에서 두 점 사이의 거리를 계산하는 가장 '일반적
리트코드정렬된 nums를 입력받아 이진 검색으로 target에 해당하는 인덱스를 찾아라.먼저 간단히 재귀로 이진 검색을 구현할 수 있다.절반씩 범위를 줄여나가며 맞출 때까지 계속 재귀 호출하면 된다.카드 마술 설명과 동일한 정석대로의 풀이다.대개는 재귀 풀이가 더 우아
리트코드특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값의 인덱스를 출력하라.설명: 정렬된 입력값은 0,1,2,4,5,6,7 이며 여기서 이진 검색을 통해 1의 위치를 찾은 다음(위치 1) 원래의 입력값에서 얼마만큼 돌아가 있는지를 확인하여(4칸), '위치
리트코드두 배열의 교집합을 구하라.먼저 가장 간단하고 직관적인 브루트 포스로 풀어본다. O(n2)으로 반복하면서 일치하는 경우 무조건 추가한다. 데이터 타입은 집합이기 때문에 속도는 느리긴해도 중복된 값은 알아서 잘 처리해줄 것이다.bisect_left에 대해서는 다음
리트코드정렬된 배열을 받아 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.주의: 이 문제에서 배열은 0(Zero-Based)이 아닌 1부터 시작하는 것으로 한다.7번 '두 수의 합' 문제는 투 포인터로 풀 수 없다고 했으나, 그 문제의 다른 버전 격인
리트코드m x n 행렬에서 값을 찾아내는 효율적인 알고리즘을 구현하라. 행렬은 왼쪽에서 오른쪽, 위에서 아래 오름차순으로 정렬되어 있다.이 문제는 행을 기준으로 이진 검색을 수행한 다음, 찾아낸 값을 기준으로 해당 위치의 각 열을 기준으로 다시 이진 검색을 수행하면 해
리트코드딱 하나를 제외하고 모든 엘리먼트는 2개씩 있다. 1개인 엘리먼트를 찾아라.단 1개의 엘리먼트를 찾는 데 적당한 연산자가 있다. 배타적(Exclusive) OR, XOR이다.XOR은 입력값이 서로 다르면 True, 서로 동일한 경우 False가 되는 논리 게이트
리트코드두 정수를 입력받아 몇 비트가 다른지 계산하라.➕ count 함수는 문자열에서 쓰이는 메서드 입니다.count 함수는 문자열 내부에서 특정 문자, 혹은 문자열이 포함 되어있는지 계산해서 반환해주는 함수 입니다..count(self, x, \_\_start, \_
리트코드두 정수 a와 b의 합을 구하라. \+또는 - 연산자는 사용할 수 없다.이번에는 좀 더 제대로 전가산기를 구현해본다. 물론 전가산기를 온전히 구현하는 데는 많은 노력이 필요하다.지나치게 어렵게 풀이하는 것 같지만, 여기서는 논리 회로에 대한 이해도 높일 겸 한
리트코드부호없는 정수형 (Unsigned Integer)을 입력받아 1비트의 개수를 출력하라.이 문제의 결과는 모두 0으로 구성된 비트들과의 해밍 거리(Hamming Distance)로 이를 해밍 가중치(Hamming weight)라고 부른다.참고로 해밍 거리는 두 정
리트코드배열 nums가 주어졌을 때 k 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하면서 최대 슬라이딩 윈도우를 구하라.제목부터 '슬라이딩 윈도우'라는 단어가 포함된 전형적인 슬라이딩 윈도우 문제로, 파이썬에서는 슬라이싱과 내장 함수를 사용해 매우 쉬운 방식으로 풀이할
리트코드문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.최소 윈도우라고 했으니 일단 T의 크기부터 시작해 점점 크기를 키워가며 모든 위도우 크기에 대해 다음고 같이 탐색을 시도해볼 수 있겠다.예제에서 T는 3개의 문자이므로 먼저
리트코드대문자로 구성된 문자열 s가 주어졌을 때 k번만큼의 변경으로 만들 수 있는, 연속으로 반복된 문자열의 가장 긴 길이를 출력하라.이 문제는 오른쪽 포인터가 계속 우측으로 이동한다는 점에서 슬라이딩 윈도우 문제이지만, 왼쪽 포인터를 계속 좁혀서 범위를 조절해 나간다
리트코드여러 번의 거래로 낼 수 있는 최대 이익을 산출하라.12번 '주식을 사고팔기 좋은 시점' 문제의 2탄 격인 문제로, 한 번이 아닌 여러 번의 거래를 할 수 있다는 차이가 있다.이 문제는 단 한 번의 거래였기 때문에 저점과 고점에만 체크했다.이제는 여러번 거래를
리트코드여러 명의 사람들이 줄을 서 있다. 각각의 사람은 (h,k)의 두 정수 쌍을 갖는데,h는 그 사람의 키, k는 앞에 줄 서 있는 사람들 중 자신의 키 이상인 사람들의 수를 뜻한다. 이 값이 올바르도록 줄을 재정렬하는 알고리즘을 작성하라.먼저, 이 문제의 입출력
리트코드A에서 Z로 표현된 태스크가 있다. 각 간격마다 CPU는 한 번의 태스크만 실행할 수 있고, n번의 간격 내에는 동일한 태스크를 실행할 수 없다.더 이상 실행할 수 없는 경우 아이들(idle) 상태가 된다.모든 태스크를 실행하기 위한 최소 간격을 출력하라.이 문
리트코드원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas\[i] 만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는데 cost\[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라.출발점이
리트코드아이들에게 1개씩 쿠키를 나눠줘야 한다. 각 아이 child_i마다 그리드 팩터(GreedFactor) gi를 갖고 있으며, 이는 아이가 만족하는 최소 쿠키의 크기를 말한다.각 쿠키 cookie_j는 크기 sj를 갖고 있으며, sj >= gi이어야 아이가 만족하
리트코드과반수를 차지하는(절반을 초과하는) 엘리먼트를 출력하라.앞에서부터 하나씩 과반수를 넘는지 일일이 체크하다가 과반수를 넘으면 바로 정답으로 처리한다.아쉽게도 타임아웃이 발생한다.브루트 포스를 다이나믹 프로그래밍으로 최적화해보자.nums.count()로 한 번 카운
리트코드숫자와 연산자를 입력받아 가능한 모든 조합의 결과를 출력하라괄호를 어디에 추가하느냐에 따라 다양한 조합이 가능하다. 모든 조합을 계산해야 하는데 이는 다음과 같이 분할 정복으로 가능하다.\*, -, + 연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 리
리트코드피보나치 수를 구하라.브루트 포스로는 안 풀릴 것 같지만 이렇게 기본적이 낭ㄹ고리즘으로도 풀리긴 한다.이제 다른 방식으로 최적화를 진행해보자.<피보나치 수 재귀 구현 계산 트리>다이나믹 프로그래밍의 하향식 풀이로 정리한 것이 바로 이 문제의 메모이제이션 풀
리트코드합이 최대가 되는 연속 서브 배열을 찾아 합을 리턴하라.언뜻 투 포인터 문제인가 하는 생각이 들 수 있다. 그런데, 왼쪽 포인터가 -2이고, 오른쪽 포인터가 4라고 했을 때, 그 사잇값이 최대가 되기 위해서는 음수를 지나치는 방식으로 알고리즘을 구현해야 하는데,
리트코드당신은 계단을 오르고 있다. 정상에 도달하기 위해 n계단을 올라야 한다.매번 각각 1계단 또는 2계단씩 오를 수 있다면 정상에 도달하기 위한 방법은 몇가지 경로가 되는지 계산하라.언뜻 생각해보면 풀이가 쉽지 않다. 모든 경우의 수를 다 찾아야 한다니 상당히 풀기
리트코드당신은 전문털이범이다. 어느집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고, 한 칸 이상 떨어진 집만 가능하다.각 집에는 훔칠 수 있는 돈의 액수가 입력값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라.이런 유형의 문제
백준
큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.입력값 2,4,5,4,6에서 M이 8이고,
숫자 카드 게임은 여러 개의 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
어떤 나라에는 1 ~ N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하라.출발 도시 X에서 출발 도시 X로
백준많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.명령 1. Go k: k는 1, 2 또는 3일 수
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.N에서 1을 뺀다.N에서 K로 나눈다.N이 17, K가 4라고 가정하자. 이 때 1번의 과정을 한 번 수행하
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.00시 00분 03초
행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 완실 정원의 특정한 한 칸에 나이트가 서 있다.나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이루어진 N X M 크기의 직사각형으로, 각각의 칸은 육지또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
백준수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이
N X M 크기의 얼음 틀이 있다.구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫혀 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생서오디는 총 아이스크림의
동빈이는 N X M 크기의 직사각형 형태의 미로에 같혀 있다. 미로에는 여러마리의 괴물이 있어 이를 피해 탈출해야 한다.동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴
하나의 수열에는 다양한 수가 존재한다 이러한 수는 크기에 상관없이 나열되어 있다.이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.입력조건첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 ≤ N ≤ 500)
N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.입력조건첫 번째 줄에 학생의 수 N이 입력된다. (1 ≤ N ≤ 100,000)
두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는
전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다.어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지
동빈이네 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어 가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.절단기에 높이( H )를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.높이
어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다.대표적으로 피보나치 수열을 예시로 들 수 있다.피보나치 수열은 이전 두 항의 합을 현재의
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.a. X가 5로 나누어 떨어지면, 5로 나눈다.b. X가 3으로 나누어 떨어지면, 3으로 나눈다.c. X가 2로 나누어 떨어지면, 2로 나눈다.d. X에서 1을 뺀다.정수 X가 주어졌으 ㄹ때
개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량 창고가 있는데 식량 창고는 일직선으로 이어져 있다. 각 식량 창고에는 정해진 수의 식량을 저장하고 잇으며 개미 전사는 식량 창고를 선택적으로 약탈하여
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 X 3
N가지 종류의 화폐가 있다.화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.예를 들어, 2원, 3원 단위의 화폐가 있을 때는
공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다.방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는
어떤 나라에는 N개의 도시가 있다. 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 없다면 Y는 X로 메
학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N + 1개의 팀이 존재한다. 이 때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.1) '팀 합치기' 연산은 두 팀을 합치는 연
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다.그리고 길마다 길을 유지하는데 드는 유지비가 있다. 마을 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분리
각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다.예를 들어 '알고리즘' 강의의 선수 강의로 '자료구조'와 '컴퓨터 기초'가 존재한다면, '자료구조'와 '컴퓨터 기초'를 모두 들은 이후에 '알
고스택
백준
백준
1. Python 2. Java
백준2\.
한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포드'를 측정공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.동빈이는 최대 몇개의 모험가 그룹을 만들 수 있는지 궁금합니다.
각 자리가 숫자 (0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+'연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.단, '+'보다 'x'를 먼저 계산
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다.뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것
동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.예를 들어 N = 5이고, 각 동전이 3, 2, 1, 1, 9원짜리 동전이라고 가정할 때, 만들 수 없는 양의 정수 금액 중 최
A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다.볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번 부터 순서대로 부여됩니다.같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니
프로그래머스평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.회전판에 먹어야 할 N 개의 음식이 있다.각
백준최댓값은 321이 될 것 같지만, 정답은 312이다. 즉, 최댓값을 K번 바꾼 후에 나온 연산들 중 찾는 것이다. (321은 3번째 연산이 아닌, 2번만 바꿨을 때 나오는 결과임) 우리는 여기서 하나를 더 알고 가보자. 정답인 312는, 사실 1번만 바꿨을 때도 나
백준
백준
백준참고스도쿠는 DFS(깊이 우선 탐색)과 백트래킹(브루트 포스, 전부 탐색)으로 풀 수 있다.다만 너무 많은 재귀, 검사를 할 것에 대비해 유망한 숫자 검사(is_promising)와 재귀를 최소화 해줄 수 있게(zeros 리스트) 만든다.1) 0인 부분만을 찾는다2
백준
백준
백준참고
백준
백준
알파벳 대문자와 숫자 (0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다.이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.입력조건첫째 줄에 하나의 문자열 S가 주어집니다. (1 ≤ S의 길이 ≤ 10,00
프로그래머스
프로그래머스\`
백준
백준
백준
백준
백준
백준
백준
백준참고1, 참고2
백준
백준
백준
백준
백준
프로그래머스빙하가 깨지면서 스노우타운에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램
프로그래머스
백준
백준
백준
백준
백준참고
백준
다음의 코드는 해당 수보다 작은 모든 수로 나누어 보아서 소수인지를 판단하는 방법으로, 소수의 정의에 충실한 방법이면서 무식하지만 가장 강력한 방법이다.한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다. 소수를 구
백준
백준
백준
백준
백준
백준
백준
참고
백준
백준
백준
C++
백준
참고참고
백준
백준
프로그래머스
백준!youtubeI5G2uU8GGZg예를 들어 n = 4라고 하면, 사칙 연산 중에서 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려해야 한다.
백준
백준
프로그래머스 ![](https://images.velog.io/images/c
백준
안테나
프로그래머스
백준최소가 되려면 매 상황에서 가장 작은 크기의 두 카드 묶음을 꺼내서 이를 합친 뒤에 다시 리스트에 삽입하는 것이 최선이다.매번 따로 비교를 하는 것보다 우선순위 큐를 사용하는 것이 훨씬 빠르다.
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.단, 이
백준
백준
백준
고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다.예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a\[2] = 2이므로, 고정점은 2가 됩니다.하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순
백준
프로그래머스
참고최소 비용 신장 트리주어진 그래프에서 만들 수 있는 신장 트리 중, 그 값이 가장 작은 신장 트리를 말한다. 최소 신장 트리는 통신망, 도로망같은 네트워크를 최소의 비용으로 구축하는 문제의 답을 말한다.프림 알고리즘시작 정점에서부터 출발해서, 신장 트리 집합을 단계
백준
백준
백준
백준
백준다익스트라 알고리즘을 사용하여 최단 경로의 값을 구한다.BFS 알고리즘을 사용하여 최단 경로의 경로를 구한다.BFS 알고리즘으로로 구한 경로를 삭제다시 한번 다익스트라 알고리즘을 사용해서 거의 최단 경로를 구한다.
백준
n × m 크기의 금광이 있다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다.채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.이후에 m번에 걸쳐서 매번 오른쪽
백준
백준
백준하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치이는 '가장 긴 감소하는 부분 수열'의 길이를 계산하는 문제로 간주할 수 있다.
백준
백준
JUNGLE못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다.1, 2, 3, 4, 5, 6, 8, 9, 10, 12...이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자
두 개의 문자열 A, B가 주어졌을 때, A를 편집하여 B로 만들려고 한다. 수행할 수 있는 연산은 다음 3가지다. 이때 최소 편집 횟수를 구하시오.삽입(Insert): 특정한 위치에 문자 하나를 삽입합니다.삭제(Remove): 특정한 위치에 문자 하나를 삭제합니다.교
백준
참고, 참고2러시아 과학자 블라디미르 리벤슈테인(Vladimir Levenshtein)가 고안한 알고리즘입니다. 편집 거리(Edit Distance) 라는 이름으로도 불립니다. Levenshtein Distance는 두 개의 문자열 A, B가 주어졌을 때 두 문자열이
백준
백준
백준
백준
백준위키피디아
선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생들의 성적을 빅한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하시오.입력조건첫째 줄에 학생들의 수 N (2≤N≤5
화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용이 존재합니다.가장 왼쪽 위 칸인 \[0]\[0] 위치에서가장 오른쪽
백준
1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며 술래는 항상 1번 헛간에서 출발합니다.전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 전체 맵은 항상 어떤 헛간에서 다른 헛간으로 도달이 가능한 형태로 주어집니다
백준참고dp\[i]\[j]는 i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 byte를 의미한다. 1) 행은 app 개수만큼, 열은 sum(cost)만큼 만들어준다. 2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다. 3-0) 현재 앱의 cost가 j보다 클
백준2\. C++
백준
한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다.이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는
공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gᵢ번째 (1 ≤ gᵢ ≤ G) 탑승구 중 하나에 영구적으로 도킹해야 합니다.이때 다른 비행기가 도킹하
마을은 N개의 집과 M개의 도로로 구성되며, 각 집은 0번부터 N - 1번까지의 번호로 구분된다.도로에 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다. 일부 가로등을 비활서와하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈
백준
백준
일단은 오늘부터 DFS, BFS를 일주일 정도 완전히 적응해야겠다는 생각이 들어서 오늘부터 1 ~ 2문제씩 풀이를 최대한 보지 않고 풀어나가보려고 한다. 이제까지의 공부는 해결되지 않으면 빠르게 해답을 보는 습관이 있는 듯하여 이를 없애야 한다..!
백준
유효성 검사입력 글자 전체를 가지고 입력여부를 판단500 이상의 자료만 입력 받아라입력 마스크입력할 글자 하나하나를 제어00LL: 숫자 2개, 문자 2개입력 자료의 형식이나 범위를 지정한글 몇글자, 숫자 몇글자, 대소문자 여부 입력형식; 문자 저장 여부; 기본값형식입력
백준
백준
백준
백준bfs 처음에 graph\[x]\[y] = '0'을 빼먹었었다..!!!
백준
백준참고로 이 문제는 무방향 그래프로 조건이 주어졌기 때문에 양쪽으로 연결시켜주지 않으면 틀렸다고 나온다.
백준참고
백준
백준
백준
백준
백준
백준
백준
백준
백준
백준
백준
백준1부터 n - 2 까지의 index를 기준으로 다음 숫자를 더하거나 뺐을 경우 0이상 20이하 일 경우에만 이전 경우의 수(dpi - 1)를 더해준다.j + array\[i] 가 20 이하일 때dp\[i]\[j + arr\[i]] += dp\[i - 1]\[j]j
Box stacking ProblemConsider, we have been given 3-Dimensional boxes. Each box has width, depth and height (wi, di, hi). Box stacking problem is to st
백준
서버와 산하의 컴퓨터 사이에서는 서로 IP 주소로 호출합니다.IP 주소는 네트워크에서 통신 상대를 식별하기 위한 번호로, 0 - 255 사이의 숫자를 점으로 구분해 4개로 나누어 표시합니다. 네트워크별로 지정하므로 다른 네트워크에 가면 같은 번호의 기기가 존재할 수도
백준
백준
메일 서버 SMTP, POP3, IMAP인터넷 서버Web, FTP공통: DNS, Proxy, SSLSMTP (Simple Mail Transfer Protocol)메일을 보내는 서버SMTP 메일에 보내면 SMTP 서버는 @ 뒤에 적혀 있는 도메인명을 확인해서 DNS 서
백준
백준
백준
참고format(N, 'b') 는 N을 2진수로 변환합니다.1 사이에 있는 0의 개수를 구하는 거라 양쪽 끝에 있는 0을 버립니다.'1'로 split 하면 연속된 '0'으로 이루어진 문자열로 구성된 배열이 리턴됩니다.\[len(x) for x in arr]로 문자열들의
1. Python
백준
1. JavaScript 시간 복잡도 :(
1. JavaScript 2. Python
자바스크립트로는 한 번도 알고리즘을 풀어본 적이 없어서 어느 타이밍에 어느 메소드를 써야하는지가 아직은 감이 안 잡히고, 계속 파이썬 문법을 무의식적으로 써버린다 :(오늘은 계속 자바스크립트로 문제를 풀어봐야겠다.Array length가 1 이상인 경우에는 range(
1. JavaScript 간단한 풀이 2. Python
0번 인덱스 부터 출발해서 거기 적힌 값이 거리 값으로 이해하였다. 하지만 그것이 아니라 개구리가 강 건너편을 건너야 하는데 건너기 위해선 강에 잎이 모두 떨어져 있어야 건널수 있다. 강에 모든 곳에 잎이 떨어져 있는 시간을 구하는게 문제이다
1. JavaScript 2. Python
1. JavaScript 정해 33% 2. Python
1. JavaScript 정해 (예외처리) 50%
어떤 구간을 K마다 자르면 완전한 subarray에는 반드시 1개의 K의 배수가 존재한다는 특성을 이용한다.즉 주어진 구간의 길이를 K로 나눠서 마지막에 남는 나머지가 있다면 그 나머지 안에 K의 배수가 있는지만 검사해서 리턴하면 되는 방식이다.우선은 A와 B 사이에
작은 값부터 있는지 확인
참고2가지 케이스만 고려하면 된다. slice가 2개 또는 3개인 경우 평균의 성질로 부분집합의 평균은 가장 작은 인자보다 항상 크다. 즉, (1, 2)의 평균은 1.5이므로 1보다 크다는 의미이다.평균들의 평균은 각 인자들의 평균과 같다. 즉, (1, 2, 3, 4)
0만 카운팅해주면 된다.0이 한 번 등장하면 다음 0이 등장할 때까지 1씩 더해주고, 0이 한번 더 등장하면 다음 0이 나올 때까지 2씩 더해주고...
1. JavaScript 정해 runtime error 2. Python
음수 \* 음수 고려해주기
참고
2개 원소의 합이 나머지 하나 보다 커야 되기 때문에 제일 작은 2개의 원소의 합만 고려
1. JavaScript 2. Python
1. JavaScript 2. Python
1. JavaScript 정해 87% 2. Python
참고, 참고2이전 블록의 높이가 현재 블록의 높이보다 높으면, 현재 블록은 이전 블록과 하나로 합쳐질 수 있으므로, 스택 lastH에서 pop을 시킨다.스택 lastH가 비어있거나, 이전 블록의 높이보다 현재 블록의 높이가 높으면 별도의 블록 조각이 필요하므로 스택 l
1. JavaScript 2. Python
1. JavaScript 2. Python
1. JavaScript 2. Python
1. JavaScript 2. Python
백준
참고문법 수준에서 모듈을 지원하기 시작한 것은 ES2015부터다. import/export 구문이 없었던 모듈 이전 상황을 살펴보는 것이 웹팩 등장 배경을 설명하는데 수월할 것 같다.아래 덧셈 함수를 보자.math.js:app.js:위 코드는 모두 하나의 HTML 파일
백준
백준
백준
백준
출처
백준
1. Python
백준
백준
백준
백준
1. Python 집합, combinations 사용
참고, 참고1
풀긴 풀었는데 아마 시간 복잡도에서 걸릴 것 같다.t가 10억이면 log의 속도가 아니면 t를 처리할 방도가 없다..
1. Python
백준
백준
백준
백준
백준슬라이딩 윈도우로 매번 배열을 점검하여 가장 긴 반복이 k - 1인 것을 찾아내려고 했는데 아마 AA의 경우 A 단독에서 4로 계산되어 제외되어 버리는 것 같다.그 이유는 ABA가 연속해서 3번 반복되기 때문이다.이 부분이 조금 헷갈린다.
참고,참고1(https://wikidocs.net/4308
1. Python
참고
![](https://ima
백준
백준
프로그래머스
백준연산자 우선순위도 고려해야한다
백준
백준
백준
백준
1. DFS
백준
백준
백준
백준
백준
백준
백준
백준
백준
백준
프로그래머스
프로그래머스
백준
프로그래머스
프로그래머스참고
프로그래머스출처
프로그래머스
백준
백준
1. C++
백준
백준
https://www.acmicpc.net/workbook/view/2954
프로그래머스
프로그래머스
프로그래머스 1. Python 2. C++ 3. Javascript
프로그래머스
1. Python 2. C++ 3. JavaScript
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
프로그래머스
백준참고
백준
연습문제배달음식 전문점 운영을 위해 다음과 같이 DeliveryStore 인터페이스와 PizzaStore, Food 클래스를 작성했습니다.업로드중..DeliveryStore :DeliveryStore는 배달 음식점의 인터페이스입니다.배달 음식점은 set_order_l
연습문제해밍 거리(Hamming distance)란 같은 길이를 가진 두 개의 문자열에서 같은 위치에 있지만 서로 다른 문자의 개수를 뜻합니다. 예를 들어 두 2진수 문자열이 "10010"과 "110"이라면, 먼저 두 문자열의 자릿수를 맞추기 위해 "110"의 앞에 0
연습문제문자열 형태의 식을 계산하려 합니다. 식은 2개의 자연수와 1개의 연산자('+', '-', '\*' 중 하나)로 이루어져 있습니다. 예를 들어 주어진 식이 "123+12"라면 이를 계산한 결과는 135입니다.문자열로 이루어진 식을 계산하기 위해 다음과 같이 간단
연습문제어느 누군가가 타임머신을 타고 과거로 가서 숫자 0이 없는 수 체계를 전파했습니다. 역사가 바뀌어 이제 사람들의 의식 속엔 0이란 숫자가 사라졌습니다. 따라서, 현재의 수 체계는 1, 2, 3, ..., 8, 9, 11, 12, ...와 같이 0이 없게 바뀌었습
연습문제다음과 같이 n x n 크기의 격자에 1부터 n x n까지의 수가 하나씩 있습니다.업로드중..이때 수가 다음과 같은 순서로 배치되어있다면 이것을 n-소용돌이 수라고 부릅니다.업로드중..소용돌이 수에서 1행 1열부터 n 행 n 열까지 대각선상에 존재하는 수들의 합
연습문제체스에서 나이트(knight)는 아래 그림과 같이 동그라미로 표시된 8개의 방향중 한 곳으로 한 번에 이동이 가능합니다.단, 나이트는 체스판 밖으로는 이동할 수 없습니다.체스판의 각 칸의 위치는 다음과 같이 표기합니다.예를 들어, A번줄과 1번줄이 겹치는 부분은
연습문제오름차순으로 정렬되어있는 두 배열 arrA, arrB를 하나의 배열로 합치려 합니다. 단, 합친 후의 배열도 오름차순으로 정렬되어 있어야 합니다.예를 들어 arrA = -2, 3, 5, 9, arrB = 0, 1, 5인 경우 두 배열을 오름차순으로 정렬된 하나의
연습문제□ 문제설명1번부터 N번까지 후보에 대해서 투표를 진행했습니다. 예를 들어 투표 결과가 1, 5, 4, 3, 2, 5, 2, 5, 5, 4라면 순서대로 1번, 5번, 4번, 3번, 2번, 5번, 2번, 5번, 5번, 4번 후보에 투표했음을 나타냅니다. 이때,
연습문제두 학생 A와 B는 계단 게임을 하였습니다.계단 게임의 규칙은 아래와 같습니다.계단 제일 아래에서 게임을 시작합니다. (0번째 칸)가위바위보를 합니다.이기면 계단 세 칸을 올라가고, 지면 한 칸을 내려가고, 비기면 제자리에 있습니다.계단 제일 아래에서 지면 제자
연습문제지난 연속된 n일 동안의 주식 가격이 순서대로 들어있는 배열이 있습니다. 이때, 다음 규칙에 따라 주식을 사고 팔았을 때의 최대 수익을 구하려 합니다.n일 동안 주식을 단 한 번 살 수 있습니다.n일 동안 주식을 단 한 번 팔 수 있습니다.주식을 산 날에 바로
연습문제도서 대여점의 만화책과 소설책의 대여 요금이 다음과 같습니다.구분 | 대여 요금 | 추가 요금만화책 | 첫 2일 500원 | 이후 1일당 200원씩 추가소설책 | 첫 3일 1000원 | 이후 1일당 300원씩 추가만화책과 소설책의 대여 요금을 계산하기 위해 아래
연습문제A 지하철역의 오늘 하루 지하철 도착 시각이 순서대로 들어있는 배열이 있습니다. 현재 시간이 주어졌을 때, 지하철을 타기위해서는 최소 몇 분을 기다려야 하는지 구하려 합니다. 이를 위해 다음과 같이 프로그램 구조를 작성했습니다.00:00을 기준으로 해서 현재 시
연습문제A 사이트에서 아래 조건에 맞는 게시글을 최초로 작성하는 이용자에게 경품을 제공하려 합니다.현재 작성되어있는 가장 마지막 게시글 이후에 작성된 게시글이어야 합니다.게시글 번호의 자릿수가 짝수여야 합니다.게시글 번호가 2n 자릿수 일때, 앞 n 자리의 각 자릿수의
연습문제자연수가 중복 없이 들어있는 배열이 있습니다. 이 배열에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법은 몇 가지인지 세려고 합니다.자연수가 들어있는 배열 arr와 arr의 길이 arr_len이 매개변수로 주어질 때, 이 배열에서 합이 K의 배수
연습문제자연수가 들어있는 배열이 있습니다. 이 배열에서, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 구하려 합니다. 단, 바로 전 숫자와 현재 숫자가 같은 경우는 증가한 것으로 보지 않습니다.예를 들어 배열에 순서대로 3, 1, 2, 4, 5, 1, 2, 2, 3
연습문제로봇이 아래 그림과 같이 2차원 평면의 원점 (0, 0)에 서있습니다.이 로봇은 x축 방향, 혹은 y축 방향으로만 움직일 수 있으며, 알파벳으로 명령을 내릴 수 있습니다. 명령을 내릴 때 사용하는 알파벳은 'L', 'R', 'U', 'D'의 4가지이며, 'L'은
연습문제한국에는 다음과 같이 8가지 종류의 화폐가 있습니다.동전 : 10원, 50원, 100원, 500원지폐 : 1,000원, 5,000원, 10,000원, 50,000원손님에게 거슬러줘야 하는 금액이 주어질 때, 거슬러주는 동전과 지폐 개수의 합이 최소가 되도록 하려
연습문제자연수가 들어있는 배열이 주어질 때, 다음 규칙에 따라 새로운 배열을 만들려고 합니다.주어진 배열의 첫 번째 원소를 새로운 배열의 첫 번째 원소에 넣습니다.주어진 배열의 마지막 원소를 새로운 배열의 두 번째 원소에 넣습니다.계속해서 주어진 배열의 남아있는 원소중
연습문제주어진 비밀번호가 안전한지 아닌지 판단하려합니다. 비밀번호의 안전 여부는 다음 규칙으로 판단합니다.연속된 3자리 이상의 알파벳 혹은 숫자를 사용할 수 없습니다. (abc, cba, 012, 987 등)비밀번호에 사용할 문자열 password가 매개변수로 주어질
연습문제0과 1로만 이루어진 문자열에서 연속해서 붙어있는 0들을 하나의 0으로 줄이려 합니다.예를 들어 "101100011100" 이란 문자열은 "101101110"으로 만들면 됩니다.0과 1로만 이루어진 문자열 s가 매개변수로 주어질 때, 연속해서 붙어있는 0들을 하
연습문제정수로 이루어진 두 배열 arrA와 arrB가 주어질 때, arrA를 회전해 arrB로 만들 수 있는지 알아보려 합니다. 배열의 회전이란 모든 원소를 오른쪽으로 한 칸씩 이동시키고, 마지막 원소는 배열의 맨 앞에 넣는 것을 말합니다.이를 위해 다음과 같이 프로그
연습문제앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들어, "aba"는 팰린드롬이며 "abccca"는 팰린드롬이 아닙니다.어떤 문자열의 부분 문자열 중 팰린드롬인 문자열이 여럿일 수 있습니다.이 중 k번째로 큰 팰린드롬을 알고 싶습
연습문제체스에서 비숍(Bishop)은 아래 그림과 같이 대각선 방향으로 몇 칸이든 한 번에 이동할 수 있습니다. 만약, 한 번에 이동 가능한 칸에 체스 말이 놓여있다면 그 체스 말을 잡을 수 있습니다.8 x 8 크기의 체스판 위에 여러 개의 비숍(Bishop)이 놓여있
연습문제두 문자열 s1과 s2를 붙여서 새 문자열을 만들려 합니다. 이때, 한 문자열의 끝과 다른 문자열의 시작이 겹친다면, 겹치는 부분은 한 번만 적습니다.예를 들어 s1 = "ababc", s2 = "abcdab"일 때, 아래와 같이 s1 뒤에 s2를 붙이면 새 문
연습문제핸드폰 화면에 문구를 출력해주는 전광판 어플이 있습니다. 문구는 "happy-birthday"로 설정하였습니다. 전광판 어플은 다음과 같은 규칙으로 화면에 문구를 출력해 줍니다.어플은 화면에 14자 문구를 출력합니다.문구는 1초에 왼쪽으로 한 칸씩 움직입니다.문
연습문제어떤 수를 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 구하려 합니다.예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.3+7+233+11+193+13+175+11+17자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는
연습문제카프리카 수는 다음을 만족하는 수를 뜻합니다.자신의 제곱수를 둘로 나누어 더한 값이 자기 자신과 같습니다.단, 둘로 나뉜 수는 모두 양수여야 합니다.예를 들어, 55^2 는 3,025입니다. 3,025는 3과 025, 30과 25, 302와 5로 나눌 수 있습니
연습문제교실에 선풍기가 4대 있습니다. 선풍기는 한 대당 학생 k명에게 바람을 보냅니다. 모든 학생에게 바람을 보내기 위해서 선풍기를 몇 대 더 구매해야 할지 구하려고 합니다.예를 들어, 선풍기 한 대당 학생 3명에게 바람을 보낼 수 있을 때, 한 교실당 학생 수가 1
연습문제모 매장에서는 팝업스토어를 열려고 합니다. 팝업스토어란 한정 기간 문을 여는 매장입니다. 팝업스토어는 k일 동안 연속해서 열 예정입니다. n일 동안의 추정 매출액이 주어질 때, 언제 팝업스토어를 열어야 가장 매출이 높을지 알아보려 합니다.n일 간의 추정 매출액이
연습문제미용실과 레스토랑이 예약을 받는 기준은 다음과 같습니다.미용실인원수가 1명인 경우에만 예약받습니다.다른 손님과 예약 시간이 겹칠 수 없습니다.레스토랑인원수가 2명 이상 8명 이하인 경우에만 예약받습니다.최대 두 팀까지 예약 시간이 겹칠 수 있습니다.두 가게에서
1\. 버텍스 (Vertex)버텍스란 하나의 점이다.정점이라하며 3D의 가장 기본단위다.2D의 포인트와 대응되는 개념이지만 정점은 위치, 색상, 법선 등 다양한 정보를 담고 있다.Vertex vs Polygon포인트는 x,y 좌표값만 가지고 있다.버텍스는 위치, 색상,
연습문제어떤 단어가 XX 사전의 몇 번째 단어인지 알고 싶습니다. XX 사전에는 대문자 알파벳 'A', 'E', 'I', 'O', 'U'를 사용해 만들 수 있는 길이가 5 이하인 모든 단어가 수록되어 있습니다.예를 들어, 사전의 첫 번째 단어는 "A"이고, 그다음은 "
연습문제알파벳 소문자와 대문자로 구성된 문자열을 압축하려 합니다. 압축이란 대표 문자와 대표 문자가 연속되는 개수를 함께 표현하는 것입니다. 이때, 대문자와 소문자는 구분하지 않으며, 대표 문자는 소문자로 표현합니다.예를 들어, 문자열 "YYYYYbbbBbbBBBMmm
연습문제정확히 n 일 연속으로 스키장 이용하는데 필요한 최소 비용을 계산하려 합니다. 다음은 스키장에서 판매하는 이용권입니다.이용권 종류 | 스키장을 사용할 수 있는 일수 | 가격one_day | 구매한 날 하루 동안 사용 가능 | one_day_pricemulti_d
연습문제마방진이란 가로, 세로, 대각선 방향의 수를 더한 값이 모두 같은 정사각형 행렬입니다. 마방진에는 1부터 정사각형 넓이까지, 수가 하나씩 배치되어야 합니다. 아래는 가로, 세로, 대각선 방향의 수를 더한 값이 모두 34인 4 x 4 마방진입니다.4 x 4 행렬의