본문 바로가기

All Post269

#1 python 메모리 구조 최근 기술면접에서 메모리 영역에 대한 질문을 받았는데, 예전 학부 수업때 잘 공부했고 당연히 알고 있다고 생각했는데 당황 + 갑자기 머리 하얘짐 으로 대답을 제대로 못했다. 충격을 받고 다시 정리를 해야겠다는 생각이 들었다. 코드 영역 : 실행할 프로그램의 코드가 저장됨 데이터 영역 : 전역변수와 정적변수가 저장됨 힙 영역 : 사용자가 동적으로 할당하는 변수나 메소드가 저장된다. C 에서는 malloc 스택 영역: 지역변수나 매개변수가 저장된다. python에서는 Python memory manager 에 의해 메모리가 관리된다. Python 메모리 할당과 관리에 대해 기초적인 것을 다음 포스팅에서 정리 해 보겠다. 2021.12.29 - [Comuter Science] - #2 python의 메모리 할.. 2021. 12. 29.
제곱수, 2의 n 제곱인지 확인 제곱수인지 확인 def isSquare(n): return int(n ** 0.5) ** 2 == n 2의 n 제곱인지 확인 def isPowerOf2(n): return (n&(n-1))==0 2의 제곱은 비트로 나타낼 때 맨 왼쪽 비트만 1이고, n이 2의 제곱이라면 n-1 은 맨 왼쪽 비트가 0이고 그 오른쪽 비트들은 모두 1이게 됨. 따라서 n이 2의 거듭제곱이라면 n과 n-1을 and 연산 했을 때 0이 나오게 됨. 2021. 12. 29.
해시 테이블 해시 테이블은 매우 빠른 삽입, 삭제, 탐색 연산을 제공하는 자료구조 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.
단방향 연결 리스트 구현 class Node: # 단방향 연결 리스트 위한 노드 def __init__(self,key = None): self.key = key self.next = None def __str__(self): return str(self.key) # v = Node() # print(v.key) # key값 출력 # print(v) -> print(v.__str__()) 와 같음 ''' 보통 이렇게 하지 않음 (매번 변수 선언) a = Node(3) b = Node(9) c = Node(-1) a.next = b b.next = c ''' class SinglyLinkedList: def __init__(self): self.head = None self.size = 0 def pushFront(self,key.. 2021. 12. 13.
스택 큐 자료구조 구현 class Stack: def __init__(self): self.items = [] # 데이터 저장을 위한 리스트 준비 def push(self, val): self.items.append(val) def pop(self): try: return self.items.pop() except IndexError: # IndexError가 발생했다면 print("Stack is empty") def top(self): # 맨 위의 값을 출력 try: return self.items[-1] except IndexError: print("Stack is empty") def __len__(self): # len()로 호출하면 stack의 item 수 반환 return len(self.items) class Q.. 2021. 12. 12.
[프로그래머스] 동굴 탐험 (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.
자료구조와 알고리즘 자료구조와 알고리즘에 대해 알아보자 그 동안 자료구조와 알고리즘을 막연하게 생각해왔는데 본질적으로 알아 봐야겠다 https://www.youtube.com/watch?v=M2mcJvmYpWY 한국외대 신창수 교수님의 자료를 보고 정리해볼까 한다. 자료구조란 어떤 data를 저장하기 위한 구조인데 이는 저장공간(memory) + 연산(읽기, 쓰기, 삽입, 삭제, 탐색) 의 구조를 가지고 있다. 이런 자료구조를 활용해 어떤 입력이 들어왔을 때 이를 유한한 횟수의 연산들을 통해 정답을 출력하는 논리적인 절차를 알고리즘이다. 자료구조의 예: 1. 변수(variable) a = 5 (쓰기연산) print(a) (읽기연산) 변수에는 값이 하나만 들어가기 때문에 삽입, 삭제, 탐색은 의미가 없다 python 내부에서.. 2021. 12. 8.
[프로그래머스] 퍼즐 조각 채우기 (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.