꺼내먹는지식 준

이진 탐색을 이해하기 위해서는 순차 탐색을 먼저 살펴볼 필요가 있다. N 개의 데이터가 있을 때 데이터를 차례대로 하나씩 확인하는 그 자체가 바로 순차 탐색이다. 순차탐색 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. import sys input = sys.stdin.readline array = [1,2,3,4,5,1,2,3,1,2,1,2,3,45,56,1,32,4,14,21,41,5,14,124,12341,1,1,213,1,2,3,4,1,2,3,1,1,1,2,3,1,2,3] N = int(input()) cnt = 0 for i in array: if i == N: cnt += 1 print(cnt) 주어진 array ..

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 이진탐색을 위해서는 정렬 알고리즘으로 데이터를 정렬하는 것이 선 과정이다. 다음의 알고리즘을 알아보자. 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 1) 선택정렬 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. 매번 가장 작은 것을 '선택'하므로 선택 정렬 알고리즘이라 한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def swap(x,y): tmp = x x = y y = tmp return x, y for i in range(len(array)): minimum = 1e9 for j ..

탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 그래프, 트리 등의 자료구조 안에서 탐색 하는 문제를 주로 다룬다. 대표적으로 DFS, BFS 를 꼽고, 이 두 알고리즘은 원리를 완벽하게 이해해야 문제 해결이 가능하다. 두 알고리즘의 원리가 되는 Stack, Queue 를 간단하게 살펴보자. STACK 스택은 박스쌓기를 기억하면 잊지 않을 수 있다 . 다음과 같이 박스를 쌓으면 맨 하단의 박스가 당연히 가장 먼저 내려놓은 박스이다. 그러나 우리가 다시 박스를 들어올릴 때는 최 상단의 박스부터 들어올리게 된다. 즉, 처음에 넣은 것이 (First in) 가장 마지막에 나오게 된다(Last out). QUEUE 큐는 버스를 생각하면 잊지 않을 수 있다. 버스는 한쪽 입구로 타서 안쪽 출구로 내린..

구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다. 즉, 1) 문제를 보고 2) 풀이를 떠올리고, 3) 소스코드로 옮겨야 한다. 즉, 마치 게임에서 손 빠른 사람을 '피지컬'이 좋다고 하듯이, 구현 유형 문제는 소스 코드로 구현을 하는 코딩 '피지컬'을 요구한다고 볼 수 도 있다. 소스코드로 옮기는 과정이 원할하기 위해서는 기본적으로 다음의 능력이 필요하다. 1) 충분한 라이브러리 사용 경험 2) 충분한 문법 숙지 완전 탐색과 시뮬레이션은 구현에 포함한다고 가정하였다. 때로 기업 공채에서는 웹 서버나 데이터 분석 기초 지식이 필요하기도 하다. 몇개의 구현 알고리즘을 풀어보자. 1) 상하좌우 N X N 정사각형의 한 블럭(1 X 1)위에 여행가가 서 있다. 가장 왼쪽 (1,1) 가장 오른쪽..

그간 코딩 테스트를 좀 주먹구구식으로 풀었다. 그러다보니 특정 알고리즘 문제를 풀어도, 내가 얼마만큼 왔고 어느정도 더 해야하는지 감이 잘 안잡혔다. 이를 위해 1독을 목표로 한 책을 선정했다. 바로 나동빈씨의 "이것이 취업을 위한 코딩 테스트다" 라는 책이다. 그 중 첫 쳅터인 그리디이다. 그리디 1) 어떠한 문제가 있을 때 단순 무식하게, 현재 상황에서 지금 당장 좋은 것만 고르는 방법 2) 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디는 다익스트라와 같이 암기 기반 알고리즘과 다르게 출제 폭이 럽어 단순 암기가 불가능하다. 즉 다양한 문제를 접해봐야한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알..

https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 조이스틱 문제 설명 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으..

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다. 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다. 입출력 예 ..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1..

우선 순위 큐는 데이터에서 우선 순위가 높은 데이터 순으로 순차적으로 먼저 뽑는 자료구조입니다. 리스트로도 충분히 구현할 수 있지만, 문제는 삽입 시간 대비 삭제 시간이 너무 커 효율적이지 못합니다. (여기서 리스트는 넣고, 찾고자 하는 조건의 원소를 원소별로 모두 비교하여 삭제하는 방법입니다.) 이에 따라 원소를 삽입할 때는 $\log N$의 시간이 걸리지만 대신에 찾고자 하는 조건의 원소(가장 큰 수, 가장 작은 수)를 찾는 것도 $\log N$으로 해결할 수 있는 자료구조 힙을 사용합니다. 힙은 기본 지식이 없는 상태에서 구현으로 떠올리기 어려운 알고리즘입니다. 이는 힙의 동작의 철학(삽입 혹은 제거 과정에서 원하는 조건을 한번에 처리하는 것이 아니라, 삽입 제거 2가지 과정이 서로 상호보완) 자체..

문자열 압축 문제를 풀었지만, refactoring 의 절실함을 느끼고 작성한다. https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제가 카카오 문제라 길고 복잡하니 해당 링크에서 확인하자. def solution(s): if len(s) == 1: return 1 lst = [] for i in range(1, int(len(s)//2)+1): tmp = [] for j in range(0, len(..