문제에서 O(logN)으로 알고리즘을 설계하기를 요구했다 -> 선형탐색은 O(N) 이므로 부적합 데이터 셋이 오름차순으로 정렬되어 나오기 때문에 이진탐색을 선택함 mid 를 인덱스로 보고 array[mid] 값과 같으면 고정점이다 -> 이 값을 리턴 그렇지 않은 경우, array[mid] 실제 값이 더 크다면 반으로 뚝 자른 데이터들 중에서 오른쪽의 큰 값들을 탐색하면 된다. 더 작으면 왼쪽의 작은 값들을 탐색한다. 탐색 실패하면 None을 반환한다. n = int(input()) array = list(map(int, input())) def binary(array, start, end): if start > end: return None mid = (start + end) // 2 if array[m..
Algorithm (PS)
카드 정렬하기 !! 첫 시도: 가능한 순열 조합을 모두 계산하고 최솟값을 찾으려고 했으나 ㅋㅋㅋ 이 문제는 숨겨진 규칙이 있었으니.. 바로 가장 작은 카드 수 부터 더해가야 한다는 것이다. 그래서 heap 자료 구조를 이용하여 카드 들 중에서 카드 수가 작은 것을 빼내어 더하고, 이 더한값을 다시 heap에 넣어줘서 다시 더해지도록 한다 heapq 라이브러리 오랜만에 쓰는데 이 참에 파이썬 힙 자료구조 라이브러러 쓰는 방법도 확실하게 숙지해야겠따. import heapq n = int(input()) heap = [] for i in range(n): data = int(input()) heapq.heappush(heap,data) result = 0 while len(heap) != 1: one = h..
유형 : 구현 그치 딱 봐도 구현 문제이다.. 그런데 처음에 문제를 이해하는데 '균형 잡힌 괄호 문자열' 이랑 '올바른 괄호 문자열' 이 헷갈렸다 ㅋㅋㅋ 문제 풀이의 핵심은 무엇일까 재귀함수를 적절히 만들어 주어야 한다 !!!!! 당연한 소리지만 -_- 1. 균형 잡힌 괄호 문자열이 p의 어느 인덱스 까지인지 반환해주는 함수 구현 2. 현재 문자열이 올바르괄호 문자열인지 아닌지 구하는 함수 구현하기 3. 재귀 함수로 호출할 solution(p) 부분 구현하기 def balance(p): count = 0 for i in range(len(p)): if p[i] == '(': count += 1 else: count -= 1 if count == 0: return i def check(p): count =..
유형 : DFS/BFS 1. 바이러스의 종류는 1 ~ K 로, K 개이다. 이 문제를 풀 때 바이러스가 상 하 좌 우 로 번식한다고 하니 dfs / bfs로 이동하는걸 떠올렸다. 그런데 나는 처음에 풀 때 dfs라고 생각했다 그런데 계속 재귀 호출 에러가 났다. 이 문제는 bfs로 풀어야 한다. 왜...? 왜일까 bfs로 풀면 바이러스를 오름차순으로 정렬한다음에, 탐색할 수 있다 !!! 풀이를 정리해 보면 1. graph 를 생성 ! 정보를 받을 때 0초로 초기화 해서 저장한다. 이 문제의 특징은 s초가 지난 후의 x,y 좌표에 존재하는 바이러스 타입이 무엇인지 묻는 것이기 때문에 초 정보도 저장하는 것이 좋다. 2. 오름차순으로 바이러스 정렬 3. bfs 실행 # 경쟁적 전염 from collectio..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 유형 : 구현 + dfs 문제집에는 dfs로 분류되어 있었는데 구현 유형스러웠던 문제 ㅋㅋ 1. 벽을 설치한다 3개까지 -> board 2차원 배열 돌면서 board[i][j] == 0 이면 벽 설치 가능 2. 3개 다 설치했으면 바이러스를 퍼뜨려 본다. 바이러스 퍼뜨릴 때 재귀호출해서 상하좌우 이동한다. 3. 바이러스를 퍼뜨린 후 안전지대를 계산한다.그리고 원래 가지고 있던 최대 안전지대 값이랑 비교하..
https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 1. 원형을 선형으로 생각해보자 , weak의 길이를 두배로 늘려서 선형으로 생각한다. 2. 친구들을 배치해야한다. -> 파이썬에서는 순열 조합을 permutations 함수로 구현할 수 있다. 친구들을 배치하는 방법을 모두 구한다음에 완전탐색으로 필요한 친구의 최소 값을 구한다. dist의 길이가 1이상 8 이하이고 8! = 약 4만 정도이므로 완전탐색으로 풀..
문제 링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 도시에 있는 치킨집 중에서 최대 M 개를 골랐을 때, 도시의 치킨 거리를 구하는 문제이다. 치킨집들 중에서 M 개를 고르는 경우를 구할때 파이썬의 조합 라이브러리를 이용하면 이 문제는 생각보다 쉽게 풀 수 있다 (!) itertools의 combination을 사용한다 풀이 과정은 다음과 같다 1. data 입력을 받는다 2. for 문으로 data 입력 받을 ..
와 대박이다 이거 풀이의 핵심 알고리즘이 뭔지 아세여????놀랍게도 bfs임 와이파이 모양으로 확장하는거 왠지모르게 bfs는 와이파이 모양이 떠오른다.. 그리고 그렇게 생각하면 쉽게 이해된다) 자자 암튼 코드는 이렇다 # 1697 from collections import deque N, K = map(int,input().split()) MAX = 10 ** 5 dist = [0] * (MAX+1) def bfs(): q = deque() q.append(N) while q: x = q.popleft() if x == K: print(dist[x]) break for nx in (x-1, x+1, x*2): if 0
