목록코딩테스트 (8)

어제보다 더 나은 나

자료구조 (배열, 벡터, 연결리스트, 스택, 큐)

* 배열 Array 삽입 / 삭제 : O(N) ( 삭제, 삽입하려는 위치 이외의 원소들을 한 칸씩 다 이동시켜야 하기 때문) 탐색 : O(1) ( 임의접근 Random access, 이유 : 인덱스를 사용했다고 해서 해당 인덱스에 이르기까지의 요소들을 모두 거치는 것이 아니라 배열의 주소 + 인덱스*type의 크기 = 메모리 주소값이라는 것을 이용해서 바로 해당 인덱스의 원소에 접근하기 때문) Python은 리스트를 사용 C++에서는 size 변경불가 (생성 시, size와 type 고정) * 벡터 Vector ( 2개 이상의 값 저장 ) 삽입 / 삭제 : O(N) 탐색 : O(1) 동적 배열 (size 변경 가능) * 연결리스트 Linked List (배열과 반대의 특성) 삽입 / 삭제 : O(1) 탐..
코딩테스트/이론 2022. 8. 11. 23:15
시간복잡도, 공간복잡도, 오버플로우

* 시간 복잡도 알고리즘의 최악의 경우 실행시간 입력량 N에 비례해서 얼마나 연산을 많이 하는지를 나타냄 빅오 표기법 (Big-O notation)으로 나타냄 알고리즘의 효율성 척도 C++ 기준 1초에 연산 1억 번이 넘어가면 위험 (1초 = 1억) * 공간 복잡도 N에 비례해서 메모리를 얼마나 사용하는지를 나타냄 메모리(공간)과 시간은 Trade Off 관계 Ex) 시간제한 2초, 메모리 제한 64MB, 입력 N의 범위는 0
코딩테스트/이론 2022. 8. 10. 20:55
백준_1316번_그룹단어체커

n = int(input()) a = list() for i in range(n): word = input() a.append(word) non_sequence = 0 non_word = 0 for i in range(n): non_sequence = 0 word_length = len(a[i]) for j in range(word_length): temp = a[i][j] temp_i = j for k in range(j+1, word_length): if a[i][k] == temp and k - temp_i == 1: temp_i = k elif a[i][k] == temp and temp_i - k != 1: non_sequence = non_sequence + 1 break if non_sequ..
코딩테스트/문제풀이 2022. 5. 13. 17:42
백준_1075번_나누기

import math N = int(input()) F = int(input()) sol = N % F # 나머지 구하기 i = 0 temp_N = N while True: if temp_N//10 > 0: temp_N = temp_N//10 i += 1 else: break p = math.trunc(N / (100)) # 100의 자리숫자~ if math.trunc((N - sol + F)/100) == p: temp_N = N - sol + F # N에서 나머지를 빼줌. 즉 나누어 떨어짐 else : temp_N = N - sol for i in range(100//F): if math.trunc((temp_N-F)/100) == p: min_sol = (temp_N-F) % 100 temp_N =..
코딩테스트/문제풀이 2022. 5. 12. 21:41
구름LEVEL_화학물질

t = int(input()) test_case = [list(map(int, input().split())) for _ in range(2 * t)] for i in range(t): special_volume = 0 min_set = 0 maxi = max(test_case[2 * i + 1]) if maxi == 0: for j in range(len(test_case[2 * i + 1])): test_case[2 * i + 1][j] = test_case[2 * i + 1][j] + test_case[2 * i][1] min_set = min_set + 1 while True: if test_case[2 * i + 1][2] == 0: for j in range(len(test_case[2 * i..
코딩테스트/문제풀이 2022. 5. 10. 20:41
Prev 1 2 Next