소신의 블로그생활

1. 문제 가사 배열이 주어지고, query가 와일드카드 "?" 와 주어졌을 때, query와 일치하는 단어 수를 반환 2. 입력 # SET - 1 words = ["frodo", "front", "frost", "frozen", "frame", "kakao"] queries = ["fro??", "????o", "fr???", "fro???", "pro?"] 3. 출력 # SET - 1 result = [3, 2, 4, 1, 0] 4. 풀이 여차하면 for문 여러번써서 풀수있지만, 그러면 효율성 테스트에서 시간초과가 난다. 최악의 경우 10000 * 10000 을 해야되기 때문 따라서 이는 bisect를 활용해 풀면되는데, 1. word를 앞으로, 뒤집어서 배열 2개를 만들고 정렬 (순서대로 나오게) ..

1. 문제 N개 집의 위치가 배열로 주어졌을 때, 공유기를 C개만큼 설치할 경우, 공유기 사이의 거리가 최대를 출력 2. 입력 # SET - 1 5 3 1 2 8 4 9 3. 출력 # SET - 1 3 4. 풀이 떡볶이 떡을 자르는 문제처럼 공유기 사이의 거리를 이진탐색으로 찾아서 푸는 문제 공유기 사이의 거리가 최소거리 1부터 배열의 N-1번째에서 0번째를 뺀 값이 최대거리일 때, 그 값의 가운데를 최소거리로 잡고 1번째부터 하나씩 공유기를 설치해나감 (0번째는 이미 설치했다고 가정) 설치한 공유기의 수가 C를 만족시키면 GAP을 늘리고 (binary search 오른쪽부분) 공유기의 개수가 딸리면 GAP을 줄임 (binary search 왼쪽 부분) 5. 코드 import sys wr = sys.st..

1. 문제 array가 정렬되어 주어질 때, index와 array[index]의 값이 같으면 출력, 하나도 없다면 -1을 출력 2. 입력 # SET - 1 N = 5 arr = [-15, -6, 1, 3, 7] SET - 2 N = 7 arr = [-15, -4, 2, 8, 9, 13, 15] SET - 3 N = 7 arr = [-15, -4, 3, 8, 9, 13, 15] 3. 출력 # SET - 1 3 # SET - 2 2 # SET - 3 -1 4. 풀이 이진탐색 패키지를 쓰지않고, 이진탐색을 구현해야 하는 문제 for문으로 N만큼 하나씩 돌면서 값이랑 index랑 같은지 찾는방법도 있지만, 그것은 시간 복잡도가 O(N)이므로 패스 O(logN)으로 풀려면 이진탐색을 사용해야한다. array를 ..

1. 문제 안테나를 집 위에 설치할 때, 어디에 설치해야 각 집까지의 거리가 최소가 되겠는가? N은 ~20만 (완전탐색 X) 2. 입력 # SET - 1 4 5 1 7 9 3. 출력 # SET - 1 5 4. 풀이 집을 정렬하고, 집의 수 N에서 1을 빼고 (가운데 왼쪽을 표현하기 위해) 2로 나눈 뒤 해당 index를 출력하면 끝 짝수일 경우 1 2 5 9 -> 1번째 (2)가 최소 1+0+3+7 = 11 / (5) 4+3+0+4 = 11 홀수일 경우 1 2 3 4 7 -> 2번째 (3)이 최소 2+1+0+1+3 = 7 / (4)==(2) 5. 코드 N = int(input()) houses = list(map(int, input().split())) def sol(N, houses): print(so..

1. 문제 오른쪽 하단 끝으로 이동하기 2. 입력 # SET - 1 board = [[0,0,0,1,1],[0,0,0,1,0],[0,1,0,1,1],[1,1,0,0,1],[0,0,0,0,0]] 3. 출력 # SET - 1 result = 7 4. 풀이 DFS로 풀려고했는데 visited 처리를 제대로 못했다. visited처리를 하면서 혼돈에 빠져서 결국 해결못하고 GG DFS로 하면 모든 경로를 다 탐색하므로 오래걸리고 안될 수 밖에;; 판단을 잘못했다. BFS로 풀면, 그 전에 방문한곳은 cost가 무조건 낮은걸로 채워져있을테니 결국 N, N에 도착하는 cost는 최저 코스트가 될 것이다. 그러므로, 다음 이동할 position을 미리 계산해서 리스트에 담은 뒤, 그것을 큐에 cost와 함께 넣어주면..

1. 문제 땅의 크기 N 각 영역별로 나라가 존재하고 최소 인구 이동, 최대 인구 이동 범위가 L, R 사이 일 때 인구 이동이 몇번 일어나는가? 2. 입력 # SET - 1 2 20 50 50 30 20 40 # SET - 2 2 40 50 50 30 20 40 # SET - 3 2 20 50 50 30 30 40 # SET - 4 3 5 10 10 15 20 20 30 25 40 22 10 # SET - 5 4 10 50 10 100 20 90 80 100 60 70 70 20 30 40 50 20 100 10 3. 출력 # SET - 1 1 # SET - 2 0 # SET - 3 1 # SET - 4 2 # SET - 5 3 4. 풀이 bfs로 확산하는것만 이해하고 같은 그룹으로 묶는거를 까먹었다보..

1. 문제 T는 선생님 S는 학생 벽(W) 3개를 세워서 감시를 피할 수 있으면 YES를 출력, 아니면 NO 출력 2. 입력 # SET - 1 5 X S X X T T X S X X X X X X X X T X X X X X T X X # SET -2 4 S S S T X X X X X X X X T T T X 3. 출력 # SET - 1 YES # SET - 2 NO 4. 풀이 N이 3~6으로 맵 크기가 작기 때문에 완전탐색도 가능하다. 선생님의 감시를 피할 수 있는지 확인하는 부분이 조금 다를 뿐 벽을 세우면서 (dfs를 돌리면서) 벽이 3개일 때, 선생님의 감시를 피할 수 있는지 체크 여기서 가능하다면 최종적으로 True를 들고가면된다. 지금은 풀이가 잘 이해되는데 다른거 공부하다가 까먹을까봐 기록..

1. 문제 숫자가 N만큼 주어지고 연산자가 N-1개 만큼 주어졌을 대 최대값, 최소값을 출력하라. 연산자 순서는 + - * / 순이다. 나눌땐 몫만 취할 것 (음수를 나눌 경우 양수로 나눈 뒤 - 붙임) 2. 입력 # SET - 1 2 5 6 0 0 1 0 # SET - 2 3 3 4 5 1 0 1 0 # SET - 3 6 1 2 3 4 5 6 2 1 1 1 3. 출력 # SET - 1 30 30 # SET - 2 35 17 # SET -3 54 -24 4. 풀이 예전에 풀때는 완전탐색으로 permutation을 사용해 풀었지만, 조금 공부하고나니 DFS로 푸는 방법이 보였다. 마치 친구와 당구를 하면서, 맨날 당구비를 내다보니 길이보이는 느낌이랄까.. 근데 중요한건 아직 시야가 편협하다는 것 max값을..

1. 문제 벽을 3개 지어서 0을 최대한 많이 만들어라. virus는 상하좌우로 퍼짐 2. 입력 # SET - 1 N, M = 7, 7 maps = '''2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0''' # SET - 2 N, M = 4, 6 maps = '''0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2''' # SET - 3 N, M = 8, 8 maps = '''2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 ..

1. 문제 친구들을 활용해 외벽 점검을 하자. 점검이 필요한 외벽의 번호 오름차순으로 주어진다. 각 친구들은 점검할 수 있는 길이가 정해져있다. 친구들을 최소한으로 사용해서 외벽 점검을 마쳐라. 2. 입력 # SET - 1 n = 12 weak = [1, 5, 6, 10] dist = [1, 2, 3, 4] # SET - 2 n = 12 weak = [1, 3, 4, 9, 10] dist = [3, 5, 7] # SET - 3 n = 50 weak = [1] dist = [6] # SET - 4 n = 200 weak = [0, 10, 50, 80, 120, 160] dist = [1, 10, 5, 40, 30] # SET - 5 n = 30 weak = [0, 3, 11, 21] dist = [10, ..