짧은코딩

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 내 풀이(큐를 생각 못했다ㅠㅠ) from collections import deque n, m = map(int, input().split()) ary = [] for i in range(n): ary.append(list(map(int, input()))) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs(x,y): q = deque() q.append((x,y)) while q: x, y = ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 내 풀이(맞음) def binary_search(array, target, start, end): mid = (start + end) // 2 if start > end: return None if target == array[mid]: return mid elif target < array[mid]: return binary_search(array, target, ..

이진 탐색은 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 순차 탐색 순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 원하는 원소를 찾을 수 있다. 순차 탐색은 이름처럼 순차적으로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하여 검사하여 구현도 간단하다. for문 한번으로 구현할 수 있어서 최악의 경우 시간 복잡도는 O(N)이다. 이진 탐색(반으로 쪼개면서 탐색하기) 이진 탐색은 데이터가 정렬되어 있어야지만 사용 가능하다. 이진 탐색은 범위를 절반씩 좁혀가며 탐색하는 특징이 있다. 이진 탐색은 시..

-처음에 생각한 풀이 처음엔 max, min 메소드를 이용하면 될 것이라고 생각했지만 이거로는 충분하지 않았다. -풀이 n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() #오름차순 b.sort(reverse=True) #내림차순 for i in range(k): if a[i] < b[i]: a[i], b[i] = b[i], a[i] else: break print(sum(a)) a를 오름차순, b를 내림차순으로 입력 받는다. 그리고 k만큼 반복하면서 비교한다. 만약 a가 b보다 작으면 두 집합의 원소를 바꾼다. a가 b보다 같거나 커지면 반복문을 종료한..

이 문제는 최대 100,000개까지 입력이 가능하여 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. -내 풀이 n = int(input()) def setting(data): return data[1] ary = [] for i in range(n): x = input().split() ary.append((x[0], int(x[1]))) ary.sort(key=setting) for i in ary: print(i[0], end=" ") -교재 풀이 n = int(input()) ary = [] for i in range(n): x = input().split() ary.append((x[0], int(x[1]))) ary = sorted(a..

퀵 정렬 퀵 정렬은 지금까지 배운 정렬 알고리즘 중에서 가장 많이 사용된다. 이 교재에는 없지만 병합 정렬도 퀵 정렬과 같이 빠르다. 퀵 정렬은 기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 기준 숫자인 피벗이 사용된다. 리스트에서 피벗을 정한다. 피벗을 정하고 나면 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 교환한다. 이렇게 있을 때, 5를 피벗으로 정했다. 그러면 왼쪽에선 7이 피벗보다 크고, 오른쪽에선 4가 피벗보다 작다. 따라서 7과 4의 위치를 바꿔준다. 이러다보면 왼쪽 리스트는 모두 피벗보다 작고 오른쪽은 모두 피벗보다 큰 데이터가 위치한다. 이렇게 ..

정렬 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능하다. 정렬 중에서 많이 사용하는 것은 선택, 삽입, 퀵, 계수 정렬 등이 있다. 파이썬에서는 리스트의 원소를 뒤집는 메서드를 제공하고 이 것은 O(N) 복잡도로 간단하게 수행된다. 선택 정렬 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이 선택 정렬이다. 이렇게 데이터가 있으면 처음엔 0이 선택되어 맨 앞의 7과 자리가 바뀌게된다. 그 다음엔 제일 작은 1이 선택되어 5와 자리를 바꾼다. 이런식으로 하다보면 정렬이 가능하다. 이 과정에서 가장 작..

from collections import deque n, m = map(int, input().split()) ary = [] for i in range(n): ary.append(list(map(int, input()))) #상하좌우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): q = deque() q.append((x, y)) while q: x, y = q.popleft() #상하좌우 방문 for i in range(4): nx = x + dx[i] ny = y + dy[i] #범위 벗어나면 continue if nx = n or ny = m: continue #괴물 만나면 continue if ary[nx]..

n, m = map(int, input().split()) ary = [] for i in range(n): x = list(map(int, input())) ary.append(x) def dfs(x, y): #범위 체크 if x = n or y = m: return False #방문했는지 체크 if ary[x][y] == 1: return False #상하좌우 탐색 ary[x][y] = 1 dfs(x-1, y) dfs(x, y-1) dfs(x+1, y) dfs(x, y+1) return True count = 0 for i in range(n): for j in range(m): if dfs(i, j): count += 1 print(count) ​(0, 0)부터 DFS 탐색으로 좌우앞뒤를 재귀적으로..

DFS DFS: 깊이 우선 탐색이라고도 하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 -인접 행렬 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다. 실제 코드에서는 논리적으로 정답이 될 수없는 999999999, 987654321 등의 값으로 초기화하는 경우가 많다. INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) -인접 리스트 방식 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. # 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연..