본문 바로가기

BOJ 알고리즘 (패캠)

 (52)
1668번: 트로피 진열 (탐색) - Fastcampus www.acmicpc.net/problem/1668 1668번: 트로피 진열 민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열 www.acmicpc.net # 보이는 트로피의 수 => 최대값이 갱신되는 횟수 카운팅 def search(N, heights): cnt = 0 max_v = -1e9 for x in heights: if x > max_v: max_v = x cnt += 1 return cnt N = int(input()) heights = [int(input()) for _ in range(N)] print(search(N, heights)) print(sear..
1302번: 베스트셀러 (탐색) - Fastcampus www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net # 베스트셀러 찾기 => 분류해서 카운팅 def search(books): d = {x: 0 for x in set(books)} for x in books: d[x] += 1 # lst = sorted(d, key=lambda x: (-d[x], x)) lst = [] for k, v in d.items(): if v == max(d.values()): lst.append(k) lst.sort() re..
1568번: 새 (탐색) - Fastcampus www.acmicpc.net/problem/1568 1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현�� www.acmicpc.net O(sqrt(N)) # 모든 새가 날아가기까지 걸리는 시간 => 새 감소시키며 반복횟수 카운팅 def search(bird): sec, song = 0, 0 while bird: sec += 1 song += 1 if song > bird: song = 1 bird -= song return sec bird = int(input()) print(search(bird))
1543번: 문서 검색 (탐색) - Fastcampus www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한� www.acmicpc.net O(NM) = 10만 # 문서에서 단어 카운팅 def search(doc, word): cnt = 0 ld, lw = len(doc), len(word) i = 0 while i + lw
7490번: 0 만들기 (구현, 재귀) - Fastcampus www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net def recur(N, res, a=[]): if N == 1: res.append(a[:]) return for op in (" ", "+", "-"): a.append(op) recur(N-1, res, a) a.pop() T = int(input()) for _ in range(T): N = int(input()) a = list(range(1, N + 1)) res = [] recur(N, res) for ops in res: exp = "" for i i..
1074번: Z (구현, 재귀) - Fastcampus www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 �� www.acmicpc.net def recur(size, cnt=0, x=0, y=0): global res if size == 1: if x == R and y == C: res = cnt cnt += 1 return cnt size //= 2 for i, j in [(x, y), (x, y+size), (x+size, y), (x+size, y+size)]: # 가지치기 추가: 4분면 중 1개만 탐색한다 if (i
2747번: 피보나치 수 (구현, 재귀) - Fastcampus www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된�� www.acmicpc.net # 반복 def fibo(n): a, b = 0, 1 for _ in range(n-1): a, b = b, a+b return b # 재귀 def fibo(n): if n
10989번: 수 정렬하기 3 (정렬, 계수정렬) - Fastcampus www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net # [KP] # 1> 메모리 제한으로 기본 정렬 함수로는 안됨 => 계수정렬 (숫자별 카운트) # 2> 시간 초과로 input() 함수로는 안됨 => sys.stdin.readline() import sys N = int(input()) ck = [0] * 10001 for _ in range(N): n = int(sys.stdin.readline()) ck[n] += 1 for i in range(1, 10001): cnt =..

티스토리툴바