![]()
https://www.acmicpc.net/problem/23881 23881번: 알고리즘 수업 - 선택 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 이 문제에서 주의할건 정렬을 할 때 뒤에서부터 정렬한다는 것 (max값을 찾아서 정렬) 시간초과 였다. 정답1 (python 3) import sys input = sys.stdin.readline if __name__ == '__main__': N, K = map(int, input().split()) A = list(map(int, input().sp..
DFS는 재귀를 사용하기 때문에 콜스택에 메모리를 차지한다. 그래서 BFS보다 성능이 딸림 BFS를 쓸 때 큐의 자료형으로는 리스트보다 Collection의 Dequeue가 가장 성능이 좋다. (파이썬 기준) pop함수를 사용할 때 list는 O(n)이고 Deque는 O(1) 의 시간복잡도를 띄기 때문 대신 검색 대상 그래프가 크거나 경로를 저장해야 하는 경우는 DFS가 좋다 검색 대상 그래프가 크지 않고 최단거리/미로찾기를 구해야 하는 경우는 BFS가 좋다 시간복잡도 O(V+E) DFS와 BFS는 완전탐색이기 때문에 Vertex와 Edge의 개수만큼 걸린다. tip. 시간복잡도는 대충 10^8보다만 작으면 된다
https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 진짜 어렵지 않아보였는데 꽤나 애먹은 문제 ^,ㅠ 이 문제는 DP로 풀어야 하는데 처음에 메모이제이션으로 접근했다가 자꾸 NameError가 뜨면서 문제 원인을 알 수 없게됨 그래서 타뷸레이션 방식으로 바꿨다. 타뷸레이션 방식이 메모이제이션보다 더 효율적이기도 하고? (재귀를 쓰다보면 콜스택에 함수가 쌓이면서 메모리를 낭비하는 문제가 있는 반면에 타뷸레이션으로 하면 재귀를 쓰지 않고 상향식으로 접근하면서 계속 했던 값을 저장하니 메모리도 더 효율적으로 쓰는 장점이 있다. ) 정답 풀이 inpu..
DP Dynamic Programming, 동적 프로그래밍 메모이제이션을 이용하여 문제를 푼다 메모이제이션 다음 상태를 저장하고, 사용하기 DP.. 난이도는 천차만별이고 처음에는 무엇을 어떻게 저장해서 써야할 지 몰라서 헤맬 수 있다 함 피보나치, Knapsack .....(피보나치가 두개가 아닌 세개거나, 지문이 너무 길어서 knapsack인지 모르거나..) 많이 풀고 생각 연습을 하는 것이 중요 푸는 순서 상태를 정의한다. 점화식을 찾는다. (구한다) 시간 복잡도를 계산한다. dp로 푸는 경우 시간복잡도가 다양할 수 있음 1차원 배열에서 쭉 도는 O(N), 2차원 배열에서 쭉 도는 O(N^2), O(N^3)... 코테에서 삼차원 배열 이상은 잘 안나온다 함. 2차원, 3차원에서 가장 많이 나온다. 반..
![]()
알고리즘 문제에서 소수를 찾으려는데 시간 복잡도에서 걸렸다. 처음 사용한 소수찾는 함수는 다음과 같다. def get_sosu(num): if num == 1: return 0 for i in range(2, num): if num % i == 0: return 0 return 1 소수는 1과 자기 자신을 제외한 숫자 외에는 약수가 될 수 없다. 다음과 같은 코드를 통해 2에서부터 자기 자신까지 모두 나눴을 때 나머지가 0이 되면 소수가 아니며, 0이 한번도 나오지 않는다면 소수이다. (완전탐색 방법이다. 시간복잡도는 슬퍼지겠다) 시간복잡도는 O(n) 이 되려나.. 아무튼 구하려는 숫자가 커질 수록 시간이 그만큼 늘어나게 되므로 비효율적이다. 소수를 찾는데 가장 효율적인 알고리즘은 에라토스테네스의 체 이..
![]()
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 코드 from sys import stdin import sys input = stdin.readline sys.setrecursionlimit(10000000) region = [] # region은 전역으로 visit = [] dx, dy = [1, -1, 0, 0], [0, 0, 1, -1] def solution(): global region,visit # 1. 입력정보 받기 N = int(inp..
쓰기 편한 것 dx = [-1, 1, 0, 0] dy = [0, 0, 1, -1] 반시계 방향 dx = [0, -1, 0, 1] dy = [1, 0, -1, 0] 시계 방향 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0]
![]()
https://www.acmicpc.net/problem/20953 20953번: 고고학자 예린 예린은 고고학자이다. 예린은 강원대학교 백록관 지하에서 고인돌이 발견되었다는 소식을 듣고 누구보다 빠르게 백록관에 도착하였다. 고인돌을 본 순간 예린은 놀라 자빠질 수밖에 없었다. 고 www.acmicpc.net 쉬운 문제인데 평소에 머리를 워낙 안쓰다시피 하니 끙끙거린다.. 이 문제는 처음에 이런 식으로 풀다가 시간 초과 로 인해 통과되지 않는다. def solution(a, b): sum = 0 for i in range(a + b): for j in range (a + b): for _ in range(j): sum += 1 return sum if __name__ == '__main__': T = in..
![]()
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 핫쒸... 솔직히 처음엔 만만하게 봤는데 어려웠다. 알고리즘은 역시 평소에 꾸준히 안해두면 머리가 굳나보다...반성 반성...^,ㅠ 이 문제는 인덱스가 0부터 시작한다는 것과 재귀함수를 잘 사용해야 한다. (내 코드는 너무 더러웠고 가장 깔끔해보이고 이해된 코드를 기준으로 작성함.) 이 문제는 0, 1, 2, 3 사분면(원래는 1부터 시작하지만 0부터라 하겠다), 각각을 네 개의 case..
![]()
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 문제 : https://programmers.co.kr/learn/courses/30/lessons/64061 생각 단순하게 리스트를 잘 활용하면 되는 문제다. 헷갈린다면 그림을 그려보자. def solution(board, moves): resultList = [] # 인형이 넣어지는 상자 리스트 answer = 0 for choiceNum in moves: for rows in board: if rows[choiceNum-1] != 0: resultList.append(rows[choiceNum-1]) # print("resultList에 뭐가 추가됨 : ", resultList) rows[choiceNum-1] = 0 if len(result..
2018 KAKAO BLIND RECRUITMENT 비밀지도 문제 문제 : https://programmers.co.kr/learn/courses/30/lessons/17681 생각 지도 두개를 통해 하나의 결과를 도출해야 한다. 각 행이 이진수를 나타내면서 지도의 길이에 따라 각 행을 이루는 요소의 개수가 정해진다. arr1, arr2가 두 개의 지도를 의미할 때, 각 배열의 요소들이 각 지도의 한 행을 의미한다. 따라서 십진수를 이진수로 바꿔주는 함수가 필요하다. # 2진수 구하는 함수 구하기 def trans(N, num): result = "" number = num while number > 0: result = str(number % 2) + result number //= 2 if len(r..
![]()
문제 1. 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합 출처 : https://euler.synap.co.kr/problem=2 피보나치(Fibonacci) 수열의 각 항은 바로 앞의 항 두 개를 더한 것이다. 1과 2로 시작하는 경우 이 수열은 아래와 같다. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 될까? 문제 풀이 fiboSum = 2 fibo_1 = 1 fibo_2 = 2 fibo_3 = 0 while(True): if(fibo_3 > 4000000): break fibo_3 = fibo_1 + fibo_2 print("fibo_3", fibo_3) if(fibo_3 % 2 == 0): fiboSum..
