기능개발https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 프로그래머스 알고리즘 고득점 kit의 스택/큐 문제 중 기능개발을 풀어보았다. 좋은 문제여서 오답을 작성한다. 1️⃣ 분석작업 진행도와 해당 작업의 속도를 담은 두 개의 배열이 주어진다. [90, 55], [1, 10] 이렇게 주어진다면 후자의 일이 더 빠르게 끝난다. 첫 번째 일이 끝나야 두 번째 일이 같이 배포될 수 있기 때문에 한 타임스탬프에 배포되는 일의 수는 2개이다. 이런식으로 배열이 주어진다면 각각의 타임스탬프마다 배포되는 일이 ..

스택1️⃣ 스택LIFO(Last In First Out)의 자료구조. 나중에 들어간 원소가 가장 먼저 나온다. DFS, 백트래킹 문제에 자주 등장하니 잘 알아둬야 한다. 2️⃣ 파이썬에서 스택파이썬에서는 리스트로 스택을 구현한다.list.append(원소)list.pop()list[-1] : pop할 원소 확인할 때 사용 큐1️⃣ 큐FIFO(First In First Out)의 자료구조. 먼저 들어간 원소가 먼저 나온다. 스택과 달리 양방향으로 삽입과 삭제를 한다. 2️⃣ 파이썬에서의 큐파이썬에서는 deque로 큐를 구현한다. list로 구현하지 않는 이유는 list가 시간복잡도가 더 걸리기 때문이다.큐에서는 deque.popleft()로 삭제를 구현한다. list.popleft()를 사용하면 시간복..

슬라이딩 윈도우투 포인터에서 두 포인터가 고정된 채로 움직이는 윈도우를 슬라이딩 윈도우라 한다. 저번에 투포인터에서 맨 앞 문자열을 추가하고 맨 뒤 문자열은 빼고, 이런 생각을 한 적이 있었는데 그 개념이 슬라이딩 윈도우에서 쓰인다. 네트워크 시간에도 배운 적이 있으니 잘 알고 넘어가도록 하자. DNA 비밀번호 (12891)처음으로 로직을 고민하고 코딩해 맞춘 문제이다. 기분이 째진다.https://www.acmicpc.net/problem/12891문제가 길어 링크를 남긴다. 1️⃣ 분석 문자열 길이와 부분 문자열 길이가 최대 백만이다. 최악의 경우 이중 for문을 통한 알고리즘 구현은 제한시간을 넘어가므로 불가하다. 그래서 투포인터의 진화형인 슬라이딩 윈도우를 써야 한다. 슬라이딩 윈도우는 O(N)..

투포인터연속된 합을 구할 때 사용하는 알고리즘이다. 구간 합으로 구할 수도 있지만 작은 시간복잡도가 필요할 때 사용할 수 있다. start_idx와 end_idx를 놓는다.다음과 같은 방법으로 합이 목표한 값과 맞는지 판단하면서 포인터들을 옮긴다.sum sum > M : sum -= start_idx; start_idx++;sum == M : end_idx++; sum += end_idx; cnt++;종료 조건은 end_idx == M일 때다.왜 start_idx가 움직일 때 더하고 end_idx가 움직일 때 빼는 건 안되는지 생각해 봤다. start_idx가 더하면서 움직이면 나중에 end_idx를 추월한다. 이는 우리가 구성한 로직과 맞지 않다.end_idx를 빼면서 가게 되면 앞으로 올 수들을 더..

구간 합합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 알고리즘이다. 구간 합 알고리즘을 사용하기 위해선 합 배열을 만들어야 한다. 리스트 A가 있을 때 합 배열의 정의는 다음과 같다. S[i] = A[0] + A[1] + ... + A[i] (A[0]부터 A[i]까지의 합) 합 배열은 기존 리스트를 전처리한 배열이라고 보면 된다. 합 배열을 통해 배열의 구간의 합을 구할 때 시간 복잡도가 O(N)에서 O(1)로 줄어든다. 🔑 합 배열 제작 공식S[i] = S[i-1] + A[i] (전의 합 배열에서 새로운 원소를 더한다.) 🔑 구간 합 공식A[i] + ... + A[j] = S[j] - S[i-1] 합 배열만 미리 구해두면 구간 합은 한번에 구할 수 있다. 구간 합은 코딩테스트에서 ..

배열과 리스트파이썬에서 배열과 리스트는 따로 구별하지 않지만 각각의 특징을 알아두면 좋다. 파이썬의 리스트는 두 자료구조의 특징을 모두 가지고 있다. 1️⃣ 배열배열은 연속된 메모리 주소 공간에 값이 채워져 있는 자료구조다. 배열의 값을 인덱스로 참조할 수 있으며 선언된 자료형만 저장할 수 있다. 📍 주요 특징인덱스로 값을 참조할 수 있다. => 참조 O(1)삽입, 삭제가 오래 걸린다. (삽입하거나, 삭제한 뒤 근처의 데이터들을 모두 옮겨줘야 한다.) => 삽입, 삭제 O(N)처음 선언할 때 크기가 정해지고 그 다음은 크기를 수정할 수 없다 2️⃣ 리스트값과 포인터를 묶은 노드를 포인터로 연결한 자료구조다. 📍 주요 특징값을 참조할 땐 처음부터 참조해 포인터를 타고 가야 한다. => 참조 O(N)..

디버깅문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅이라 한다. IDE에서는 디버깅을 위한 툴을 제공한다. 프로그래머스 같은 온라인 사이트에서는 디버깅 툴을 본 적이 없는 것 같다. 툴을 사용하지 않고도 발생할 수 있는 문제들을 알고 있어야 이에 대응할 수 있어야 한다. 코테 때 하기 쉬운 4가지 실수1️⃣ 변수 초기화 오류 여러 테스트 케이스를 진행하다 보면 변수 초기화가 안되는 경우가 있다. 이를 대비하기 위해 초기화 하는 구문을 꼭 넣자. 2️⃣ 반복문 인덱스 범위 오류 종종 반복문에서 반복 범위를 잘못 지정하거나 비교 연산자를 잘못 사용하는 경우다.N = 1000for i in range(1, N): print(i)다음 코드의 반복 횟수는 1부터 N-1까지다. (1, N+1)까지 설정해..

알고리즘 선택의 중요성좋은 알고리즘을 선택하지 못한다면 문제에 적합한 좋은 코드는 나오지 않는다. 좋은 알고리즘을 찾기 위해선 시간 복잡도 개념을 알고 있어야 한다. 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 파이썬 프로그램은 1초에 대략 2천만번에서 1억번까지의 연산을 수행한다. 최악의 경우를 생각하는 빅-오 노테이션을 통해 1초에 2천만번의 계산을 진행한다고 가정하자. 시간 복잡도 활용하기백준 2751 수 정렬 문제2를 보고 시간 복잡도에 대해 알아보자.https://www.acmicpc.net/problem/2751 수 정렬하기 2시간 제한 : 2초문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,0..