본문 바로가기
728x90

분류 전체보기115

[알고리즘_카카오] 다익스트라 - 합승 택시 요금 [알고리즘_카카오] 다익스트라 - 합승 택시 요금 다익스트라 최단 경로 알고리즘 동작 과정 1. 출발 노드 설정 2. 최단 거리 테이블을 초기화 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5. 3, 4번 과정 반복 처음에 이해가 안갔던 포인트가 방문한 노드는 그 노드까지의 최소 비용이 이미 결정된 상태라는 것이었다. '다른 길로 둘러서 왔을 때 더 비용이 적으면 어떡하지?' 라는 생각을 했는데, 다시 생각해보면 새롭게 방문하게 되는 노드는 방문하지 않은 노드 중 가장 비용이 적은 노드라는 사실에서 그 명제가 참이 된다. 즉 다른 길로 돌아가는 것 자체의 첫발(첫 간선)부터 비용이 새롭게 방문하게 되는 노.. 2021. 12. 26.
[알고리즘_카카오 인턴] 거리두기 확인하기_bfs [알고리즘_카카오 인턴] 거리두기 확인하기_bfs 정말 오랜 시간이 걸렸다..... bfs로 풀었는데 내 방식대로 해서 답을 맞히는데 오랜시간이 걸렸다. 처음에 for문을 두 번 돌면서 place[i][j] =="P" 즉 사람일 때를 찾아 bfs를 실행하고나서 for문 둘 다 break하고 나머지 for문을 돌지 않는 방법이 떠오르지 않았다. 결국 이를 check라는 함수로 따로 빼서 해결했다. 그랬더니 반쯤 맞았다. # 첫 시도 def solution(places): answer = [] visited = [[0] * (5) for _ in range(5)] for place in places: # 5번 for i in range(5): for j in range(5): if place[i][j] ==.. 2021. 12. 21.
[백준_1987] 알파벳(bfs, set, bactracking) [백준_1987] 알파벳(bfs, set, bactracking) 고생한 문제다..... 처음에 dfs로 시도했다가 시간 초과가 떴다. 첫 풀이 passed는 지나간 알파벳을 문자열로 저장했고 visited는 전체 행렬에 trace를 알 수 있도록 했었다. 둘 다 시간초과 import sys input = sys.stdin.readline dx = [1,-1,0,0] dy = [0,0,1,-1] def bt(x,y,lengg): global leng leng = max(leng, lengg) for i in range(4): nx, ny = x+dx[i], y+dy[i] if 0 2021. 12. 20.
[면접 질문] 기타 [면접 질문] 기타 1바이트은 몇 바이트? 8바이트 (예전엔 4, 6바이트 인 컴퓨터도 있었음) 1픽셀은 몇 바이트? 채널이 몇개냐에 따라 다름 3개인 경우 RGB 각각 2^8이므로 24비트 = 3바이트이다. Stack과 Queue의 차이? Stack은 LIFO. Queue는 FIFO(queue.popleft 생각해보면 간단) Binary Tree의 시간 복잡도는? O(n) balanced tree인 경우 O(logn) DNS의 역할? 호스트의 도메인 이름을 호스트의 네트워크 주소(IP)로 변경 하는 것. 사람은 숫자보다 문자를 더 잘 기억 HTTPS와 HTTP의 차이? HTTP: Hyper Text Transfer Protocol HTTPS: Hyper Text Transfer Protocol Secu.. 2021. 12. 19.
[면접 준비] OS [면접 준비] OS 운영체제를 사용하는 목적? 1) 제멋대로 동작하는 응용프로그램들이 하드웨어를 잘못 사용하는 것을 막음 2) 응용프로그램들이 단순하고 균일한 메커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치들을 조작할 수 있도록 함 -> 두 가지 목표 달성을 위해 추상화를 이용 1) 파일 : 입출력장치의 추상화 2) 가상 메모리: 메인 메모리와 디스크, 입출력장치의 추상화 3) 프로세스: 프로세서, 메인 메모리, 입출력장치 모두의 추상화 프로세스란? 메모리에 올라가서 실행중인 프로그램이 프로세스 운영체제는 시스템에서 이 한 개의 프로그램만 실행되는 것 같은 착각에 빠지도록 해준다. 즉 프로그램이 프로세서, 메인 메모리, 입출력장치를 모두 독차지하고 있는 것처럼 보인다. 이 것은 프로세스라고 .. 2021. 12. 19.
[알고리즘_카카오 인턴] 보석 쇼핑 (파이썬)_투포인터 [알고리즘_카카오 인턴] 보석 쇼핑 (파이썬)_투포인터 무넺 자체가 정확성과 효율성 테스트이면 단순하게 안풀린다는 얘기... gems 배열의 크기가 100,000 이하여야하기 때문에 꽤 빡센 조건이다. 연속된 구간에 대한 문제이므로 투포인터를 이용할 수 있는 문제. 투포인터를 이용한 첫 시도 def solution(gems): answer = [] answer1 = [] tmp = [] n = len(gems) m = len(set(gems)) end = 0 # index minv = 100000 for start in range(len(gems)): while len(set(gems[start:end+1])) < m and end < n: end += 1 if len(set(gems[start:end+.. 2021. 12. 19.
728x90

티스토리툴바