본문 바로가기
반응형

알고리즘149

(Python/🥈3)백준 알고리즘 1269번: 대칭 차집합 문제 출처:https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 풀이: (N,M) = sys.stdin.readline().split() A = set() B = set() for i in sys.stdin.readline().rstrip(): A.add(i) A.discard(' ') for i in sys.stdin.readline().rstrip(): B.add(i) B.discard(' ') print(len(A-B)+len(B-A)) .. 2022. 5. 26.
(Python/🥈4)백준 알고리즘 1764번: 듣보잡 문제 출처:https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이: (N,M) = sys.stdin.readline().split() # N은 듣잡 M은 보잡 list1 = set() list2 = set() for i in range(int(N)): list1.add(sys.stdin.readline().rstrip()) for i in range(int(N)+1): list2.add(sys.stdin.readline().rstrip()) r.. 2022. 5. 26.
(Python/🥈4)백준 알고리즘 10816번: 숫자 카드 2 문제 출처: https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이: N = int(input()) arr = list(map(int, input().split())) N2 = int(input()) arr2 = list(map(int, input().split())) res = list() for i in arr2: if i in arr: res.append(arr.count(i)) else: res.appen.. 2022. 5. 26.
(Python/🥈4)백준 알고리즘 1620번: 나는야 포켓몬 마스터 이다솜 문제 출처:https://www.acmicpc.net/step/49 집합과 맵 단계 카드의 집합을 만들어 특정 카드가 집합에 있는지 빠르게 찾는 문제 www.acmicpc.net 풀이: (N,M) = sys.stdin.readline().split() # 도감에 있는 포켓몬 갯수 N 문제갯수 dict = {} # 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, # 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. for i in range(1,int(N)+1): word = sys.stdin.readline().rstrip() dict[i] = word dict[word] = i # dict 을 만들어줌 몬스터가 키일때 숫자가 키일때 둘다 for i in range(int(M)): .. 2022. 5. 26.
(Python/🥈3)백준 알고리즘 14425번: 문자열 집합 문제 출처:https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이: (N,M) = sys.stdin.readline().split() setword_S = set() # 집합에 포함되어 있는 문자열들 setword = list() # 검사할 문자열들 count = 0 for i in range(int(N)): # 집합에 들어갈 단어들 setword_S.add(sys.stdin.readline().rstrip()) .. 2022. 5. 26.
이진탐색/선형탐색 Search 알고리즘 1) 선형탐색 O(N) 선형탐색 이란 일렬로 된 자료를 왼쪽부터 차례대로 탐색하는 것을 말한다 즉 배열이 커질수록 시간이 길어지며 시간복잡도는 O(N) 을 이룬다 인풋이 많을수록 수행하는 시간또한 선형적으로 증가하게 된다. 구현이 아주 쉽다는 장접이 있지만 시간 복잡도가 O(N) 이라서 효율적이지 않다는 단점이 있다. def solution(L, x): for i in range(len(L)): if x == L[i]: return i return -1 L1 = [3,5,2,8,6,1,7] x = 2 y = 7 print(solution(L1, x)) print(solution(L1, y)) # 선형탐색 예제 # 2 6 출력 여기서 발전한 방법이 이진탐색이다. 1) 이진탐색 O(lo.. 2022. 5. 26.
반응형

티스토리툴바