🌷맹이나라🌻

프로그래머스 17685 자동완성 문제 링크 1. 설계 로직 문제를 보자마자 트라이 자료구조가 생각났습니다. 트라이 구조로 만들 경우 ["go", "gone", "guild"]가 주어질 때 이런 식으로 생기게 됩니다. 그리고, 해당 문자가 존재하는지 여부를 확인하기 위해 trie.search("go") = True, trie.search("gone") = True, trie.search("guild") = True, trie.search("gon") = False와 같이 문자가 끝나는 지점에만 True값을 넣어주는 것과 같이 문자인지 아닌지 넣어주면 됩니다. 일단 문자열을 다 담아줍니다. 이 때 {'g': [1, {'o': [1, ...]}]}과 같이 dict의 key는 문자,..

1. 문제 https://www.acmicpc.net/problem/1005 2. 접근 방법 위상정렬 알고리즘을 사용하면됩니당 최근에 위상정렬을 알게되어 ^-^.. (그래프 문제 너무 어려워영ㅇ엉어엉엉) 풀어보았습니다. 여튼 위상 정렬 알고리즘은 다음과 같은 로직을 가집니다. 진입차수가 0인 노드를 큐에 넣는다(시작점) 큐가 빌 때까지 다음의 과정을 반복한다. 2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 문제는 도착 지점까지 제일 오래 걸리는 시간을 찾으면 되므로, answer를 이용해서 각 노드까지 도착하는 최대 시간을 계속 갱신해줍니다. 그러다가 해당 노드의 진입차수가 0이 될 경우, 그 때 queue에 해당..

문제 링크 1. 설계 로직 N의 범위가 1~16이라 완전탐색 문제라고 생각했습니다. 각각의 arr들을 이진수로 변환합니다. 이진수로 변환된 맵을 하나씩 확인하면서 맵 합칩니다. 0: 공백, 1: 벽 두가지 맵 중 하나라도 1이면 1 두가지 맵 모두 0이면 0 0인 경우 공백으로 나타내고, 1인경우 #으로 나타내어 출력합니다. 시간복잡도: O(N^2) 2. 코드 def solution(n, arr1, arr2): def trans_map(arr): new_arr = [] for i in range(n): val = &#39;&#39;.join(bin(arr[i]))[2:] while len(val) < n: val = &#39;0&#39; + val new_arr.append(val) return new_..

문제 링크 1. 설계 로직 "AB"와 "ab"는 같은 문자 취급하기 때문에, str1과 str2를 모두 소문자로 만들어서 시작했습니다. 각 문자를 2개씩 쪼개서 dict형으로 만들어 key: &#39;문자 이름&#39;, value: &#39;문자가 등장한 갯수&#39;를 넣어줍니다. 이 때, 문자의 형식이 올바르지 않은 경우는 제외해줍니다. 각각의 key값들이 등장한 문자이기 때문에, set 메서드를 이용하여 교집합(&)과 합집합(|)을 만들어줍니다. 교집합 요소의 경우 str1, str2 중 더 적은 count 값을 가지므로, min값을 분자에 더해줍니다 합집합 요소의 경우 str1, str2 중 등장한 집합에서의 count값을 가지는데, 이 때 두 집합 모두에서 등장한 경우에는 더 많은 count ..

문제 링크 1. 설계 로직 시간은 모두 분(min)을 기준으로 바꾸어 문제풀이를 진행했습니다. 먼저, 가능한 셔틀 시간을 모두 shuttles리스트에 담아줍니다. (셔틀 운행 횟수, 간격 고려) 크루들이 대기열에 오는 시간을 모두 리스트에 담아주고, 정렬해줍니다. 일단 모든 크루를 셔틀에 태워봅니다. 만차의 기준: 마지막 셔틀 버스가 만차인지 아닌지. 만차라면, 제일 뒷 시간인 사람보다 1분 빠른 시간이 답이 됩니다. 만차가 아닌 경우, 마지막 셔틀 버스 시간이 답이 됩니다. (셔틀 도착 시간까지 탈 수 있으므로) 시간복잡도: O(N+M) 각 버스에 해당 승객이 탈 수 있는지 없는지 확인해야하므로 O(N+M)입니다. (N = 버스 수, M = 승객 수) 2. 코드 def solution(n, t, m, ..

1. 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 접근 방법 그냥 sort인데 N의 갯수가 1,000,000이므로 O(N^2)인 것은 사용하면 안됩니다요~! 그래서 그냥 sys를 사용해서 입력을 빨리 받아서 내장 소트 사용했습니다요 처음에 입력받을 때 int를 안해줬더니 3 -2 -1 0 테케를 넣었을 때 -1 -2 0 으로 뜨더라구용 ㅋㅋㅋㅋㅋㅋ ㅠ 어이없어서 티스토리에 글쓰러 왔습니다~! 3. 코드 python i..

문제 링크 1. 설계 로직 주어진 board를 모두 순회한다.(바로 지우지 않는 이유 : 겹치는 경우가 존재하므로) 이 때, 현재 좌표 (x, y)를 기준으로 오른쪽(x+1, y), 아래(x, y+1), 오른쪽 아래(x+1, y+1)가 모두 같은 모양이라면 -> 추후에 지워질 블록이기 때문에 리스트에 (x, y)를 담아놓는다. 순회 후 지워질 블록 리스트를 하나씩 확인하며 오른쪽, 아래, 오른쪽 아래 블록까지 모두 지운다. 지우면서 이 블록이 겹치는 블록인지 확인하고, 겹치지 않는 블록이라면 count +1, 겹치는 블록인데 이미 지워진 블록이라면 pass한다. 블록을 지운 후 위에 있는 블록이 아래로 떨어져 빈 공간을 채운다. 1-3의 로직을 지울 수 있는 블록이 존재하지 않을 때까지 반복한다. 시간복..

모르고리즘을 올리다가 이런 오류를 만났습니다. 짧은 영어로 읽어보자면 "index.lock" file이 있다. 그리구 다른 프로세스가 동작하고 있다. 요런 말이자나여 ? 그래두 궁금하니까 찾아봤더니 다른 프로세스가 동작하고 있어서 index.lock파일에 의해 락이 걸린 상황이라네여 ! 해결방법은 간단했지만 그래두 오랜만에 기록하고 싶어서 왔슴미다 ~! 해당 .git 폴더로 가셔서 index.lock파일만 지워주면 됩니다 ~! rm -f index.lock저는 쫄보라 하나하나씩 확인해가면서 했습니다 ~! 제 폴더 구조는 아래와 같이 molgorithm2(myoung)이라는 폴더 내부에 .git폴더가 숨겨져있구용 그래서 cd .git/으로 이동 후 index.lock이 존재하는 것을 확인하여 rm -f i..

프로그래머스 17684 압축 문제 링크 1. 설계 로직 먼저 dict에 A-Z를 담아줍니다. 주어진 msg를 하나씩 확인하여 해당 문자(혹은 문자열)가 존재하면 그 다음에 등장하는 문자를 하나 붙여줍니다. 이 때 기존 문자에 다음 문자를 붙인 문자열을 new_word라고 하고, 해당 new_word가 또 존재하면 해당 문자열 뒤의 문자를 하나 더 붙여 new_word를 갱신합니다. 만약 new_word가 dict에 존재하지 않을 경우 dict에 담아주고, 그 다음 문자로 넘어가 2번을 반복합니다. 시간복잡도: O(N^2) 문자열이 dict에 존재하는지 확인하기 전 문자열을 만들 때 시간 복잡도가 O(N^2)이고, 확인하는 과정은 O(1)이라서 O(N^2)이라고 생각했습니다. 이라고 생각했는데 승환님과 계..

1. 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 2. 접근 방법 사실 3장만 뽑으면 되는거라 3중 for문 써도 되지만, 그냥 함수 만들어서 조합 만들 듯 합을 더해줬습니다. 3. 코드 python def solution(): N, M = map(int, input().split()) nums = list(map(int, input().split())) answer = 0 def make_sum(sta..