[Programmers] - 완주하지 못한 선수 (해시) with Python

문제 해시 - 완주하지 못한 선수 문제 분석하기 굉장히 쉬운 문제예요! 머리 예열 겸 코딩 테스트 연습을 다시 풀고 있어요. 아쉽게도 지원 언어가 C++, Java, JavaScript, Python 뿐이고 Swift는 없어서, 저의 경우 Java, JavaScript, Python으로 풀었는데 이 글에서는 Python의 코드로만 설명해볼게요 :) 그리고 이 글을 쓰게 된 이유는 가장 아래 문제 풀이 고민에서 말해볼게요! 두 가지 배열이 주어지고, 앞선 배열인 participants는 반드시 뒤의 배열인 completion 보다 요소 1개를 더 가지고 있고 이 요소를 찾는 문제예요. 가장 단순하게는 participants를 for문으로 돌고, completion을 그 안에서 순회하면서 매칭 되는지 여부를..
알고리즘 학습/프로그래머스 2022. 3. 23. 11:20
Python, Swift로 { 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 } 구현하기

기본 정렬 구현하기 오랜만에 알고리즘을 보며 기본 정렬(버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬)을 구현해봤어요. 알고리즘 풀이를 위해 제가 사용하는 언어인 Python과 iOS 개발을 위해 사용하는 언어인 Swift로 각각 구현했어요. 각 정렬의 시간복잡도나 자세한 정렬 알고리즘을 위한 글이 아니라, 단순히 기본 정렬 알고리즘들을 구현하고 싶은 분들을 위해 코드를 공유해요 :) 제가 구현할 때 했던 생각 정도만 설명으로 추가할게요. 입력되는 배열이 빈 배열인 상황 등은 고려하지 않은 코드예요. 혹시 빈 배열의 입력이 가능한 상황이라면 추가적인 처리가 필요해요 :) 혹시 코드에 미흡한 점이 있거나 더 좋은 코드로 개선 가능한 방향이 있다면 피드백 부탁드려요! 버블 정렬(Bubble So..
알고리즘 학습/알고리즘 개념 2022. 3. 14. 22:34
[Programmers] - 모음사전 (위클리 챌린지) with Python

문제 위클리 챌린지 - 모음사전 문제 분석하기 길이 5 이하이므로 사전을 전부 만든 후 검색을 해도 속도에 문제가 없어요. 참고로 사전의 총 길이는 5 + 5^2 + 5^3 + 5^4 + 5^5 가 될 거예요 :) 이 사전을 구현하기 위해 재귀 함수를 사용할 수 있겠지만 파이썬의 모듈인 product를 사용하면 보다 손쉽게 구현할 수 있어요. Product 사용하기 Product는 itertools에서 사용할 수 있어요. itertools에는 Permutation, Combination이 있는데 이것은 순열과 조합이므로 중복을 허락하지 않아요. 이 문제에서는 중복이 필요하기 때문에 Product를 사용해요. 사실 Product는 이름 그대로 product 곱을 위한 모듈이에요. 예시를 살펴볼게요! ite..
알고리즘 학습/프로그래머스 2022. 2. 17. 22:51
[백준 알고리즘] - 트리 순회(1991번) with Swift

문제 풀이 과정의 고민 시뮬레이션으로 문자열을 직접 탐색하는 것도 방법일 수 있다고 생각했어요. DFS처럼 탐색하지만 탐색 조건을 변경하면서요. 하지만 그런 방식은 상황이 너무 복잡해지고 작은 디테일에서 오류가 쉽게 발생할 수 있다고 생각해서 노드를 직접 만드는 것으로 생각했어요. 이 글에서 전위, 중위, 후위 순회에 대한 설명을 하진 않을 계획이에요. 다만, 각 탐색 메서드에서 명백하게 출력의 우선순위를 보여주는 것이 중요하다고 생각해요. 전위는 말 그대로 부모 노드의 데이터를 먼저 보여주는 것, 중위는 왼쪽 노드부터 탐색한 후 부모 노드의 값을 출력해주고 오른쪽 노드를 탐색하는 것처럼이요. 언어를 조금 고민했어요. 파이썬 풀이도 추가로 올릴 예정이지만, 아무래도 Node 클래스를 이용해 풀이하는 데에..
알고리즘 학습/백준 알고리즘 2022. 1. 16. 11:02
[백준 알고리즘] - 친구 네트워크 (4195번) with Union Find 알고리즘

문제 풀이 과정의 고민 이 문제는 단순한 구현 문제가 아니라 Union Find의 개념을 이해해야 풀기 쉬웠어요. Union Find의 개념을 간단히 설명해볼게요. 키 포인트는 노드 간에 부모 - 자식 관계를 만드는 거예요. 즉, 같은 그룹인지 확인하는 방법을 같은 부모를 가지고 있는지 확인하는 것으로 대신하는 거죠. 쉽게 생각하면 같은 그룹에 속할 경우 그 요소들에 그룹 번호를 부여한다고 볼 수도 있는데, 그 그룹 번호가 새롭게 생성되는 것이 아닌 특정 요소를 부모로 해서 그 요소 자체를 그룹 번호로 설정하는 거예요. 예시를 통해 살펴볼게요. 아래와 같이 4개의 노드가 존재한다고 가정해요. 이 상태에서는 어떤 연결도 없기 때문에 각 노드의 부모는 자기 자신이 될 거예요. 노드 1 2 3 4 부모 1 2..
알고리즘 학습/백준 알고리즘 2022. 1. 3. 11:24
[백준 알고리즘] - 프린터 큐 (1966번) with Python

문제 풀이 과정의 고민 출력할 문서의 위치를 어떻게 이동시킬지 고민했어요. 방법은 다양할 수 있는데, 출력 위치가 0번 인덱스로 고정되어 있기 때문에 원형 큐처럼 인덱스를 따라 돌게 만들기로 했어요. enumerate를 통해 인덱스와 중요도를 튜플로 묶으면 생각하기 편하긴 하지만 자료의 수가 늘어날수록 성능에 영향을 미치게 되어 정수 하나의 인덱스로 관리하는 게 더 낫다고 판단했어요. 파이썬에서 제공하는 기본 리스트 자료구조의 경우 내부적으로 더블 링크드 리스트이지만 사용 시 스택처럼 작동하기 때문에 pop(0)을 사용하는 것을 피하려고 했어요. 인덱스 1번부터 요소가 존재한다면 전부 시프팅이 일어나기 때문이에요. 그래서 대안으로 생각한 것은 주어진 자료구조를 reverse 해 pop(0)가 아닌 pop..
알고리즘 학습/백준 알고리즘 2022. 1. 2. 11:05
[Leet Code] 819. Most Common Word(가장 흔한 단어)

책에 나온 문제에 추가적인 조건을 더해야 문제를 풀 수 있어요. case-insensitive란 대소문자를 구별하지 않는다는 뜻이에요. 그리고 결과는 항상 소문자로 반환해요. 📝 풀이 책의 풀이와 달라요. 제가 생각하기에 더 빠른 속도의 알고리즘이에요(O(N^2) -> O(N)). 문제의 조건에 위배되는 입력을 할 경우 무한 루프에 빠질 수 있어요. 문제의 조건에 맞는 입력을 했다는 가정하에 풀이했어요. def my_solution(paragraph: str, banned: [str]) -> str: from collections import Counter import re banned_dict = dict(Counter(banned)) paragraph_dict = Counter([word for wo..
알고리즘 학습/파이썬 알고리즘 인터뷰 2021. 12. 9. 11:50
[Leet Code] 937. Reorder Log Files(로그 파일 재정렬)

로그를 재정렬하는 문제예요. 현업 프로젝트 코드에서도 로그는 거의 모든 부분에서 수집하기 때문에 그걸 처리하는 센스를 보는 문제라고 할 수 있어요. 난이도가 쉬운 문제인데 책에서 주어진 정보가 매우 부족하고 조건이 부실해서 책을 기준으로 문제를 풀었더니 예외처리에 시간이 오래 걸렸어요. 에서 제공하는 문제 정보는 항상 조건에 대한 정보가 부실하다고 느껴요. 반례의 상황 등에서요. 오히려 풀이를 보면서 "이렇게 풀이하는 걸 보면 문제 조건이 이렇게 제한될 수밖에 없구나"라고 판단했어요. 에 나오는 풀이 상으로는 숫자 로그는 숫자만 나오고, 문자 로그는 문자만 나와요. 혼용될 수 없지만 조건에 없었어요(그래도 덕분에 혼용되는 조건이라는 발전된 문제를 생각해볼 수 있었고 아래 고민 섹션에 코드를 올렸어요). ..
알고리즘 학습/파이썬 알고리즘 인터뷰 2021. 12. 8. 16:15
1 2 3 4 ··· 22