목록코딩테스트 (10)

어제보다 더 나은 나

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

* 배열 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
백준_11650번_좌표정렬하기

import sys N = int(input()) dot_list = [] for _ in range(N): dot = list(map(int, sys.stdin.readline().split())) dot_list.append(dot) # print(dot_list) dot_list.sort(key=lambda x: (x[0], x[1])) for j in range(N): print(dot_list[j][0], dot_list[j][1])
코딩테스트/문제풀이 2022. 7. 11. 20:14
백준_9324번_진짜메시지

n = int(input()) for i in range(n) : message = input() dict = {} answer = 'OK' ch = 0 for j in range(len(message)) : if message[j] not in dict.keys(): dict[message[j]] = 1 else : dict[message[j]] += 1 #print(message[j], dict[message[j]]) if dict[message[j]] == 4: dict[message[j]] = 0 #print(j) if (dict[message[j]] > 0) & (dict[message[j]]%3 == 0): # print(dict[message[j]]) if j+1 < len(message) ..
코딩테스트/문제풀이 2022. 7. 11. 18:37
백준_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
Prev 1 2 Next