Algorithm

k진수 찾기랑 소수 찾기는 코테에서 꽤나 빈출 유형으로 나오는데 두 가지가 결합된 문제가 있어 정리해본다. 기억해두고 더 이상 헷갈리지 말자. https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr k진수 k진법이란 0부터 k개의 숫자를 사용해서 수를 표현하는 방법으로, 2진법은 0과 1의 2가지 숫자로 수를 표현한다. 3진법은 0,1,2의 3가지 숫자로 수를 표현한다. 즉, 0부터 k-1까지의 숫자로 수를 표현하는 것을 말한다. 구하는 방법은 그림과..

코딩 테스트 뿐만 아니라 데이터 분석을 할 때도 정규 표현식을 많이 사용하기 때문에 한번 쯤 꼭 정리해야 겠다고 생각했다! 정규 표현식에서 사용하는 메타 문자 메타 문자란? 원래 그 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자를 말한다. 즉, 온점(.)을 본래 의미(문장을 끝냄)가 아닌 다른 의미를 부여하여 사용하겠다는 뜻이다. 메타 문자의 종류는 다음과 같은 것들이 있다. . ^ $ * + ? { } [ ] \ | ( ) 정규 표현식에 메타 문자를 사용하여 특별한 의미를 부여하였다. 각 메타 문자별로 어떤 의미를 가지고 있는지, 이를 활용한 정규 표현식을 정리해보겠다. 문자 클래스 [] 의미: [] 사이의 문자들과 매치, [] 사이에는 아무 문자나 다 들어갈 수 있음 관련 문제 프로그래머스 신규..

그래프의 기본 구조 예전 포스팅 (https://emperor-one-data-study.tistory.com/45) 에서도 언급했듯이 그래프는 node와 edge (간선)로 구성되어 있다. 프로그램에서 그래프를 나타내는 방식으로는 인접 리스트와 인접 행렬이 있는데 두 가지 표현 방식을 파이썬 코드로 알아보았다. 인접 행렬 (adjacency matrix) 2차원 배열에 각 노드가 연결된 형식 파이썬에서는 2차원 리스트로 구현할 수 있음 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성함 (실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값 중에서 9999999999 등의 값으로 초기화하는 경우가 많음) 0 1 2 0 0 7 5 1 7 0 무한 2 5 무한 0 0,1,2를 노드로 하는 그래프에서 각..

스택과 큐 관련 내용은 이전 글 참고 https://emperor-one-data-study.tistory.com/33 [코딩테스트/Python] 꼭 필요한 자료구조 기초: 스택과 큐 자료 구조에 대해 왜 알아야 할까? 프로그래밍 문제 중 "탐색" 유형은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 코딩 테스트에서는 그래프, 트리 등의 자료구조 안에서 탐색을 emperor-one-data-study.tistory.com DFS와 BFS를 구현하기 위해서는 스택과 큐 뿐만 아니라 재귀 함수에 대해서도 이해하고 있어야 한다. 재귀 함수 (Recursive Function) : 자기 자신을 다시 호출하는 함수 가장 간단한 재귀함수 예제 위와 같이 재귀 함수 호출 문구가 무한히 호출된다. 자기 자신..

문제 1. 진도 100일 때 서비스에 반영 가능 2. 각 기능의 개발 속도는 모두 다르고, 앞 서비스가 완료되어야 뒤 서비스도 반영 가능 3. progresses: 작업의 진도 / speed : 개발 속도 , 하루에 얼마나 작업할 수 있는지 4. 각 배포마다 몇 개의 기능이 배포 되는지를 return 풀이 시도하다가 만것 def solution(progresses, speeds): #일단 dictionary 만들어놓기 dic = dict(zip(progresses, speeds)) day=[] for key, value in dic.items(): if key+value*day = 100 answer = [] return answer 처음에는 단순하게 문제 의미만 파악하면서 풀어보려고 했는데 이렇게 진행..

문제 que 관련 문제: 하나의 큐에서 원소 추출해서 다른 큐에 집어넣기 (큐는 선입 선출) 결과적으로 두 큐의 원소 합이 같도록 만들기(전체 합을 파악한 후, 나눠서 담는다고 생각하자) 풀이 첫 시도 from collections import deque def solution(queue1, queue2): answer = 0 queue1=deque(queue1) ; queue2=deque(queue2) #큐로 변환해주기(popleft 함수 사용위해) que_sum = sum(queue1)+sum(queue2) q_s = que_sum //2 if que_sum % 2 != 0: #반반 나눌 수 없으면(2로 나누어 떨어지지 않으면 -1 return) return -1 if que_sum % 2 == 0:..

자료 구조에 대해 왜 알아야 할까? 프로그래밍 문제 중 "탐색" 유형은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 코딩 테스트에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS, BFS가 있는데, 해당 알고리즘을 잘 이해해야만 탐색 유형 문제들을 잘 풀어갈 수 있다. 탐색 알고리즘을 이해하기 위한 필수적인 자료구조로는 스택, 큐, 재귀 함수 등이 있다. 해당 개념을 완벽히 이해하고 넘어가보자! (재귀 함수는 다음 포스팅에서 다루고자 한다. ) 자료 구조, 스택과 큐 자료 구조는 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 자료 구조 중 스택과 큐를 쓰기 위해서는 이를 이루는 두가지 주요 함수에 대해 알아야 한다. 삽..

구현이란? 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 과정이다. 별도의 유형으로 다룬다기 보다, 대부분의 문제 유형에서 아이디어를 얻고, 이를 코드로 구현하는 모든 과정을 이른다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 주로 "구현" 문제로 일컫는다. EX) 알고리즘은 간단한데 코드가 너무 길어지는 문제, 특정 소수점 자리까지 출력해야하는 문제, 파싱해야하는 문제 등등 완전 탐색: 모든 경우의 수를 주저없이 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 유의해야할 점 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려할 것: list를 여러개 선언하고, 크기가 큰 list가 있을 경우 메모리 에러가 발..