lsh424

이 문제 포스팅할 생각이 없었는데, 생각보다 테스트케이스 5번과 10번에 대해 어려움을 겪는 사람들이 많은것 같아서 포스팅해보려구 합니다 ㅎㅎ (저도 5번, 10번 통과가 안되어서 뭐가 문제인지 헤멨어요 ㅜㅜ) programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 문제는 위와 같은 격자 배열에서, 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임입니다. 해당 블록이 사라지면 위에 있..

안녕하세요 오랜만에 알고리즘 풀이를 포스팅해보려 합니다 :) 오늘 포스팅할 문제는 카카오 blind recruitment에 나왔던 '자물쇠와 열쇠' 입니다. programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr [문제 설명] [제한사항 & 입출력 예] 이 문제는 2차원 배열을 잘 다룰 수 있는지 확인하는 문제로, 2차원 배열의 회전과 이동방법을 구현해서 완전탐색을 수행하면 풀리는 문제입니다. [접근 방식] 1. key가 회전 가능하기 때문에, key를 회전시키기 위한 rotat..

스트링 편집 거리(string edit distance) 알고리즘이란 두 문자열의 유사도를 측정하기 위해 사용되는 알고리즘으로 Levenshtein distance(LD)라고도 합니다. 스트링 편집 거리 알고리즘은 논문, 보고서 등의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용되어지는데요. 두 문자열의 유사도는 S: 원래 스트링 T: 비교 스트링이라 했을 때 S -> T로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용(최소 편집 횟수)을 구함으로써 판단합니다. (비용이 작게 나올수록 유사도가 큼) 만약 GUMBO라는 단어와 GAMBOL이라는 단어의 편집 거리를 구해보면, U -> A로 대치 (비용 +1), 맨 마지막에 L 추가 (비용 +1)로 편집 거리는 2가 되게 됩니다. (삽입, ..

오늘 풀어볼 문제는 코딩 테스트 고득점 Kit에 들어있는 DFS/BFS - 네트워크입니다. 개인적으로는 이 문제는 여행경로와는 다르게 레벨 3치고는 엄청 쉬운 편(?) 인 것 같습니다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 접근 방식: 1. 주어진 2차원 배열을 갖고 그래프를 만듭니다. 2. 탐색을 해야 하므로 BFS함수를 작성합니다. 모든 탐색이 끝난 후 그래프에서 방문한 노드를 삭제해 줍니다. 한 번의 ..

안녕하세요! 오늘은 메모이제이션(Memoization)에 대해 알아보려 합니다. 메모이제이션이 뭐냐?? 메모이제이션은 동일한 연산을 반복해야 할 때 이전에 연산한 값을 메모리에 미리 저장해 둠으로써 계산의 반복수행을 제거하여 프로그램 실행 속도를 향상시키는 기술입니다. 메모리에 저장해뒀다가 사용한다는 점에 있어서 캐싱의 범주에 속한다고 보면 될 것 같은데요. 메모이제이션은 어떤 함수의 인풋에 대한 아웃풋을 저장한다고 보시면 되고 (함수를 위한 캐싱), 우리가 보통 말하는 캐싱은 외부에서 들어오는 파일, 데이터를 저장해서 사용하는 용어로 생각하시면 될 것 같습니다. (혹시라도 틀린 부분이 있다면 꼭 댓글 남겨주세요!) 메모이제이션의 특징으로는, 보통 실행 속도가 빠른 알고리즘이 더 많은 메모리를 사용하듯이..

안녕하세요 ㅎㅎ 오늘은 알고리즘 문제풀이 시 가장 많이 사용하는 리스트(list), 집합(set), 딕셔너리(dictionary) 메서드의 시간 복잡도를 정리해보려 합니다. 본격적인 시작전에 왜 여러 자료형들의 메서드에 대한 시간 복잡도를 알아야 하는지 짚고 넘어갑시다! 보통 알고리즘 문제 풀때 리스트로 큐를 구현하시는 분들이 많으실 텐데요. 여기 큐를 pop하는 반복문을 돌려서 풀어야 하는 문제가 있다고 가정해 봅시다. 만약 리스로 큐를 구현했다면 다음과 같이 나타낼 수 있는데요. 리스트의 경우 마지막 원소를 pop하는 연산의 시간 복잡도는 O(1)이지만, 그 외의 원소를 pop할 경우 원소를 한 칸씩 당기기 때문에 시간 복잡도는 O(N)이 되게 됩니다. 결국 반복문과 중첩되니 전체적인 시간 복잡도는 ..

오늘은 프로그래머스의 코딩 테스트 고득점 Kit에 들어있는 DFS/BFS문제를 풀어보려 합니다. DFS/BFS는 코딩테스트에 자주 나오는 유형이니 4문제 다 풀어보면 좋을 것 같네요 오늘 풀어볼 문제는 여행경로입니다. programmers.co.kr/learn/courses/30/lessons/43164 처음 문제를 읽고 레벨3치고는 쉽네? 생각했는데, 테스트 케이스 1번 때문에 생각보다 애를 먹었네요. 그래서 아예 풀이를 갈아엎고 다시 풀었다는.. ㅜㅜ 저의 접근 방식은 이렇습니다. 1. 주어진 배열을 그래프로 만든다. (그래프 만드는 방법은 다양한 방법이 있겠지만, 저는 딕셔너리를 사용해서 인접 리스트 형식으로 만들었습니다.) 2. 큐를 만들고 (출발 노드, [경로]) 넣어준다. (처음엔 출발점이 무..

오늘은 기초적인 정렬 알고리즘을 알아보려 합니다. 대표적인 정렬 알고리즘으로는 선택 정렬, 버블 정렬(거품 정렬), 삽입 정렬, 셸 정렬(쉘 정렬), 병합 정렬, 퀵 정렬 등이 있는데요. 간단하게 선택 정렬, 버블 정렬, 삽입 정렬, 쉘 정렬 네 가지 정렬의 정의와 코드를 정리하고 각각의 알고리즘 실행 속도를 측정하여 성능을 비교해 보려 합니다. 1. 선택 정렬 주어진 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하고... 반복하는 정렬 방법 정렬 방법 1. 주어진 배열 중 최솟값을 찾는다. 2. 그 최솟값을 맨 앞의 원소와 교환한다. 3. (N-1)원소에 대해 1-2 방법 반복 소스코드(파이썬) def select_sort(a: list) ->..

알고리즘에는 시간복잡도라는 것이 있는데요. 코드를 다 작성하고 나서, 점근적 표기법인 빅오 표기법(Big-O notation)을 사용하여 대략적인 수식으로 시간복잡도를 나타낼 수 있습니다. 하지만, 만약 실제로 자신이 작성한 알고리즘이 얼마만큼의 시간이 걸리나 측정해보고 싶다면 어떻게 해야 할까요?? 방법은 정말 간단합니다. 여러 언어들이 시간 관련 프레임워크나 모듈을 제공 할텐데, 저는 파이썬 기준으로 설명드리겠습니다. 파이썬에는 time 모듈이 있는데요. 이 모듈의 time 메서드를 사용하시면 됩니다 ㅎㅎ (쉽죠??) 오늘 시간 측정을 해보기 위해 사용할 녀석은 정렬입니다. 정렬을 하는 방법에는 정말 다양한 방법이 존재 하는데요. 그래서 어떻게 알고리즘을 작성하느냐에 따라서 시간복잡도도 달라지게 됩니..

오늘은 딕셔너리에 대한 메소드를 정리해보려 합니다. 리스트, 튜플 딕셔너리로 변환 # 리스트 및 튜플 딕셔너리 변환 # 리스트 -> 딕셔너리 name_and_sex = [['LEE', 'M'], ['KIM', 'M'], ['RYU', 'F'], ['JEONG', 'F']] print(dict(name_and_sex)) #결과: {'LEE': 'M', 'KIM': 'M', 'RYU': 'F', 'JEONG': 'F'} # 튜플 -> 딕셔너리 name_and_sex = (('LEE', 'M'), ('KIM', 'M'), ('RYU', 'F'), ('JEONG', 'F')) print(dict(name_and_sex)) #결과: {'LEE': 'M', 'KIM': 'M', 'RYU': 'F', 'JEONG':..