아이테킨의 끄적끄적

계수정렬(counting sort)을 사용해서 풀어야하는 문제다. 계수정렬의 가장 큰 특징은 비교정렬이 아니다 라는 점이다. 비교정렬은 두수의 대소관계를 반복적으로 계산하면서 푸는 정렬방법인데 계수정렬은 이런 방법을 사용하는게 아니라 말 그대로 숫자들의 개수를 세면서 정렬한다. 그리고 계수정렬의 시간복잡도는 선형시간이다 O(n) 성능이 좋다는 다른 정렬방법(퀵정렬 - O(n^2), 병합정렬 - O(nlogn), 힙정렬 - O(nlogn))들 보다도 훨씬 빠르다. 그러나 단점은 제한이 많다는 것이다. 값들간의 차이 크기가 별로 없거나 값들이 정수로만 이루어져있을때 사용이 가능하다. 역시나 모든 문제에서 좋은 알고리즘은 없고 그때그때마다 상황에 맞는 알고리즘을 찾아서 사용해야 한다. 계수정렬의 스탭별 자세한..

먼저 이 글은 나동빈님의 '이것이 취업을 위한 코딩테스트이다' 이진탐색 파트를공부하고 정리한 것임을 밝힙니다. 순차탐색(Sequential Search) 리스트 안에서 특정 원하는 데이터를 찾으려고 할때 가장 먼저 떠올릴 수 있는 아이디어는 처음부터 하나하나 확인하면서 일치하는 데이터의 인덱스를 뽑아내는 것이다. 이를 순차탐색(Sequential Search) 이라고 한다. 반복문과 조건문을 적절히 이용하면 큰 어려움 없이 만들어볼 수 있다. 이때의 시간복잡도는 당연히 O(N)이다 이제 더 빨리 찾아낼 수 있는 이진탐색에 대해서 알아보자. 이진 탐색(Binary Search) 먼저 이진탐색은 데이터가 정렬이 되어있는 상태에서 사용할 수 있는 알고리즘이다. 이진탐색의 아이디어는 위치를 나타내는 변수 3개를..

시간복잡도 O(nlogn)을 가지는정렬을 사용해야 통과가 가능한 문제이다 1. 파이썬 내장함수 사용(sorted) 2. 퀵정렬 3. 퀵정렬(cache사용없이) 4. 병합정렬 5. 힙정렬 이 다섯가지 정렬방법으로 풀어보았다. (그리고 시간이 중요한만큼 sys.stdin.readlind으로 입력값을 받았다.) 1. 파이썬 기본 내장함수 sorted() import sys n = int(input()) li = [] for _ in range(n): li.append(int(sys.stdin.readline())) for i in sorted(li): print(i) 병합정렬을 기반으로 만들어진 함수이며 O(nlogn)의 시간복잡도를 가지는 알고리즘이라고 한다. 일반적으로 직접 함수를 만들어서 사용하는 것보다..

최단거리를 찾는 문제이므로 bfs탐색 알고리즘을 사용하면 쉽게 풀수 있다. 또 시간초과가 떳다. 이게 시간초과가 뜬 내가 만든 코드이고 from collections import deque import sys input = sys.stdin.readline def bfs(): while queue: x,y = queue.popleft() for step in range(8): nx,ny = x + dx[step], y+dy[step] if 0

이 코드로 했더니 테스트케이스의 답들은 잘 나오는데 시간초과가 떠버렸다. 3차원 배열을 사용해야 하는 문제라서 반복문 3개를 썻다고 시간초과가 나오는 건 아닐거라고 생각한다. 확실한 이유는 아닐 수도 있지만 내 생각에 중간에 zip내장함수를 이용해서 좌표를 만들어낼때 내부적으로 연산이 더 되는게 아닌가 싶다. 사실 잘 모르겠다. 어떤 부분에서 시간 초과가 나는지...ㅠㅠ # 7569 토마토 3차원 문제 import sys input = sys.stdin.readline m,n,h = map(int,input().split()) graph = [[] for _ in range(h)] for i in range(h): for _ in range(n): graph[i].append(list(map(int,in..

최단거리를 묻는 문제에서는 우선 BFS탐색법을 생각해봐야 한다. 단순히 최단거리를 묻는 문제가 아니라 여러가지 조건들을 만족시켜야 하는 상황이어서 코드가 약간 길어지긴 했지만 다행히 통과가 되었다. BFS문제는 큐 자료구조를 이용해서 큐가 빌때까지 하나씩 노드를 뽑아서 탐색하는 방법이다 1. 큐 자료구조를 만들고 2. 큐에서 한개씩 뽑아서 탐색 3. 큐가 빌때까지(while queue:) 코드 # 7576 토마토 m,n = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input().split()))) arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우 from collections..

bfs문제다. 최단거리를 찾는 문제는 bfs탐색법을 활용하면 된다. bfs는 큐 자료구조를 활용하는데 큐에서 한개씩 꺼내서 연결된 노드들을 탐색하면서 큐가 빌때까지 루프를 돌려주면 되는 탐색 알고리즘이다. # 2178 미로 탐색 - 최단거리 n,m = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input()))) arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우 from collections import deque def bfs(x,y,step=1): q = deque() q.append([x,y]) while q: node = q.popleft() for i in arrow:..

이번 문제는 이전 단지번호 붙이기(2667번)에서 사용되었던 방법을 이용하면 풀수 있다. 아니, 문제 자체는 오히려 더 쉽다. 하지만 이번 문제에서도 에러를 만나게 되었는데 바로 런타임에러(recursion error)이다. 이놈을 만나고 나서 계속 코드를 하나하나 뜯어보았다. 분명히 코드엔 잘못된 부분이 없는것 같다. base case조건도 분명하게 걸어놨고 테스트 입력값에서도 잘 돌아갔다. 구글링을 통해서 찾아보니 재귀의 깊이제한을 설정해줘야 한다는 것을 알았다. 파이썬은 기본 재귀 깊이 제한이 1000으로 매우 얕다고 한다. 따라서 재귀를 사용하여 문제를 풀 때에는 위의 코드를 넣어주어 재귀에러가 나는것을 막아주어야 한다. 이후에 코딩테스트에서도 이부분은 필수라고도 적혀있으니 기왕이면 외워두는게 좋..

DFS문제다. DFS/BFS 탐색문제를 계속해서 풀면서 느끼는건 1. 방문했던 곳을 한번더 방문하지 않기 위해서 적절한 표시를 남기는 방법 2. DFS는 재귀를 이용해서 BFS는 큐를 이용해서 푼다. 이 두가지를 고려하면서 문제를 풀기 시작하면 어느정도 풀리는 것 같다. 처음에는 DFS문제이므로 주어진 값들을 그래프로 그려보고 노드라고 보고 문제를 풀어보려고 했었다. 그런데 자기 자신으로 이어지는 노드들을 고려하는게 생각보다는 까다로웠다. 그래서 그냥 그래프, 노드 이런 개념들은 잠시 접어두고 2차원 배열 그 자체로 보고 문제를 풀기 시작했다. 먼저는 dfs함수를 정의했다. 주어진 좌표평면에서 벗어나지 않으면서 숫자가 1인 곳들을 표시하면서 탐색하는 함수를 만들었다. 그리고 표시를 할 때 각 단지별로 서..

dfs/bfs문제다. 문제를 크게 꼬거나 어렵게 만들지 않은 것 같다. dfs/bfs 둘중에 하나만 제대로 구현할 줄 알면 풀 수 있는 문제인 것 같다. 감염된 컴퓨터의 개수를 구하는 문제이므로 탐색문제에서는 시작점으로부터 방문한적이 있는 노드의 수를 카운팅하면 되는 문제이다. BFS를 이용한 풀이 # 2606번 바이러스 - bfs n = int(input()) m = int(input()) graph = [[0]*(n+1) for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 visited = [0]*(n+1) from collections import deque def bfs..