아이테킨의 끄적끄적

시간복잡도 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..

그리디 문제에서 가장 대표적인 거스름돈 동전 문제이다. # 2720 세탁소 사장 동혁 t = int(input()) coins=[25,10,5,1] for _ in range(t): change = int(input()) change_coin = [] for coin in coins: change_coin.append(change//coin) change -= (change//coin)*coin for i in change_coin: print(i,end=' ')

일단 이 문제는 내 스스로 풀지 못했다. 오늘 임계점에 도달했는지 머리가 돌아가기를 거부한 듯 하다. 지금 안하면 영원히 안하게 될거같아서 어쩔수없이 구글찬스를 썻다..ㅎㅎ 단어수학이라는 문제인데 대문자의 영어알파벳 단어를 입력받고 각 알파벳의 자리수만큼 10의 승수만큼 곱해주어 단어들의 수를 정하고 그 합계의 최대값을 구하는 문제이다 아래의 링크에 들어가보면 문제에 대한 설명이 잘 나와있다. https://jokerldg.github.io/algorithm/2021/03/13/word-math.html 백준 1339번 단어 수학 (python 파이썬) - Tech 백준 1339번 단어 수학 (python 파이썬) March 13, 2021 jokerldg.github.io 코드 # 1339 단어 수학 ..