본문 바로가기

알고리즘

[Lv2] 캐시(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/17680 도시들 간 순서가 있어야 함 & 자료구조의 사이즈를 알아야 함 - 초기 접근 방식 딕셔너리를 사용해서 key - 도시 이름, value - 해당 도시가 들어왔던 직전 순서를 저장. i번째 도시를 찾으려고 할 때, 이미 이전에 값이 들어온 적이 있으면 해당 value 값을 보고 value >= i - cacheSize + 1이면 cache hit으로 봤음 - 초기 접근 방식의 반례 cacheSize = 3, A B B B A 라 하면 , 마지막 A를 찾을 때 cache[A] = 0이 되어서 원래는 cache hit임에도 cache miss로 판정됨 => " 절대적인 순서가 필요한 게 아니라 캐시.. 더보기
[Lv2] 짝지어 제거하기(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 2. 풀이 과정 - stack을 사용해서 stack의 top 문자와 s[i]가 같으면 stack.pop()하고 아니면 stack.append()를 해가다가 최종 stack이 빈 stack이면 1을 리턴. - "붙어있어야 한다 + 붙어있는게 사라졌을 때, 새로운 짝이 생긴다 (b aa b -> bb) " -> .. 더보기
탐색 1. 순차탐색 - 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 - O(N) 2. 이진탐색 - 찾으려는 데이터와 중간 위치 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법 - 배열 내 데이터들이 정렬되어있어야 한다. - 확인하는 데이터의 개수가 절반씩 줄어든다는 점에서 O(logN) - 입력 데이터가 2000만을 넘어가면 이진 탐색으로 접근해보기 def binary_search (array,target,start,end): if start > end: return None mid = int((start + end) // 2) if array[mid] == target; return mid elif array[mid] > target: return binary_sear.. 더보기
[Lv2] 튜플(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 2. 구현 과정 1) 문제 내 정의 정리 * 튜플 - 어떤 순서를 따르는 요소들의 모임 - 중복 원소 가능 - 요소끼리의 순서 존재 - 원소 개수는 유한 * {}로 표현할 수 있는 집합 - 중복 원소가 없는 튜플의 원소들을 이용하여 {a1}, {a1,a2}, {a1,a2,a3..} 등으로 표현하는 집.. 더보기
vim 기본 명령어 정리 1. 이동 - h,j,k,l : h(좌), j(아래),k(위),l(우) - 0 : 줄의 맨 앞 - shift + 4($) : 줄의 맨 끝 - gg: 문서의 맨 처음 - shift + g(G) : 문서의 맨 끝 - w : 한 단어 앞 - b : 한 단어 뒤 - f : 한 페이지 다운 (page down) - u : 한 페이지 위(page up) 2. 수정 - dd : 한 줄 삭제(및 잘라내기) - dw : 한 단어 삭제 - dx : 한 글자 삭제 - yy : 한 줄 복사 - p : 붙여넣기 - cw: 한 단어 삭제 후 편집모드 - cx : 한 글자 삭제 후 편집모드 3. 검색 - /단어이름 : 단어 찾기 ( n : 다음 찾기, shift + n : 이전 찾기 ) - :%s/[찾을문자열]/[바꿀문자열]: 단.. 더보기
[2110] 공유기 설치(python) 1. 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 2. 구현 과정 - 읽을 수록 헷갈려서 문제를 이해하는데 오래걸렸다. 인접한 공유기의 최대거리? 가 어떤 의미인지를 빨리 이해하는 게 중요한 것 같다. - 맨 처음 완전 탐색으로 전체 N개 중 C개를 조합으로 구한 후, 가장 먼 거리를 구하려 했는데, 시간 초과가 난다. -> 파이썬 기준 2초 : 약 4000만 연산. nC2만 해도 2.. 더보기
[18111] 마인크래프트(python) 1. 문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 2. 구현 과정 - 완전 탐색으로 처음 풀었더니, 시간 초과가 났다. 500*500*256이 파이썬에선 1초가 넘어가는 걸 처음 알았다.. C++만 풀어왔던 나에겐 다소 충격(저 크기가 초과가 난다고?)이었고, 앞으로는 주의해서 풀어야 겠다. - 완전 탐색에 실패해서 그 다음 이분 탐색으로도 고민을 해 보았지만, 답을 구하려는게 최소-최대 높이가 아닌 최소 소요시간 이라는 점에서 정확.. 더보기
[Lv2] 거리두기 확인하기(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 2. 접근 방법 1) 모든 인원끼리의 맨해튼 거리가 2 이하인지 확인 => 각 .. 더보기

티스토리툴바