분류 전체보기 (58) 썸네일형 리스트형 KMP 알고리즘 참고 블로그: https://pearlluck.tistory.com/581 [python] 문자열매칭. KMP 알고리즘 (백준16916, 백준1786) 단어검색 (문자열매칭) 요구사항 - 워드안에서 Ctrl+F하는 것 처럼, 검색한 단어들이 있는 모든 위치를 전부 알려줘! - 단어사전에 단어가 수만개, 문서길이가 수천개 - 문서는 띄어쓰기가 없거나 pearlluck.tistory.com KMP 알고리즘을 이해하는데 위 블로그를 참고했다. 한 문자열 M이 다른 문자열 N이랑 매치되거나 포함되는지 확인하는 알고리즘으로 쉽게 생각해볼 수 있는건 N에서 M의 시작점을 옮겨가며 매치되는지 확인하는 것이다. 하지만 이와 같은 방법으로는 O(MN)의 시간복잡도를 가진다. KMP 알고리즘을 사용하면 접두사와 접미사가 .. 프로그래머스 2단계 - n^2 배열자르기 (Python) 깃허브: https://github.com/MSIQOC/Programmers/blob/main/n%5E2%20%EB%B0%B0%EC%97%B4%EC%9E%90%EB%A5%B4%EA%B8%B0.py https://programmers.co.kr/learn/courses/30/lessons/87390# 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr 하아..... 구현은 제대로 했는데 테스트 케이스 12와 13에서 막혔었다. 처음에 예제로 나온 것들을 그.. 위상정렬 알고리즘 참고 블로그: https://velog.io/@younge/Python-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 [Python] 그래프 - 위상 정렬(Topology Sort) 알고리즘 구현하기 다음과 같은 조건을 가진 그래프라면 위상 정렬을 할 수 있다. 간선이 방향성을 가진 그래프여야 한다. 그래프 내부에 순환(Cycle)이 없어야 한다. 즉, 위상 정렬은 DAG(Direct Acyclic Graph)에 대해서만 velog.io 한마디로 "1을 하기 전에는 2를 할 수가 없다." 라는 일정한 순서가 정해져 있을 때 쓰기 편한 알고리즘이라고 한다. 위상정렬의 s.. defaultdict와 dict의 차이점은? 참고 블로그: https://emilkwak.github.io/defaultdict-rather-than-dict Python 딕셔너리(dict) 대신 쓰는 디폴트딕트(defaultdict) Python, Pandas를 Excel보다 사랑하는 직장인을 위한 블로그 emilkwak.github.io 코딩을 하다가 문득 그런 생각이 들었다. "왜 bfs를 위해 그래프를 생성할 때는 dict가 아닌 defaultdict를 사용하지?" 궁금증을 해결하기 위해 블로그를 검색해보았다. 그냥 딕셔너리는 처음에 딕셔너리에 없는 키를 생성하려면 dictionary = dict() if ?? not in dictionary: dictionary[??] = ... 이런식으로 if문으로 선언줘야만 한다. 하지만 default.. 백준 5052 - 전화번호 목록 (Python) https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 파이썬의 리스트에 전화번호를 String 형태로 append해주고 sort를 하면 길이가 짧은 순서대로 정렬이 됩니다. (예: [123, 12345, 253, 8897, 88958]) 리스트가 arr이라고 할 때 리스트를 처음부터 n-1까지 순회하며 arr[i]가 arr[i+1]의 접미사인지 확인하면 됩니다. (주의: 포함이 돼있는지 확인하는게 아니라 접미사인지 확인하는 것.. error during connect: This error may indicate that the docker daemon is not running.: 오류: error during connect: This error may indicate that the docker daemon is not running.: Get http://%2F%2F.%2Fpipe%2Fdocker_engine/v1.24/images/json: open //./pipe/docker_engine: The system cannot find the file specified. 도커 이미지를 생성하는데 나왔던 에러이다. https://chaelin1211.github.io/study/2021/04/01/docker-error.html [Error] Docker Run 시에 발생한 오류 - Chaelin's Blog 안녕하세요. 잘 되던 docker가 계속 오류가 발생해서 여러 방법을 해.. 프로그래머스 2단계 - [1차] 캐시 https://programmers.co.kr/learn/courses/30/lessons/17680 = cacheSize and cacheSize != 0: cache.pop(0) if cacheSize != 0: cache.append(temp) answer += 5 else: answer += 1 cache.pop(cache.index(temp)) cache.append(temp) return answer Colored by Color Scripter cs 백준 7453 - 합이 0인 네 정수 (Python) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 어떻게 푸는지 몰라서 검색을 해본 결과, a,b,c,d의 조합을 전부다 구하면 O(n^4)의 시간이 걸리기 때문에 a+b+c+d = 0을 변형해서 a+b = -(c+d)로 바꿔서 a와 b의 조합, 그리고 c와 d의 조합을 각각 O(n^2)의 시간에 구해서 풀면 되는 문제였다. 그리고 파이썬에서 제공해주는 dict()를 사용하면 dict는 해쉬 알고리즘을 이용해서 O(1)만에 원하.. 이전 1 2 3 4 5 6 ··· 8 다음
