알고리즘 문제를 풀다보면 변수를 수정할 때 다른 변수가 원치 않게 변경되는 경우가 있다. 그래서 헷갈리지 않게 할당과 복사에 대한 내용을 정리해보겠다. 📍할당과 복사 할당과 복사는 비슷해보이지만 차이가 있다. 비교를 위해 먼저 리스트를 다른 변수에 할당해보자! 리스트 a를 b에 할당 리스트를 다른 변수에 할당하였으므로 리스트가 두개가 될 것 같지만 확인해보면 다음과 같이 리스트는 하나이다. 두 리스트를 연산자로 확인해보면 True가 나온다. 이름은 다르지만 사실은 같은 리스트인 것이다. 따라서 b의 요소를 변경하면 a도 변경이 된다. b의 1번 인덱스를 5로 변경해보자. 이해하기 쉽게 그림으로 확인해보면 다음과 같다. 다음은 복사를 해보자! 이번에도 똑같은 리스트를 할당이 아닌 복사를 해보면 다음과 같다. a를 b로 복사 앞에서 나온 할당 그림과 비교했을 때 리스트가 각각 생긴 걸 확인할 수 있다. a와 b를 연산자로 비교해보자. a

백준 16928번 - 뱀과 사다리 게임 이 문제는 최소 주사위 횟수를 구해야 하는 bfs 문제이다. 전에는 너비우선탐색을 하며 전의 값 + 1만 해주면 되었다면, 이 문제는 이 값이 뱀이나 사다리가 있는지에 따라 경우가 추가되는 문제다. 그래서 visited 정보를 따로 저장해주었고, board에는 0으로 초기화한 후, 뱀과 사다리 위치에는 연결되는 ㄱ값을 넣어주었다. 하나씩 방문해가면서 0이 아닌 경우는 뱀과 사다리로 처리하고, 0인 경우는 일반적인 너비우선탐색으로 처리했다. solution

구간 합 구하기 연속적으로 나열된 n개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제이다. M개의 쿼리, N 크기의 구간이 주어질 때, 매번 구간 합을 계산한다면 해당 알고리즘은 O(NM)의 시간 복잡도를 가진다. 이러한 경우에는 M과 N의 범위가 커지면 시간 초과가 발생하여 문제를 해결하기 어려워진다. 접두사 합(Prefix Sum) 그렇다면 여러 번 사용될 만한 정보는 미리 구해 저장해두는건 어떤가? 확인해보면 쿼리는 M개지만 N개의 수는 한 번 주어지고 변경되지 않는다. 그러므로 접두사 합을 사용한다. N개의 수의 위치 각각에 대하여 접두사 합을 미리 구해두면 된다. 해당 알고리즘은 다음과 같다. N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다. 이때, index를 헷갈리게 하지 않기 위해 새로운 배열에 0을 추가해둔다. 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R] -

9251번 문제 - LCS(Longest Common Subsequence) 이 문제는 풀이법이 잘 떠오르지 않았다. 문자열 a,b를 가지고 점화식을 그려보자면, a[i] == b[j] 일 때, LCS(a[i], b[j]) = LCS(a[i-1], b[j-1]) + 1 a[i] != b[j] 일 때, LCS(a[i], b[j]) = LCS(a[i-1], b[j]), LCS(a[i], y[i-1]) !! 위의 코드는 자꾸 틀렸다.. 입력값의 길이 조건이 없는 게 찝찝했는데 다른 사람 풀이를 보고 나니 앞에 패딩을 넣고 인덱스를 +1 로 처리해줘야한다는 걸 알았다. 내가 완전히 이해한 건지는 모르겠지만 다음에 내 힘으로 다시 풀어보자. 12865번 문제 - 평범한 배낭 ![

수열 문제, DP로 풀어보자! 11053번 - 가장 긴 증가하는 부분 수열 문제 설명 이 문제는 생각보다 문제를 이해하는 데에 시간 소모가 컸다. 역시 문제를 처음 접했을 때, 문제와 입력 조건, 출력을 잘 읽어보는 것이 중요하다는 걸 또 한번 느낄 수 있었다. 수열이 주어졌을 때, 증가하는 숫자의 수열 (연속 조건 x) 길이 중 가장 긴 길이를 구하는 것이다. 테스트 케이스가 간단한 입력만 나와있어서 그거만 보고 풀었다가는 산으로 갈 수 있다. , 와 같은 케이스를 고려해야 하기 때문이다! 처음 드는 DP의 사고방식은 각 인덱스마다 그 값으로 끝나는 증가하는 수열의 길이를 저장하는 것이었다. 그렇다면

동적 프로그래밍(dynamic programing) 지난 계단 오르기 문제(참고)를 풀어보며 동적 프로그래밍은 각 단계의 최적값을 메모리에 기록하여 중복 연산을 줄이는 기법이라고 이해했다. 그 이해를 바탕으로 오늘은 1912번 연속합 문제를 풀어보았다. 문제 1 - 연속합 배열이 주어졌을 때, 가장 큰 부분합을

동적 프로그래밍(다이나믹 프로그래밍)의 목적은? 메모리를 사용해서 중복 연산을 줄이고, 수행 속도를 개선하는 것 여기서 메모리를 사용한다는 것은! 배열 혹은 자료구조를 만든다는 것이다. 이를 통해 중복 연산을 줄인다는 것은 연산한 결과를 배열에 담는다는 것이다. 자꾸 다이나믹 프로그래밍이라는 이름이 와닿지 않아서 모호해지고, 응용이 어려워지는 것 같다. 한 교수님은 이것을 기억하기 알고리즘이라고 말했는데 그렇게 생각하고 풀어보자. 동적 프로그래밍 알고리즘 문제를 알아보고 구분하는 방법 이 풀이법은 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화할 때 고려될 수 있는 알고리즘이다. 그렇다면 코딩테스트 문제를 보고 dp로 풀어야겠다고 어떻게 알아볼까? dfs/bfs 로 풀 수는 있지만 경우의 수가 너무 많은 문제 경우의 수들에 중복 연산이 많은 경우 위에 해당한다고 했을 때, 각 위치까지 올 수 있는 최적의 값을 기록해가며 활용해보는 것이다. 그렇게

시간 복잡도 (Time complexity) 입력 값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비례하여 시간이 얼마나 걸리는가? 즉 입력 값이 커짐에 따라 증가하는 시간의 비율을 말한다. 시간 복잡도 표기 Big-O(빅-오) Big-Ω(빅-오메가) Bid-θ(빅-세타) 세가지 표기법은 최악, 최선, 중간(평균)의 경우를 나타내는 방법이다. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 고려할 수 있다. ** O(1) - constant complexity 입력값이 증가하더라도 시간이 늘어나지 않는다. 상수의 시간 복잡도이기 때문에, 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다. 예) 배

bfs와 dfs는 그래프 탐색 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다. > 그래프란? 여러 개체들이 연결되어 있는 자료구조 > 탐색이란? 특정 개체를 찾는 것 대표적인 문제 유형 경로 탐색 유형 (최단거리, 시간) 네트워크 유형 (연결, 그룹 개수) 조합 유형 (모든 조합 구하기) DFS 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법 스택보다는 재귀함수를 통해 구현하는 것이 일반적이고, 재귀를 타고 타고 가서 탈출 조건에 먼저 도달하도록 한다. 모든 경로를 방문해야 할 경우 사용에 적합 시간 복잡도 인접 행렬 : O(V^2) 인접 리스트 : O(V+E) V는 접점, E는 간선을 뜻한다 BFS 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 일반적으로 큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문) 가장 먼저 넣었던 것을 꺼내서 거기에

개념 참고 - https://velog.io/@lhj99apr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95 백준 9461 - 파도반 수열 문제 - [https://www.acmicpc.net/problem/9461] 수열의 패턴을 잘 살펴보고, 패턴을 코드로 구현하면 된다. 백준 1149번 - RGB거리 문제 링크 - https://www.acmicpc.net/problem/1149 이 문제는 dp로 푼다는 생각을 못했던 문제다. 여기서 다시 동적프로그래밍으로 풀 수 있는 문제의 조건을 살펴보면, 작은 해가 큰 해에 영향을 끼치는 것, 그 값을 구하기 위해 이전의 값이 반복적으로 사용된다는 점을 확인할 수 있고 DP로 구현할 수 있다. 백준 1932번 - 정수 삼각형 문제 링크 - https://www.acmic

1. 깊이 우선 탐색 그래프 탐색은 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것이다. 깊이 우선 탐색(Depth-First Search)이란 그래프 탐색법의 일종으로, 한 정점에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 전부 탐색하는 방법이다. 주로 모든 노드를 방문해야 할 때 이 방법을 선택하며, 너비 우선 탐색(BFS)보다 간단하나 검색 속도는 느릴 수 있다. 불필요한 경우를 차단하는 등의 처리가 없기 때문에 경우의 수가 줄어들 수는 없다. 때문에 N!의 경우의 수를 가지는 문제는 DFS로 풀 수 없다. 또한 최단 경로를 구하는 문제의 경우 그 해는 최단 경로가 되지 않을 수 있다. 해에 도착하면 탐색을 끝내버리기 때문이다. 트리를 기준으로 보았을 때는 자식 노드의 자식 노드 끝까지 따라가 잎(leaf)를 만날 때까지 깊게 탐색하는 꼴이며, 미로 탐색의 예에서는 한 길로 쭉 가다가 더이상 진행할 수 없을 때 직전의 갈림길로 돌아가 다른

이분 탐색 = 이진탐색 (binary search) 탐색 범위를 두 부분으로 분할하면서 찾는 방식으로 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지닌다. 시간복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN) 진행 순서 비교할 리스트를 정렬한다. left와 right로 중간 값인 mid를 설정한다. mid에 위치한 값과 내가 구하고자 하는 값을 비교한다. 구할 값이 mid보다 높으면 : left = mid+1, 구할 값이 mid보다 낮으면 : right = mid - 1 left > right가 될 때까지 계속 반복한다. 숫자 카드 - 백준 10815 solution 첫번째 솔루션은 간단하게 두 배열을 생성한 후, 있는지 없

2차원 배열 - 세로 읽기 (백준 10798번) 위와 같은 입력이 주어지고, 세로로 읽은 텍스트를 공백 없이 출력하라는 문제다. solution 먼저 각 줄의 입력을 이차원 배열 형식으로 저장하고, 이중 for문으로 읽으려고 한다. 여기서 for문에 주어지는 조건문과 없을 경우 예외 처리만 잘 해주면 되지 않을까? 입력을 받을 때 max_count 변수를 저장해주었다. solved! 2차원 배열 - 색종이 (백준 2563번) solution 처음 문제를 봤을 때는, 겹치는 부분을 구해야겠다고

HackerRank Preparation Kit Trees Tree: Height of a Binary Tree 위와 같은 트리 구조의 자료가 있다. 트리의 노드 개수 n이 주어졌을 때,

📒 1강 왜 자료구조를 알아야 하는가? 파이썬의 기본적인 데이터 타입 만으로는 해결하기 어려운 문제가 있고, 문제들을 조금 더 효과적으로 해결하기 위한 여러가지 자료구조들이 있다. 왜 알고리즘을 알아야 하는가? 문제마다 최적의 해법은 서로 다르다. 주어진 문제의 효율적인 해결을 위해 적절한 자료 구조와 연산 방법들을 선택해야한다. 📒 2강 - 선형 배열 (Arrays) 배열이란? 👉 원소들을 순서대로 늘어놓은 것 👉 파이썬에서는 list 자료형이 있고, 원소의 순서대로 0부터 매겨진 index가 존재한다. 연산 시간 소요가 길이와 무관한 연산: 맨 끝에 덧붙이거나 제외하는 append(), pop() 연산 --> 상수 시간 O(1) 리스트가 크면 클수록 오래 걸리는 연산 : 앞이나 중간 원소 삭제 혹은 삽입하는 insert(index, value), del(index) 연산 --> 선형 시간 O(n) 탐색

문제 해결 이 문제는 bfs로 풀면 간단한 문제다. 먼저 선입선출로 가장 빠른 길을 찾는 문제기 때문에 deque를 사용하여 구현한다. 그리고 한글자 차이인 단어를 찾아 차례대로 deque 에 넣고 바꾸고를 반복하며 원하는 단어가 나오는 가장 빠른 길을 찾는다.

프로그래머스 문제 이 문제는 미로 통과하는 경우의 수 중에, 가장 최단거리를 구하는 문제다. 일단 최단거리를 구하는 문제기 때문에 bfs 방식으로 구현하려고 했다. queue를 활용했고, 목적지에 도달하는 순간 바로 정답을 리턴한다. 아래는 첫번째 나의 솔루션인데, 해결되지 않았다. 디버깅 필요!!!

문제 이 문제는 네트 워크 상 컴퓨터끼리의 서로 연결 유무를 나타낸 lists 가 있을 때, 네트워크 덩어리가 몇 개인지 구하는 문제이다. 처음에는 감을 못 잡았지만, 천천히 고민하며 한 노드와 연결된 모든 노드를 재귀적으로 찾도록 dfs 방식을 활용하고, 다 찾은 경우에 개수를 +1 해주도록 작성했다. 여기서 visited가 필요한 이유는, 탐색 중에 걸리는 모든 노드는 재귀적으로 연결된 모든 노드를 확인하기 때문에 한번 본 노드는 볼 필요 없으므로 체크하기 위함이다. 아래는 solution이며 블로그를 참고하여 풀었다.

타켓넘버 이 문제가 왜 dfs/bfs 인지 처음에는 이해가 되질 않았다. 이 포스팅이 도움이 되었다. 모든 경우의 수의 합을 트리의 맨 마지막 노드라고 생각하면, 트리의 깊이인 idx 값을 숫자 개수와 비교하여 합을 체크하면 된다. 맨 마지막 노드가 아닐 경우에는 다음 숫자를 +- 한 값을 큐에 추가한다. 큐가 모두 빌 때까지 반복한다면, 모든 자식 노드를 확인한 셈이 될 것이다. 아래는 이해를 완료한 후 다시 작성한 solution이다.

히스토그램에서 가장 큰 직사각형 크기를 찾는 문제 빈 스택을 만든다. 첫 번째 막대에서 시작하여 모든 막대 hist[i]에 대해 다음을 수행합니다. 여기서 ' i '는 0에서 n-1까지 존재한다. 2-1. 스택이 비어 있거나 hist[i]가 스택 상단의 막대보다 높으면 ' i '를 밀어 스택에 넣습니다. 2-2. 이 막대가 스택 상단보다 작으면 스택 상단이 더 큰 동안 스택 상단을 계속 제거합니다. 2-2-1. 제거된 막대를 hist[tp]라고 합니다. hist[tp]를 가장 작은 막대로 사용하여 직사각형의 면적을 계산합니다. hist[tp]의 경우 '왼쪽 인덱스'는 스택의 이전(tp 이전) 항목이고 '오른쪽 인덱스'는 ' i '(현재 인덱스)입니다. 스택이 비어 있지 않으면 스택에서 모든 막대를 하나씩 제거하고 제거된 모든 막대에 대해 단계(2.2 및 2.3)를 수행합니다.