알고리즘

이때까지의 dp는 최댓값, 최솟값만 구했다.이제부터는 실제 해를 경로로 찾아보자.기본적으로 dp를 푸는방법과 동일하며 path를 이용하여 재귀적으로 찾는다.문제1. 1로만들기 2주어진 수를 3가지 연산을 통해 1로 만드는 최소 횟수와 그 경로를 묻고있다. 그럼 최단거리

정수삼각형예시그림에서 최댓값은 7+3+8+7+5=30이다."아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다."이므로 다음과 같이 재귀관계를 작성할 수 있다.아래의 합은 원래수+max(대각선 왼쪽, 대각선

UCPC는 무엇의 약자일까?처음에 공백기준으로 문제를 잘못 이해해서 틀린 문제다.문제와 질의응답을 보고나서야 간단한 문제라는것을 알았다.아무튼 U...C....P...C...가 존재하는 문자열이 정답이다.문자열문제는 파이썬이 강력하다.U, C, P, C가 들어올때마다

분산처리예시 설명을 보면 a = 10일때, 10개의 컴퓨터는 1번, 2번, ..., 10번, 1번, 2번, ... 이렇게 순서가 매겨진다. b = 5면 5번 컴퓨터가, b = 10이면 10번 컴퓨터가, b = 11이면 1번 컴퓨터가 마지막으로 작업한다.a^b % 10과

BOJ4097 수익 구간합의 최대값을 찾는 문제로 Dynamic Programming의 예제격인 문제이다. 효율이 나쁘면 O(n^3), 분할정복(divide-and-conquer)를 이용하면 O(nlogn), 그리고 DP를 이용하면 O(n)으로 해결할 수 있다. Ka

최단거리를 찾는 문제는 BFS로 해결할 수 있다.2차원에서 BFS를 하는 방법은 다음과 같다.Queue에서 현재 좌표를 얻는다.1.1. 현재좌표와 목표(좌표, 상태 등)가 같다면 종료한다.다음 좌표를 계산한다.2.1 방문한 적이 없다면 Queue에 삽입한다.2.2 이미

컴퓨터로 방정식의 해는 어떻게 구하는지 알아보자.

파이썬은 str 객체를 통해 문자열을 지원한다.알고리즘문제에서 문자열 관련 문제들은 어렵지 않은데, C스타일로 짜다보면 머리가 어질어질해진다. 왜 코드가 심각하게 길어지는것같지? 하면 90%정도 이미 함수, 메소드가 있다고 생각하면 된다.\[BOJ 11656] 접미사

트리의 지름예제의 트리를 그리면 다음과 같다.트리의 지름의 정의는 두 정점 사이의 거리 중 가장 긴 것이므로 1-3-4-5를 잇는 거리가 11로 가장 길다. 1에서 DFS/BFS를 하면 가장 큰 거리를 구할 수 있다.그런데 어느 정점에서 탐색을 해야 최대 거리가 될 것

자연수 배열 중 원소의 합이 S인 경우를 찾을 때, $O(n)$으로 해결한다.투포인터, 두 포인터, caterpillar method(??) 으로 불리는 알고리즘이다. \[BOJ 2003] 수 들의 합2기본적으로 완전탐색을 통해 $O(n^2)$으로 해결할 수 있다. 하

모든 경우의 수를 탐색해서(보통 재귀함수, 또는 DFS로 구현) 답인지 확인하는 방법을 브루트포스라고 한다. 그러나 입력 크기가 커지면 브루트포스의 성능은 매우 안좋다.따라서 모든 탐색을 하는중, 이미 정답과 모순이 되는 경우일 때 더이상 탐색하지 않고 가지치기(pr

괄호변환, 2020 카카오 블라인드 채용균형잡힌 괄호 문자열 : (과 )의 개수가 같은 문자열올바른 괄호 문자열 : '균형잡힌 괄호 문자열'이면서 (과 )의 짝이 맞는 문자열문제에서 제시된 '올바른 괄호 문자열'만들기 알고리즘은 다음과 같다.입력이 빈 문자열인 경우,

알고리즘이라기 보다는 일종의 테크닉이다. 기본적으로 컴퓨터는 데이터를 이진수로 저장하므로 비트단위로 데이터를 보겠다는 것이다. 그렇다면 비트연산을 쓰는 이유는 무엇일까? 장점을 적어보면 다음과 같다.삽입, 삭제, 검색 기능이 간결해진다.빠른 연산 속도, 적은 메모리로

어떤 T(Target)가 배열 A에 존재하는 위치를 빠르게 찾을 때 선형탐색으로 찾을 수 있다.def binary_search(A, T): start, end = 0, len(A) - 1start, end = 0, len(A) while start &lt

프로그래머스 - 순위검색

스택

문자열을 소문자로 바꾼다두글자씩 끊긴 문자열의 개수를 계산한다. 이때 알파벳만 인정자카드 유사도 구하기3.1 교집합 원소 개수 구하기3.2 합집합 원소 개수 구하기3.3 유사도 반환

DFS/BFS

파이썬은 여러 모듈들이 굉장히 편리하게 사용이 가능하다.자료구조를 제외하고 가급적 사용하지 않으려고 한다.이번에는 정규표현식과 permutation을 사용하지 않고 구현한다.expression을 숫자와 연산자를 분리한다.가능한 연산자의 순열을 만든다.순열의 우선순위대로

누적합과 그 응용문제이다배열 A의 원소 a\[0], a\[1], ..., a\[n-1]에 대하여, a\[i]...a\[j]의 원소의 합을 여러번 구해야 하는 경우가 있다. A가 변하지 않는다면 쿼리가 들어올 때마다 배열의 합을 구하는 것은 비효율적이다. ${\\rm S

데이터베이스 수업 처음에 배우는 후보키에 대한 설명이 주어지고, 2차원 문자열 배열에서 가능한 후보키의 개수를 찾는 문제이다.컬럼의 개수가 최대 8개, 로우의 개수가 최대 20개이므로 Brute-Force로 해결할 수 있을 것으로 보고 효율성을 최소한으로 고려하여 문제

운영체제의 메모리 단원에서 배우는 LRU기법을 이용하여 캐시 히트/미스 여부에 따라 전체 실행시간을 계산하는 문제다.LRU 알고리즘은 가장 안쓴 메모리를 캐시에서 삭제하는 간단한 방법이다.캐시사이즈가 최대 30이므로 queue를 이용하지 않고 단순 리스트로 구현하였다.

브루트포스, 조합어피치 점수를 A, 라이언 점수를 B라 하자모든 경우의 수에 대해 A와 B를 구한 후B-A가 최대인 경우를 업데이트한다

카카오 코딩테스트는 그림이 항상 친절하게 주어진다. 그림도 하나의 힌트다.그림을 보니 (심지어 문제 설명에도) 이진트리로 데이터가 주어져있다. 이진트리? 트리? 트리순회? 힙? 그래프? DFS/BFS?그리고 입력이 info와 edges인 것을 보아 그래프 관련문제임을

2차원 누적합, dp본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면

$N$이하의 수 중에서 약수가 $i$인 개수: $floor(N/i)$이므로 답 = $\sum$

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? (1 $\\leq$ S $\\leq$ 4,294,967,295)$\\sum\_{i=1}^n i=\\frac{n(n+1)}{2}$이므로 $\\sqrt{S}$를 고려하면 $O(S)

각 문자별로 계수를 구한 후, 계수가 큰 숫자부터 9, 8, 7, ...을 할당해준다.문제의 예시를 예로 들면2GCFACDEBA = 10,000B = 1C = 1,010D = 100E = 10F = 1G = 100이고 숫자가 큰 문자부터 9, 8, 7, ... 을 할당

방향그래프에서 사이클에 속하는 정점이 몇개인지 알아야 하는 문제단순히 사이클이 존재하는지 확인하는 것이라면 union-find를 하겠지만 정확히 누가 사이클의 원소인지 파악해야한다.문제 예시1번이라면1에서 dfs 시작trace가 1, 3에서 3을 재방문하므로 사이클인

dp\[x]\[y]: x에서 y로 가는 $K$의 최솟값solve(x, y): dp\[x]\[y]를 구하는 함수. 재귀로 구현0->4만 구하면 되는데 모든 경우를 구하다 보니 재귀가 지나치게 많아져서 시간초과인 것으로 생각된다.dp\[x]: x에서 N-1까지 가는 $K$

BOJ 16926 배열 돌리기 1에서 회전수 R이 최대 $10^9$로 커진 버전이다.가장 바깥 껍데기를 원형큐로 만든다. 이때의 큐의 크기를 Q라 하자.회전수는 R이 아니라 $Q \\mod R$이므로 효율적으로 돌린다.다시 큐의 앞부분부터 껍데기를 채운다.안쪽 껍데기가

대략적인 알고리즘은 1\. 보석과 가방을 무게 기준으로 정렬2\. 각 가방에 넣을 수 있는 보석 중에서, 가격이 가장 비싼 보석 선택이다.N, K <= 300,000이라 $O(NK)$이어서 시간을 줄이는 방법을 고민중이었다.2단계에서 생각을 해보면 전 가방에 들어

dp인 걸 눈치챘으나, 처음에 점화식을 못썼다dp\[x]\[y]: land\[x]\[y]를 선택할 때, 누적합의 최댓값land\[x]\[y]를 선택하면, 그 전 row에서 dp\[x-1]\[y]를 제외한dp\[x-1]\[j]중에서 최댓값을 고르면 된다.정답은 마지막 r

회문을 확인하는 방법은 word의 양끝에서부터 문자를 확인하면 된다.만약 일치하지 않는다면word\[s+1:e+1] 또는 word\[s:e]이 회문이라면 유사회문이고, 여기서도 회문이 아니라면 회문도, 유사회문도 아니다.word\[a:b]이면 word\[b]는 포함되지

선수들의 적합한 포지현 수는 최대 5이므로 브루트포스 완전탐색을 하면 시간복잡도가 $O(T5^{11})=O(T 48,828,125)$이다전형적인 백트래킹 문제였는데 처음에 내가 짠 함수의 인덱스가 헷갈려서 꼬였다dfs(table, picked, stats, player

링크드리스트 + 스택링크드리스트를 직접 구현할 것인가?단순 삽입 삭제라면 딕셔너리로 해결할 수 있다data\[i] = \[i - 1, i + 1]: i번째 row의 prev, next를 원소가 2개인 리스트(튜플)로 표현할 수 있다.

투포인터 복습겸 다시 풀어보았다defaultdict의 len()은 key의 value가 0이어도 살아있다. 따라서 원치않는 길이가 나올 수 있으므로 삭제한다

BFS + DP추가 TC가 생겨서 과거 블로그의 코드가 정답이 아닌 경우가 있어 고생했다.특히 TC25번....

학생 마다 매번 징검다리를 시뮬레이션하면 끝이 없다.stones의 최댓값이 200,000,000 이고 배열의 길이가 200,000 이므로 시간초과난다. 바로 여기서 이분탐색 아이디어를 떠올릴 수 있다

연결리스트 구현 연습으로 풀었다입출력이 많을 때는 Pypy3보다 python3이 조금 더 빠르다고한다혹시 50~52%에서 틀린다면 이부분을 고려해보길...

시뮬레이션 구현 능력을 묻는 문제같아서 구현능력에 초점을 맞췄다. 블록의 크기가 최대 30x30밖에 안되어서 시간복잡도 신경쓰지 않았다. >1. 4x4 블록에 모두 같은 프렌즈가 있으면 플래그 처리하기. >2. 각 컬럼마다 플래그가 있는 프렌즈는 빼고 내리기 >2.1

머리로는 알겠는데 코드로 옮기기가 귀찮은 문제 음수, 0, 1, 양수 따로 저장하고 > 1. 데이터 저장 음수, 0, 1, 양수 따로 저장 정렬 음수는 오름차순으로 (절댓값이 내림차순) 양수는 내림차순으로 수 묶기 음수리스트, 양수리스트에서 2개씩 묶어 곱하고 더하기

던전의 길이가 최대 8이므로 모든 경우의 수는 8!이다. 8!은 1초안에 계산이 가능한 계산량이다

BOJ 2812 크게만들기와 동일한 문제다k: 남은 제외할 숫자의 횟수스택에 숫자를 집어넣으면서 top보다 현재 숫자가 크면 top 이하의 수나 될때까지 pop을 한 후에 현재 숫자를 push한다. pop의 횟수는 숫자를 제외하는 횟수이므로 k를 줄여준다이 문제에 함정

멀티탭에 빈 구멍이 있다면, 해당 구멍에 전기용품을 꽂는다이미 사용중인 전기용품이 있다면 다음 전기용품으로 넘어간다꽂을 구멍이 없다면, 꽂혀있는 전기용품 중에서 가장 나중에 사용되는 전기용품을 뽑고 그 구멍에 새로운 전기용품을 꽂는다처음 배열을 순회하면서 각 전기용품마

쌀때 사서 최댓값에 판다최댓값 $M_1$을 찾고, 구간 ...$M_1$에서 수익을 계산한다. 그리고 다시 남은 구간에서 이 작업을 반복한다. 이러면 $O(N^2)$이라 시간초과가 발생한다.각 구간의 최댓값을 $M1, M_2, ...M_n$이라 하면....$M_1$, .

해시테이블 연습 겸 C로 구현해보았다.원래 해시테이블에는 init, insert, search, remove, show가 있어야 하지만 이 문제에서는 remove와 show는 하지 않았다.

해시테이블은 (key, value)를 저장하는 자료구조로, 빠른 탐색을 원할때 쓰는 자료구조다. 주로 문자열을 탐색할때 사용된다.(정수 기반 탐색은 인덱싱이 가능한 배열/리스트를 이용하면 된다)아래 이미지는 사람 이름을 검색하면 전화번호부를 찾는 해시테이블이다. (이미