'coding test'에 해당되는 글 13건

ambiguous 오류

입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다.

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.

또한 입력과 출력 스트림은 별개이므로, 테스트케이스를 전부 입력받아서 저장한 뒤 전부 출력할 필요는 없다. 테스트케이스를 하나 받은 뒤 하나 출력해도 된다.

이 외 다른 언어 관련 내용 링크

https://www.acmicpc.net/board/view/22716

https://www.acmicpc.net/blog/view/55

-출처 백준

const int MX = 1000005;
int front, back = MX;

위와 같은 방식으로는 할당에 오류가 생김

const int MX = 1000005;
int front = MX;
int back = MX;

이렇게 해야 에러가 안뜸

양쪽 끝에서 삽입과 삭제가 가능.

deque 이면서 Double Ended Queue라는 뜻을 지니고 있다함

일반적으로 아는 deck이랑은 다른 단어임

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 앞/뒤의 원소 확인이 O(1)

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

덱에서도 삽입,삭제,제일 앞/뒤 원소의 확인이 O(1)이다.

제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다는데

특이하게도 STL deque에서는 인덱스로 원소에 접근할 수 있음.

STL stack, queue에서는 불가능했던 거라 특이함.

배열로 구현한다 치면,

가운데 인덱스에서 시작하는게 좋음

STL deque에 insert와 erase도 있고 front에서도 O(1)의 속도를 보이니

vector의 상위호환인가 싶지만,

vector와 달리 deque의 원소들은 메모리 상에 연속하게 배치되어 있지 않다.

둘을 굳이 짧게 비교하자면,

앞쪽에서의 추가,제거가 필요하면 deque를,

그렇지 않고 배열느낌으로 쓸거면 vector가 낫다는 듯.

FIFO(First In First Out) 형식 자료구조

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 앞/뒤의 원소 확인이 O(1)

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

만약 배열로 구현한다 칠 때,

삭제가 발생할 때마다 앞쪽에 쓸모없는 공간이 생기는데

이것을 방지할 수 있는 방법은 원형큐(맨첫 인덱스와, 마지막 인덱스를 연결)를 만드는 것이다.

그래서 실무에서 큐를 만들고자 한다면, 원형큐를 만들어 쓰는게 좋다.

원형큐의 경우 그냥 head와 tail로 지정한 부분이 배열 끝 수에 오면

0으로 바꿔주는 식으로 한다

이런 기본적인 것들부터 제대로 알아야

팍팍 성장할 수 있지.

먼저 들어온 것이 나중에 나가는 구조 FILO(First In Last Out)

이렇게 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다 함.

그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 합니다.

스택의 성질

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 상단의 원소 확인이 O(1)

4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

s.empty() : 비어있는지 확인

s.size() : 원소 수를 반환

s.top() : 맨 위의 원소 리턴

s.push(n) : 맨 위에 원소 추가

s.pop() : 맨 위의 원소 삭제

선형 자료구조

배열

- 임의의 위치에 추가하거나 삭제하는데 O(N)

- 특정 원소 접근 확인/변경 O(1)

연결리스트

- 임의의 위치 추가 삭제하는데 O(1).. 단, 주소를 알고있다는 가정하에..

- 특정 원소 접근 확인/변경 O(N)

- C++ 배열은 전역에 선언하면 원소들이 알아서 0으로 초기화됨

근데 그렇지 않으면 이상한 숫자들로 초기화 됨

- 배열에 특정 아스키 코드 순서가 개입되야하는데 0부터 시작하고 싶다면

첫번째 걸로 초기화 해 둘 수 있겠다.

예를 들어 알파벳 세기 문제에서

string s;

for(auto c : s)

   freq[c - 'a']++;

이런식으로 c는 결국 char나 string일텐데

a는 알파벳의 첫번째 순서니까

c를 a만큼 빼면 아스키 코드 상에서 a로 시작되는 알파벳 구간에서 시작되는것