https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 이중연결리스트 문제를 풀고 삘받아 원형연결리스트문제까지 도전해보았다. 이것도 역시 단순 수식으로 짧게 푸는 방법도 있지만, 원형 연결리스트로 풀어보았다. import sys input = sys.stdin.readline class CList: class Node: def __init__(self,item,link): self.item = item self.next = link def __init__(self): self.last = None self.size = 0 def insert(..
https://www.acmicpc.net/problem/1406 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 www.acmicpc.net 처음에 단순히 전에 풀었던 스택/큐/덱 문제처럼 접근해서 리스트로 풀었더니 시간 초과가 나왔다. list.insert가 O(n)이고 list..
stack,queue,deque가 무엇인지 설명은 넘어가도록 하고 간단히 STL만 정리했다. queue는 stack과 비슷하고 q.top()대신 q.front()와 q.back()이 있다. queue의 멤버함수는 stack과 거의 같다. 스택 선언 stack s type 자료형을 저장하는 스택 생성 스택의 멤버함수 s.empty() 스택이 비어있으면 1 반환 아니면 0 반환 s.pop() 스택의 맨 위의 요소를 제거 s.push(x) 원소(x) 삽입 s.size() 스택의 전체 크기 반환(스택에 있는 원소 수) s.top() 스택의 맨 위에 있는 데이터 반환 deque는 vector와 비슷하고 데이터의 삽입과 삭제가 front와 back에서 가능하다. deque의 멤버함수는 vector와 거의 같다. d..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. www.acmicpc.net 분류에 이분 탐색이라 되어 있어서 열심히 이분 탐색을 공부해서 풀었다. import sys input = sys.stdin.readline n = int(input()) L = list(map(int, input().split())) m = int(input()) mL = list(map(..
벡터 선언 vector v type 자료형을 저장하는 동적배열(벡터) 생성 vector v(n) 0으로 초기화된 n개의 원소를 가지는 벡터 생성 vector v1(n, m) m으로 초기화된 n개의 원소를 가지는 벡터 생성 vector v2(v1) v2는 v1 벡터를 복사해서 생성 vector v3(n, vector(m, 0)) n*m 크기의 2차원 벡터를 선언하고 0으로 초기화 vector v4 = vector(v1.begin()+2, v1.end()) v4는 v1의 2번째 원소부터 마지막 원소까지 복사하여 생성 벡터의 멤버함수 v.assign(n, x) n개의 원소값을 x로 할당 v.at(i), v[i] i번째 원소를 참조, at은 v[i]보다 느리지만 범위 점검함으로써 안전하다 v.front(), v..
STL(Standard Template Library) * 표준 C++ 라이브러리 * 구성요소 : Container, Iterator, Function Object, Algorithm 등 컨테이너 : 객체를 저장하는 객체, 자료구조 - 순차 컨테이너(sequence container) : array, vector, list, deque 등 * 자료를 입력한 순서대로 저장하기 때문에 저장, 검색 알고리즘에 불리 -> 많지 않은 양의 자료, 검색속도 중요하지 않은 경우 사용 - 연관 컨테이너(associative container) : set, multiset, map, multimap 등 * 이진탐색트리 기반 * 일정규칙에 따라 자료를 조직화하여 저장 * 자료를 정렬하여 저장하기 때문에 검색 유리 -> 많..
백준 1929번 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net * prime함수 : n을 매개변수로 넘겨받아 1부터 n-1까지 n%i = 0이면 a에 1을 더해줘서 최종적으로 a가 1이면 (모든 수는 1로 나누어지므로 모든 수의 a는 최소1이다) 소수 -> True 반환 * a,b를 입력받아 list1에 소수인 것들만 append해줬다. * a와 b가 100만까지 들어오다보니 이 방법으로는 시간초과가 발생하였다. * 따라서 새로운 방법인 '에라토스테네스의 체'를 사용해보았다. import math def get_primes(a,b..
모르는 사이에 조금씩 조금씩..
