알고리즘

문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 출력 첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 ..

- 정의와 성질 - 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 이중 연결 리스트는 단일 연결 리스트와 달리 주어진 원소의 이전 원소를 알 수 있다. 다만 원소가 갖고 있어야 할 정보가 1개 더 많아져서 메모리를 더 많이 차지하게 된다. 원형 연결 리스트는 원소의 처음과 끝이 연결되어 있는 리스트이다. 배열과 달리 연결 리스트는 다음 원소의 주소 값 또는 이전 원소의 주소 값을 갖..

- 배열의 정의 - 배열을 선언한 뒤에 배열의 길이를 변경하는 게 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 가정하자. - 배열의 성질 - 1) 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이기 때문에 k번째 원소의 위치를 바로 계산할 수 있다. k번만큼 이동하면 되기 때문에 시간복잡도 O(1) 2) 다른 자료구조들과 다르게 추가적으로 소모되는 메모리 양이 거의 없다. 3) 메모리 상에 데이터들이 붙어있기 때문에 Cache hit rate가 높다. 4) 메모리 상에 연속한 구간을 잡아야 하기 때문에 할당에 제약이 걸린다. - 배열의 기능(시간복잡도) - -배열을 특정 값으로 초기화시키는 방법- 1) cstring의 memset 함수는 memset(포인터(배열의 ..

문제 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다. 한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다. 두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지..

문제 C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래밍 언어에서 문자열을 다루는 것은 매우 중요하기 때문에, C 표준 라이브러리는 문자열을 다루는 데에 매우 유용한 함수들을 제공하고 있다 : 그들 중에는 strcpy, strcmp, strtol, strtok, strlen, strcat 가 있다. 하지만, 잘 알려져 있지 않으며, 잘 사용되지도 않는 함수가 하나 있다 : strfry 함수다. strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어낸다. (역자 주 : 여기에서 입력된 문자열과 새로 재배열된 문자열이 다를 필요..

문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 코드 #include using namespace std; int n, a[100000], x, tmp[1000001], ans = 0; int main(void) {..

0x02강 - 기초 코드 작성 요령 2 - STL 함수 인자 - 기초적인 내용을 확인해보자. 위 코드들은 각각 함수 인자로 int, int 배열, 구조체를 보내 값을 바꿨을 때 원본의 값이 바뀌는 지를 확인하는 코드이다. 첫 번째 코드처럼 int를 함수 인자로 보내면 원본이 아니라 복사된 값이 보내진다. 때문에 함수에서 값을 바꾸더라도 main의 변수 t에는 아무런 영향을 주지 않는다. 두 번째로 int 배열인 arr를 보내는 것은 함수 인자로 arr의 주소를 넘기는 것이다. 따라서 func 함수에서 arr[0] 값을 바꾸면 원본에서도 자연스럽게 바뀌게 된다. 마지막으로 구조체 tmp는 int 변수와 마찬가지로 값이 다 복사되기 때문에 원본이 영향을 받지 않는다. 두 변수의 값을 바꿔주는 swap 함수를..

문제 두 양의 정수가 주어졌을 때, 두 수 사이에 있는 정수를 모두 출력하는 프로그램을 작성하시오. 입력 두 정수 A와 B가 주어진다. 출력 첫째 줄에 두 수 사이에 있는 수의 개수를 출력한다. 둘째 줄에는 두 수 사이에 있는 수를 오름차순으로 출력한다. 서브태스크 예제 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); long long a, b; cin >> a >> b; if (a > b) swap(a, b); if (a == b) cout

0x00강 - 오리엔테이션 - 코딩 테스트에 대한 정보 - 코드의 채점을 진행하는 입력 데이터를 테스트 케이스, TC라고 부른다. 테스트 케이스는 적어도 30개에서 50개는 있어야 한다. 코딩 테스트는 코드가 모든 테스트 케이스를 통과했을 때만 문제를 맞혔다고 처리한다. - 환경 세팅 - Visual Studio 2017/2019는 기본적으로 msvc 컴파일러를 사용하지만 거의 모든 채점 서버는 gcc 컴파일러를 사용한다. msvc에서는 못쓰는데 gcc에서는 할 수 있는 기능이 일부 있다. 예를 들어, msvc에서는 배열을 선언할 때 그 크기로 변수를 이용할 수 없는데, gcc에서는 가능하다(VLA, 가변 길이 배열). 강의 내에서는 msvc, gcc에서 모두 잘 실행되는 코드로 설명한다. bits 폴더..