Python With Algorithm

필자는 대부분 c,c++을 사용해서 코딩 공부를 했었다.컴퓨터 지식을 배우기에 둘 다 매우 중요한 프로그래밍 언어이지만 코딩테스트에 과연 적합할까? 라는 생각이 항상 있었다.지인들에게 물어봐도 코딩테스트는 python이 최고라고 했다.그래서 1학년 때 잠깐 맛보기로 배

배열은 메모리의 연속 공간에 값이 채워져 있는 자료구조인덱스틀 통해서 해당 주소 값을 참조 가능특징1\. 인덱스를 사용해서 값 O(1) 로 접근 가능2\. update 시 어려움. 하나씩 앞으로 당기거나 뒤로 미뤄야함3\. 일반적으로 배열은 처음 초기화 시 크기 고정4

숫자의 합 구하기 (백준 11720번, 시간 제한: 1초) > 입력: 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은

이론 구간 합 이용 시 합 배열을 먼저 구해야 한다. > s[i]=A[0]+A[1]+...+A[i] 합 배열을 미리 구해놓으면 시간 복잡도 O(n)=>O(1) 로 줄어든다. ex) A[i]~A[j] 까지 구간 합 구하려면 for문을 돌아야 하기 때문에 시간 복잡도 O

문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1 2 3 42 3 4 53

문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.입

문제어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.예를 들

문제주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷

문제N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다.입력첫째 줄에는 수의 개수 N(1 ≤ N ≤

슬라이딩 윈도우는 기존의 투 포인터 문제와 다르게 일정 window를 유지한 채로 sliding 하며 푸는 문제를 의미.문제평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’,

문제 예시N개의 수 A1, A2, ..., AN과 L이 주어진다.$Di$= $A{i-L+1}$ ~ $A_i$ 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 $A_i$는 무시하고 D를 구해야 한다.입력첫째 줄에 N과 L

Stack >stack 은 선입선출 (Last in Frist Out) LIFO 형식으로 이루어진 자료구조. stack.append(data) 를 하면 가장 뒤쪽에 들어오고 stack.pop() 을 하면 가장 뒤쪽이 삭제된다. top pointer로 stack에서

문제크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바

문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로

Bubble Sort:데이터의 인접 요소끼리 비교, swap방식을 통해 정렬하는 방식Selection Sort:대상에서 가장 크거나 작은 데이터를 찾아 선택하면서 정렬하는 방식Selection Sort:대상을 선택해 정렬된 영역에서 적절한 위치를 찾아가며 삽입하여 정렬

문제버블 소트 알고리즘을 다음과 같이 C++로 작성했다.위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A1부터 사용한다.위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.입력첫째 줄에 N이 주어진다. N은 500,000보다 작거

데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법.왼쪽부터 정렬되므로 inner for문 시 시작 지점을 잘 정하는 것이 그나마 효율성 측면에서 좋음.코팅테스트에서는 거의 사용하지 않는 알고리즘이다.문제배열을 정렬하는 것은 쉽다. 수가 주어

정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬하는 방식.시간 복잡도는 O(n^2)문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출

pivot 을 정해 해당 값보다 작은 데이터와 큰 데이터로 분류하여 recursive 하게 정렬하는 알고리즘=Divide and conquer시간복잡도가 일반적으로 O(nlogn)이지만 최악의 경우 O(n^2)start, end 2개의 포인터가 있어 pivot 기준 s

Divide and Conquer 방식을 이용하여, 데이터 분할 및 정렬하여 합치는 알고리즘.시간 복잡도 => O(nlogn)가장 작은 데이터 집합 부터 하나씩 정렬해가면서 => 전체 정렬 ex) 1\. 42 32 24 602\. 42 32 | 24 603\. 32 4

문제N개의 수로 이루어진 수열 A1, A2, …, AN이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이

기수 정렬(radix sort): 두 값을 비교하지 않고, 각 자리수에 따라 비교하여 정렬하는 알고리즘 시간복잡도 - O(kn) , k=데이터의 자릿수ex)16 80 18 77 03 24 88 23 1의 자리 숫자 기준으로 데이터 저장list0={80}list3={03

깊이 우선 탐색(dfs)그래프의 시작 노드에서 출발하여, 한쪽 분기를 정해, 최대 깊이까지 탐색하는 알고리즘.한번 방문한 노드는 다시 방문해서는 안된다. 구현 방법재귀 함수스택 이용시간복잡도 O(V+E) (노드 수 + 선분 수) 구현 구체화 방법1\. 그래프를 인접 리