Programing/자료구조, Algorithm

바이너리 서치 python (binary search python)

바이너리 서치란? 정렬 된 자료를 반으로 나누어 계속하여 탐색하는 방법 정렬 할 자료는 오름차순 이어야 함 퍼포먼스가 좋음 구현시 필요한 변수 target : 찾고자 하는 목표 값 data : 오름차순으로 정렬 된 list (찾을 위치) start : data의 처음 값 index end : data의 마지막 값 index mid : start - end 의 중간 값 구현 (재귀) def bin_search(data, target, start, end): idx = (start + end) // 2 mid = data[idx] if target == mid: print(f'idx: {idx}') return elif mid > target: bin_search(data, target, start, idx..

2022. 4. 15. 03:27

Programing/자료구조, Algorithm

programmers 추석트래픽 [python]

def solution(lines): answer = 0 trafics = [] for l in lines: elements = l.split() S = elements[1].split(':') s = int((int(S[0]) * 3600 * 1000) + (int(S[1]) * 60 * 1000) + (float(S[2]) * 1000)) t = int(float(elements[2][:-1]) * 1000) start = (s - t) + 1 end = s trafics.append((start, end)) for trafic in trafics: count = 0 for tr in trafics: if tr[1] >= trafic[1] and tr[0] < trafic[1] + 1000: coun..

2022. 3. 15. 00:52

Programing/자료구조, Algorithm

programmers -프렌즈4블록- (python)

def solution(m, n, board): answer = 0 maps = [] # maps 좌표 만들기 for i in range(0, m): tmp = [] for j in range(0, n): tmp.append(board[i][j]) maps.append(tmp) while True: rm = [] # 지워질 블록 수집 for x in range(0, m-1): for y in range(0, n-1): if maps[x][y] == maps[x+1][y] and maps[x][y+1] == maps[x+1][y+1] and maps[x][y] == maps[x+1][y+1] and maps[x][y] != 0: rm.append((x, y)) rm.append((x+1, y)) rm.ap..

2022. 3. 14. 03:50

Programing/자료구조, Algorithm

프로그래머스(programmers) 신고 결과 받기 -python-

from collections import defaultdict def solution(id_list, report, k): report = set(report) answer = [] mails = defaultdict(int) # 메일 받을 개수 딕셔너리 users = defaultdict(int) # 유저 초기화 for u in id_list: mails[u] users[u] reports = defaultdict(list) # 신고 한 사람 저장 for r in report: a, b = r.split() reports[b].append(a) for i in users: # 신고 당한 횟수 지정 users[i] = len(reports[i]) pass for user in users: # "신고가 ..

2022. 3. 10. 20:24

Programing/자료구조, Algorithm

백준 1700 반례 (python)

#멀티탭 스케줄링 2022-02-16 22:18 start N, K = map(int, input().split()) seq = list(map(int, input().split())) plug = [] cnt = 0 for i in range(K): if seq[i] in plug: continue if len(plug) < N: plug.append(seq[i]) continue idxs = [] for j in range(N): if plug[j] in seq[i:]: idx = seq[i:].index(plug[j]) else: idx = 101 idxs.append(idx) del plug[idxs.index(max(idxs))] plug.append(seq[i]) cnt += 1 print(c..

2022. 2. 17. 02:44

Programing/자료구조, Algorithm

백준 1062 (python)

백준 1062 python 문제풀이 회고 비트 마스킹을 활용한 집합 연산을 알게 되었음 brute force 알고리즘 (완전탐색) 유형 -> DFS등 그래프 완전탐색 combination 같은 조합 완전탐색 중복 된 문자라는 키워드를 보고 set으로 접근하였지만, 시간/공간 복잡도에 걸림 풀이 풀이는 순서대로 주요 포인트 코드 해석을 위주로 작성 모든 조합을 다 순회해야한다 -> itertools 의 combination 기본적으로 {a, n, t, i, c} 다섯 문자는 무조건 포함이 되므로 5이하의 문자를 배우는 경우는 읽을 수 없음 print(0) 입력받은 K(개수)에서 문자 5개(a, n, t, i, c)를 제외 시킴 5개는 무조건 배워야 하니까. ky(key)와 v(value)를 enumerat..

2022. 2. 16. 22:12