DevKim

programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr [문제 접근] - 암호화 되어있는 정수배열을 각각 2진수로 바꿔준 뒤, 두개의 배열을 비교해서 조건에 따라 문자열에 추가 [알고리즘] - 완전탐색 [코드] def solution(n, arr1, arr2): answer = [] for i in range(n): n1=arr1[i] n2=arr2[i] # n자리수의 이진법으로 바꾸기 a='' b='' result='' ..

programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr [문제 접근] - 파이썬의 정규표현식 re를 이용해서 각 단계를 하나씩 한줄로 구현 [알고리즘] - 문자열 처리 (구현) [코드] import re def solution(new_id): answer = '' i=0 #1단계 new_id=new_id.lower() #2단계 new_id=re.sub("[^0-9a-z_.-]","",new_id) #3단계 new_id=re.s..

[1] Union-find [ 개념 ] - 서로소 집합을 찾는 것 = 공통 원소가 없는 두 집합을 의미함 - Union = 합집합 - Find = 찾기 [ 과정 ] 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다 A와 B의 루트 노드 A',B'를 각각 찾는다 A'을 B'의 부모 노드로 설정한다 반복 [ 최적화 ] - find 함수를 최적화하기 위해, 경로 압축을 이용한다 - find 함수를 재귀적으로 호출한 뒤에, 부모 테이블 값을 바로 갱신 [ 응용 ] - "무방향" 그래프 내에서의 사이클 판별시 - 두 노드의 루트 노드가 서로 같다면 cycle(사이클)이 발생한 것임 [ 코드 ] def find_parent(parent,x): if parent[x]!=x: parent[x..

- '하나'의 정점에서 다른 모든 정점으로 가는 최단 경로 [ 조건 ] - 음의 간선이 존재하지 않음 [ 기존의 선형탐색 방법의 다익스트라 ] - O(n^2) 의 시간 복잡도를 가짐 - 문제점은 노드의 개수가 10,000개가 넘어가는 문제라면 시간초과 가능성이 높음 [ 우선순위 큐를 이용한 다익스트라 ] - 힙을 이용하여 구현 - python 에선 heapq 라이브러리로 구현되어있음 - O(NongN) 의 시간복잡도 [ 과정 ] 최단거리 테이블을 초기화(자기 자신은 0, 직접 연결되어있지 않는건 무한대로 초기화) 처음엔 가장 가중치가 작은 값을 선택함 하나의 노드를 선택하고 해당 노드를 거쳐서 가는 경우를 모두 고려하여 가장 최소인 값으로 업데이트 (이때, 값이 새로 갱신된 경..

www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 정답률이 낮은 문제!!!! 왜냐고!!!! 왜긴왜야.. 또 시간초과지 뭐.. ㅎ ㅎ ㅎ ㅎ 에라토스테네의 체를 이용하였는데도 시간 초과가 발생했다. 그 문제를 살펴보니 #시간 초과의 이유 #1.에라토스테네스의 체를 이용하여 홀수인 소수를 구하는 과정에서 n이 입력될때마다 에라토스 함수를 돌림 #2.함수 내에서 홀수인 소수를 저장하는 리스트를 따로 생성함 #3.처음에 a 인 부분을 구하면 그..

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제 이름을 보면 알겠지만.. 같은 문제가 메모리와 시간초과 제한만 다르게 출제되어있다. 1과 2는 sorted 내장 함수와 다른 정렬 알고리즘을 이용하여 쉽게 풀었지만, 이번 문제는 시간제한과 메모리 제한이 다음과 같다. 3 초 (하단 참고) 8 MB (하단 참고) 입력개수 N(1 ≤ N ≤ 10,000,000)로 주어져있고, 입력 수는 10,000보다 작거나 같은 자연수인 것에 비해 메모리 제한이 너무 작아서 4번이나 메..

[1] 합병 정렬 merge sort *서로 떨어져있는 원소를 교환하는 것이 아니므로, 안정적임 *merge : 정렬을 마친 두 배열을 비교하여 합침 O(n) *전체 시간 복잡도 = O(n log n) (1) sorted 함수 사용하기 -> 정렬을 마친 상태가 아니더라도 적용가능하지만, 빠르지 않음 c=list(sorted(a+b)) (2) heapq 모듈의 merge() 함수 사용하기 ->속도가 빠름 c=list(heapq.merge(a,b)) [2] 퀵 정렬 quick sort 퀵 정렬은 가장 잘 알려진 빠른 정렬 알고리즘이다. pivot을 이용하여 분할 정복 해나가는 알고리즘으로, pivot을 어떤 식으로 정할지가 성능에 크게 영향을 미친다. 평균 시간 복잡도는 O(NlogN) 이며, 만약 매번 1..

1> 단순 선택 정렬 O(n^2) : 말그대로 가장 작은 애 부터 선택해서 순서에 맞는 위치로 옮기며 작업 반복 def select_sort(List): n=len(List) for i in range(n-1 ): min=i for j in range(i,n): if List[min] > List[j]: min=j List[i],List[min]=List[min],List[i] return List List=list(map(int,input().split())) print(*select_sort(List)) 2> 단순 삽입 정렬 O(n^2) : 노드를 하나씩 선택해서 알맞은 위치에 삽입함 def insert_sort(List): k=0 n=len(List) for i in range(1,n): k=i f..