본문 바로가기

Python191

해시 테이블 해시 테이블은 매우 빠른 삽입, 삭제, 탐색 연산을 제공하는 자료구조 python에서는 dict를 사용 key와 value의 형태로 해시 테이블에 저장 ( 해시 테이블은 보통 배열을 사용, 이 슬롯의 크기를 m이라 함) 해시 테이블에 저장할 때 hash Function을 이용해서 특정한 인덱스(Hash Code)를 지정해주게 됨 python에서는 hash(key)를 입력하게 되면 특정 key가 출력됨 hash function 1. perfect hash function : 이상적인 h.f key -> slot 이 1:1로 매치됨 즉, collision이 발생하지 않음 -> 비현실적 2. universal hash function : x란 key 값과 y란 key 값이 있다고 했을 때 f(x) == f(y.. 2021. 12. 29.
[프로그래머스] 무지의 먹방 라이브 (Python) https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 딕셔너리 + 정렬을 활용해서 문제를 풀었다. 효율성에서 아슬아슬하게 통과해서 더 좋은 풀이가 있을 것 같다. 알고리즘 : 1. 먹는 것이 종료되는 시간이 같은 음식을 dict를 통해 세어 준다. (defaultdict 활용) 2. 짧은 시간 순서대로 dict.items를 정렬한다. - food_times의 입력이 [6, 6, 1, 1, 2, 2, 3, 5] 일 경우 아래와 같이 정렬됨. - Tsort => [(1, 2), (2, 2), (3, 1), (5, 1), (6, 2)] (음식 다 먹는 시간, 그 음식의 개수) 3. 정렬된 T.. 2021. 12. 28.
양방향 연결 리스트 구현 https://www.youtube.com/watch?v=zWrFVf9_YTQ&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=16 교수님 자료를 보고 리뷰한 포스팅 단방향 연결 리스트의 단점 - 만약 tail 노드를 지우고 싶다고 했을 때, tail 노드를 안다고 하더라도 tail 노드 앞의 prev 노드를 알지 못하기 때문에 결국 head부터 끝까지 search 하며 찾아야 한다. O( n ) 시간 소요 - 이를 해결하기 위해 왼쪽 방향 오른쪽 방향의 양방향 연결 리스트가 필요하게 됨. - 단점 : 링크가 양쪽으로 있어서 복잡성이 증가함 Splice 연산 def splice(self, a, b, x) : 조건 1 : a ->.. -> b : a에서 앞으로 가다 보면 .. 2021. 12. 28.
[프로그래머스] 가사 검색 (Python) https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문자열 검색 알고리즘인 Trie를 활용해서 푸는 문제다 계속 효율성 4번에서 시간 초과가 나서 풀이를 참고하고 그대로 구현했다. class Trie(): def __init__(self): self.child = dict() self.count = 0 def insert(self,str): curr = self for ch in str: curr.count += 1 if ch not in curr.child: curr.child[ch] = Trie() curr = curr.child[ch] curr.count += 1 def search(se.. 2021. 12. 27.
[프로그래머스] 단어 퍼즐(Python) https://programmers.co.kr/learn/courses/30/lessons/12983 코딩테스트 연습 - 단어 퍼즐 단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na programmers.co.kr dp 활용 문제다. 처음에 그리디 + dfs로 풀었는데 시간 초과가 났다. dp를 생각하긴 했는데 dp에 익숙하지 않아서 다른 사람 풀이를 참고했다. dp를 설계할 때 일반적으로 원하는 답을 설정하면 구하기 쉽다. 이 문제는 각 위치에서 단어조각 개수의 최솟값을 return 하는 문제이므로 dp를 각 위치에서의 최소 단어조각 개수로 설정해주고 문제를 .. 2021. 12. 22.
[프로그래머스] 실패율 (Python) https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr dict 활용 문제다 defaultdict 활용하면 좀 더 편하긴 함. - dict 정렬 참고 나의 풀이 def solution(N,stages): member = len(stages) counting = {} result = {} for stage in stages: if counting.get(stage): counting[stage] += 1 else: c.. 2021. 12. 21.
[프로그래머스] 지형 이동 (Python) https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다 dfs + heapq 알고리즘 1. 0, 0 에서 방문 가능한 곳 방문(height) 2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장 3. 이동 할 수 있는 곳 모두 이동 했을 .. 2021. 12. 20.
[프로그래머스] 지형 이동 (Python) https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다 dfs + heapq 알고리즘 1. 0, 0 에서 방문 가능한 곳 방문(height) 2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장 3. 이동 할 수 있는 곳 모두 이동 했을 .. 2021. 12. 20.
[프로그래머스] 동굴 탐험 (Python) https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr DFS에 조건을 잘 걸어야 하는 문제다 from collections import defaultdict import sys sys.setrecu.. 2021. 12. 9.
[프로그래머스] 퍼즐 조각 채우기 (Python) https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr dfs로 풀이했다. 알고리즘은 다음과 같다. 1. 게임보드의 모양을 구한다. 모양은 2차원 배열의 좌표 순서대로 찾으며, 방문하지 .. 2021. 11. 29.
python 알고리즘 정리 보호되어 있는 글 입니다. 2021. 11. 27.
[프로그래머스] 표 편집 (Python) https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 연결리스트를 활용해서 풀어야 하는 문제다 트리나 연결리스트를 활용하는 방법을 정리해놔야겠다. class Node: def __init__(self): self.prev = None self.next = None self.removed = False def solution(n, k, cmd): linkedList .. 2021. 11. 24.
[프로그래머스] N-Queen (Python) https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 다른 풀이를 참고했다. 아직 dfs를 짜는데 좀 익숙하지 않은 것 같다. 나중에 다시 살펴봐야겠다. import sys sys.setrecursionlimit(10**6) def dfs(queen,n,row): answer = 0 if n == row: return 1 for i in range(n): queen[row] = i for j in r.. 2021. 11. 23.
[프로그래머스] 하노이의 탑 (Python) https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 대표적인 재귀 문제다. 나의 풀이 import sys sys.setrecursionlimit(10**6) answer = [] def hanoi(n, from_col, to_col, assi_col): global answer if n == 1: answer.append([from_col, to_col]) return hanoi(n-1, .. 2021. 11. 23.
[프로그래머스] 스티커 모으기(2) (Python) https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr DP 유형의 문제다. 첫 번째 스티커를 찢는 경우, 찢지 않는 경우를 따져서 문제를 풀면 된다. 나의 풀이 def solution(sticker): if len(sticker) 2021. 11. 23.

티스토리툴바