codeplus 스타트링크 백준 알고리즘 강의 기초 2강- queue, deque, ascii 코드,문자열
코드 플러스 백준알고리즘 강의 정리.
일+운동 다녀와서 엄청나게 피곤하지만.. 그래도 할 건 해야지...ㅠㅠ 오늘은 3강 큐와
queue란?
한 쪽 끝에서 자료를 넣고 다른 한쪽 끝에서 뺄 수 있는 구조. 터널이나 무빙워크 정도로 생각하면 편하겠다.
먼저 넣는 것이 가장 먼저 나오는 구조.
queue는 c++에 STL에 있기 때문에 구현해서 쓰기보다는 가져다 쓰는 것이 편하다.
c++의 경우 : queue
java의 경우 : java.util.Queue
queue의 STL APT
push : 큐에 자료를 넣는 연산 . return 값이 없다
pop : 큐에서 자료를 빼는 연산. return 값이 없다
front : 큐의 가장 앞에 있는 자료를 보는 연산. 가장 앞에 있는 자료를 return한다.
back : 큐의 가장 뒤에 있는 자료를 보는 연산. 가장 뒤에 있는 자료를 return한다. -> queue특성상 활용도가 높지 않다.
empty : 큐가 비어있는지 아닌지 알아보는 연산. 비어있으면 true, 아니면 false를 boolean형으로 return한다.
size : 큐에 저장되어있는 자료의 개수를 알아보는 연산. 자료의 개수를 return한다.
queue에 관련해서 풀어볼 문제
10845번(https://www.acmicpc.net/problem/10845)
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
www.acmicpc.net
- queue를 구현하는 문제로 stl을 사용하지말고 구현해보자.
1158번(https://www.acmicpc.net/problem/1158)
1158번: 조세퍼스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
- queue를 이용해서 시뮬레이션 하면 된다.
- push와 pop을 반복하면 간단히 해결할 수 있을 것같다.
deque이란?
양 쪽 끝에서 자료를 넣고, 양 끝에서 뺄 수 있는 자료구조. 좀 더 개선된 queue라고 생각하면 되겠다.
deque는 c++에 STL에 있기 때문에 구현해서 쓰기보다는 가져다 쓰는 것이 편하다.
c++의 경우 : deque
deque의 STL APT
push_front, push_back : 각각 앞뒤에 자료를 넣는 연산. return값이 없다
pop_front, pop_back : 각각 앞뒤에 자료를 빼는 연산. return값이 없다
front : 덱의 가장 앞에 있는 자료를 보는 연산. 가장 앞에 있는 자료를 return 한다.
front : 덱의 가장 뒤에 있는 자료를 보는 연산. 가장 뒤에 있는 자료를 return 한다.
queue에 관련해서 풀어볼 문제
10866번(https://www.acmicpc.net/problem/10866)
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
www.acmicpc.net
- 덱을 구현하는 가장 기본적인 문제.
- 알고리즘 문제에서 많이 나오지않고 구현이 복잡한 만큼 STL을 사용하는 연습으로 풀거나, 아니면 직접 구현해봐도 좋겠다.
ASCII 코드란?
문자를 인코딩하는 방법중 하나라고 생각하면 된다.
각각 숫자로 매핑해 되어있고, 출력만 그에 해당하는 글자로 해주는 것이라고 이해.
ascii code와 관련해서 풀어볼 문제
별도의 알고리즘 없이 대충 구현해도 풀 수 있어서 나도 대충 적음ㅎ
10808번, 10809번, 10820번
- 배열을 만들던지 map으로 매핑하는 방법으로 하던지 그냥 편한대로 편한 구조 사용해서 풀면 될 것같다.
문자열 관련 문제
2743번(https://www.acmicpc.net/problem/2743)
-for(int i=0;i<strlen(s);i++) 이런식으로 구현하면 for문에 들어올때마다 strlen함수를 돌리므로 시간복잡도가 O(n^2)로 커진다. 따라서 변수에 strlen(s) 값을 할당해서 풀면 O(n)으로 풀 수 있다.