본문 바로가기

전체 글

 (76)
[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) 우선순위 큐(Priority Queue) 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - 데이터를 우선순위에 따라 처리하고 싶을 때 사용 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐(Priority Queue) 구현 방법 - 리스트 이용하여 구현 - 힙(heap)을 이용하여 구현 - 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도 우선순위 큐 구현 방법 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) _..
[프로그래머스] 신규 아이디 추천 (카카오 문제) (Python) 문제 - 신규 아이디 추천 https://programmers.co.kr/learn/courses/30/lessons/72410?language=python3 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 나의 풀이 문제 해결 방법 1 ) 정규표현식을 이용하여 문제를 풀었다. 2 ) 각 단계별로 맞는 정규표현식을 코드로 표현하였고, 이를 수행시켰다. 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 ..
[알고리즘] 개발형 코딩테스트_REST API 서버와 클라이언트 클라이언트가 요청(Request)를 보내면 서버가 응답(Response)함 클라이언트(Client) = 고객 서버로 요청을 보내고 응답이 도착할 때까지 대기 서버로부터 응답을 받은 뒤에 서버의 응답을 화면에 출력 - 웹 브라우저 : 서버로부터 받은 HTML, CSS 코드를 화면에 적절한 형태로 출력 서버(Server) = 서비스 제공자 클라이언트로부터 받은 요청(Request)을 처리해 응답(Response)을 전송 - 웹 서버 : 로그인 요청을 받아 아이디와 비밀번호가 정확하지 검사하고 그 결과를 응답 HTTP 개요 HTTP(HyperText Transfer Protocol) : 웹상에서 데이터를 주고받기 위한 프로토콜 - 웹 문서(HTML 파일)를 주고받는 데 사용 - 모바일 앱 및..
[Python] 정규표현식(Regular Expressions) - re 모듈 (2) 파이썬에서 정규 표현식을 지원하는 re 모듈 import re p = re.compile('ab*') - re.compile을 사용하여 정규표현식을 컴파일 - re.compile의 결과로 돌려주는 객체 p(컴파일된 객체)를 사용하여 그 이후 작업 수행 정규식을 이용한 문자열 검색 match( ) 문자열의 처음부터 정규식(정규표현식)과 매치되는지 조사 search( ) 문자열 전체를 검색하여 정규식과 매치되는지 조사 findall( ) 정규식과 매치되는 모든 문자열을 리스트로 반환 finditer( ) 정규식과 매치되는 모든 문자열을 반복 가능한 객체로 반환 match( )와 search( )는 정규식과 매치될 때는 match 객체 반환, 매치되지 않을 때는 None 반환 import re p = re.c..
[Python] 정규표현식(Regular Expressions)(1) 정규표현식(Regular Expressions) - 복잡한 문자열을 처리할 때 사용하는 기법 - 예를 들어, 주민등록번호의 뒷자리를 * 문자로 변경하는 문제 import re data = """ park 800905-1049118 kim 700905-1059119 """ pat = re.compile("(\d{6})[-]\d{7}") print(pat.sub("\g-*******",data)) # 결과값 # park 800905-******* # kim 700905-******* 정규표현식의 기초, 메타문자 메타문자 - 원래 그 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자 문자 클래스 [ ] → [ ] 사이의 문자들과 매치 - [abc] → a, b, c 중 한개의 문자와 매치 - a : 매치(a..
[백준] 13460번_구슬 탈출2 (Python/파이썬) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 ..
[백준] 2960번_에라토스테네스의 체 (Python/파이썬) https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤..
[알고리즘] 코딩 테스트에서 자주 출제되는 기타 알고리즘 소수(Prime Number) 소수랑 1보다 큰 자연주 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 ( ex. 7 ) def is_prime_number(x): # 2부터 (x-1) 까지의 모든 수를 확인하며 for i in range(2, x-1): if x % i == 0: return False return True print(is_prime_number(4)) print(is_prime_number(13)) # False # True 소수(Prime Number) 성능 분석 2부터 X-1까지의 모든 자연수에 대하여 확인을 하며 연산을 수행 -> O(X) 개선된 소수 판별 알고리즘 약수의 성질 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸 특정한 자연수..

티스토리툴바