Algorithm/Algorithm

[프로그래머스] 수식 최대화

문자열 식이 주어진다. 해당 문자열 식에서 연산의 우선순위를 변경했을 때, 절대값이 가장 큰 경우 그 값을 반환하는 알고리즘이다. 이 문제는 문자열을 원하는 형태로 나누고, 연산의 우선순위를 변경하여 각 값을 계산해본다. 이 값들 중 절대값이 가장 큰 값을 리턴하는 것인데, 이러한 반복 작업과 문자열을 필터링하는 것이 관건이다. itertools라이브러리, permutations 을 활용해야 한다. permutations는 순열 . combinations는 조합이다. 순열은 중복을 허용하지 않는다. (AB != BA) 정규식을 통해서 문자열을 구분하는 것도 원할하게 쓸줄 알아야한다. ( 풀었음에도 몇 달 지나니 아예 또 못푸는 현상 반복...) re.split() 함수 re.split('정규식', 문자열..

Undirected Graph Adjacency List, Matrix:: 무 방향 그래프, 인접 목록, 행렬

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보, 잡지식을 꾸준히 쌓아가는 글입니다. 출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ 무방향 그래프를 나타내는 두 가지 방법이 있다. ( 방향이 없는 그래프 ) 인접 행렬 인접 목록 1. 인접 행렬 Adjacency Matrix 그래프 이론에서 어느 꼭짓점들이 변으로 연결되어있는지 나타내는 ㅎㅎㅎㅎ정사각형 행렬(노드의 갯수 x 노드의 갯수)입니다. 연결 행렬이라고도 합니다. 그래프에서 방향이 지정되지 않은 경우 인접 행렬은 대칭이다. 1과 0으로 노드들의 연결 관계를 표현한다. ( True 와 False로 표현하기도 한다.) 즉, 인접 행렬에서 간선인 경우 matrix(i, j) = 1이고 선이 없다면..

불량사용자 - 카카오 코딩테스트

불량사용자 2019 카카오 개발자 겨울 인턴십 Level 3 응모자가 아래와 같이 있고, 불량으로 응모한 아이디가 있다. 이를 걸르기 위해 불량아이디인 경우를 모두 뽑아내라. 응모자 아이디 불량 사용자 frodo fr*d* fradi abc1** crodo abc123 frodoc 제재 아이디 경우1 제재 아이디 경우2 frodo fradi abc123 abc123 Retrun 값은 2가 된다. 입력은 배열의 형태로 주어진다. ["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "abc1**"] Permutations를 사용하여 푼다. 1. 사용자 아이디의 조합을 불량 사용자 인원의 수 만큼 조합을 만들어낸다. 2. 이러한 조합에서 각 조합을 check..

Binary Search 이진 탐색 이분 탐색

✊✋ Binary Search ✋✊ 이진탐색, 이분탐색 0, 1, 0, 1??? 처음 이 알고리즘을 알았을 때는 0 과 1의 알고리즘인 줄 알았다. 그러나 그러한 개념보다는 이진 탐색은 탐색시간을 단축시키기 위한 알고리즘으로 기억하는게 옳다. 반드시 정렬을 하여 사용하는데, 개인적으로 사용을 하면서 느낀점과 기억해야 할 것을 기록하려 한다. 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법이다. 순차 탐색에 비해서는 굉장히 효율적이고 빨라보이지만, 반드시 정렬이 되어있어햐 하며, 경우에 따라서는 쓰기 곤란한 경우가 있다. 이진 탐색의 계산복잡도는 O(logn) 순차 탐색이 O(n)이다. - 연결리스트의 경우 이러한 이진 탐색은 불가능 하다. (물론 구현은 가능하다. 번거로울 뿐) 기..

🧩 코딩 테스트 정복기 @21#B*06

파이썬 알고리즘 인터뷰 📚📚📚👈🏻 책 구매 링크 🤴🏻👸🏻👵🏻👴🏻 👈🏻 소스코드 깃허브 😥😱🤪👈🏻 책 정오표 🏓📡📺 👈🏻 유투브 채널 문자열 조작 String Manipulation 문자열을 변경, 분리하는 등의 여러 과정을 말한다. 코테에서도 문자열 조작은 매우 빈번하게 출제되는 주제 중 하나이다. 특히 실무에서도 다양한 분야에 쓰이는 상당히 실용적인 주제이다. 문자열 처리와 관련한 알고리즘이 쓰이는 대표적인 분야. 1. 정보처리 분야 : 키워드 탐색 시, 문자열 처리 앱을 이용하게 된다. 특히 현대의 거의 모든 정보는 문자열로 구성되어 있으며 문자열 처리는 정보처리에 핵심이다. 2. 통신시스템 분야: 데이터 전송에서 문자열 처리는 매우 중요하다. 문자, 이메일 등에 기본적으로 사용된다. 3. 프로그래밍..

[백트래킹] 퇴각검색

BackTracking 백트래킹 = 퇴각검색 백트래킹은 한정 조건을 가진 문제를 풀려는 전략이다. 1950년대 미국 수학자 D.H.레머가 만들었다. 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각가의 변수들을 값이 있어야 한다. 퇴각 검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기때문이다. 결국 풀이 시간이 단축된다. 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 DFS를 사용한다. 탐색 중 오답을 만나면 이전 분기점으로 돌아..

🧩 코딩 테스트 정복기 @21#B*05

파이썬 알고리즘 인터뷰 📚📚📚👈🏻 책 구매 링크 🤴🏻👸🏻👵🏻👴🏻 👈🏻 소스코드 깃허브 😥😱🤪👈🏻 책 정오표 🏓📡📺 👈🏻 유투브 채널 리스트 List 순서대로 저장하는 시퀀스이자 변경 가능한 목록을 말한다. 입력 순서가 유지되며, 내부적으로 동적 배열로 구현되어있다. 파이썬의 리스트는 큐와 스택에서 사용가능한 모든 연산을 제공하고 있다. 엄청나게 편한 것이다. 연산 시간 복잡도 설명 len(a) O(1) 전체 요소의 갯수 a[i] O(1) 인덱스 i의 값 a[i : j] O(k) i 부터 j까지 슬라이스의 길이만큼인 k개의 요소들 elem in a O(n) elem요소가 존재하는 지 확인, 순차탐색이므로, n만큼 소요 a.count(elem) O(n) elem요소의 갯수를 리턴 a.index(elem) O..

🧩 코딩 테스트 정복기 @21#B*04

파이썬 알고리즘 인터뷰 📚📚📚👈🏻 책 구매 링크 🤴🏻👸🏻👵🏻👴🏻 👈🏻 소스코드 깃허브 😥😱🤪👈🏻 책 정오표 🏓📡📺 👈🏻 유투브 채널 빅오, 자료형 Big-O 빅오는 입력값이 커질 때 알고리즘의 실행 시간과 함께 공간 요구사항이 어떻게 증가하는지를 분류하는데 사용한다. (간단히 말하면 알고리즘의 효율성을 평가하는 척도라고 보면된다.) 시간 복잡도 Time Complexity 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미한다. Computational Complexity 계산 복잡도를 표기하는 대표적인 방법이 빅오인 것이다. O(1) : 입력이 아무리 커져도 일정하다는 의미이다. 최고의 알고리즘. 이상적인 알고리즘이다. O(log n) : 로그는 매우 큰 입력값에도 크게 영향을 받지..