반응형 PS 문제 풀이/Jungol101 [Jungol] 정올 2518 문자열 변환 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1779&sca=203 Approach 변경되는 문자를 두 개의 배열로 매칭 from[] = {'A', '0', '5'} / to[] = {'a', '5', '4'} ABC0145abA → aBC5144aba #define _CRT_SECURE_NO_WARNINGS #include int N, M; char from[50], to[50], temp; void decode(char A) { for (int i = 0; i < N; ++i) { if (A == from[i]) { printf("%c", to[i]); return; } } printf("%c", A); } int main(void).. 2021. 3. 18. [Jungol] 정올 1814 삽입정렬 횟수 세기 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1087&sca=2070 Approach 숫자의 개수가 크지 않은 N이었다면, 실제 삽입 정렬을 구현해서 교환(밀어내기) 횟수를 구해도 되지만, 삽입 정렬의 시간복잡도는 O(N2)이기 때문에 숫자 개수 N이 클 경우 TLE 발생 이 문제는 삽입정렬을 구현하여, 특정 숫자가 삽입 될 때, 교환 횟수를 물어보는 것이 아니라 정렬이 끝난 후, 총 교환 횟수를 요구하고 있습니다. (그 과정에서 삽입정렬 방식이 설명되어 있는 것입니다.) 따라서 시간복잡도 O(NlogN) 많은 숫자 개수 N에서도 가능합니다. Merge Sort에서 교환횟수는 어떻게 구할 수 있을까? 정렬되지 않은 숫자 { 4 3 5 2 1 }.. 2021. 3. 18. [Jungol] 정올 3690 stack api 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3039&sca=99&page=24 Approach Stack 자료구조를 구현하는 문제 ▶ [스택] Stack 이란? [스택] Stack 이란? Stack 이란? 스택 (Stack) 특징을 가장 잘 나타내는 표현은 후입선출(Last In First Out, LIFO) 이다. ▶ 스택(Stack)은 삽입(push)과 삭제(pop)이 한쪽 끝에서만 일어나는 구조 가장 상단에 위치한 원소를 가리. zoosso.tistory.com #ifndef NULL #define NULL 0 #endif const int SIZE = 100010; struct Node { int num; Node* next; Node() { nu.. 2021. 3. 18. [Jungol] 정올 3701 queue api 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3050&sca=99&page=24 Approach Queue 자료구조를 구현하는 문제 ▶ [큐] Queue란? [큐] Queue란? Queue란? 선입선출(First In First Out, FIFO)의 자료 구조 ▶ 큐(Queue)는 한쪽에서 삽입(Push, Enqueue) 하며, 다른 한쪽에서 빠져나오는(Pop, Dequeue) 구조 두 지점을 와 로 표현한다. (Front, Rear) ▶ C++.. zoosso.tistory.com #ifndef NULL #define NULL 0 #endif const int SIZE = 100010; struct Node { int num; Node* next; Nod.. 2021. 3. 18. [Jungol] 정올 1102 스택(stack) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=382&sca=2070 Approach Stack 자료구조 이용 [C++] [STL] Stack Stack 기본 연산 - LIFO 구조 (Last In First Out) - push(element) : 스택 (뒤쪽에) 원소 추가 - pop() : 스택에 (뒤쪽에) 있는 원소 삭제 (반환 x) - top() : 스택에서 끝에 있는 원소 반환 - empty() : 스택이.. zoosso.tistory.com ▶ [스택] Stack 이란? [스택] Stack 이란? Stack 이란? 스택 (Stack) 특징을 가장 잘 나타내는 표현은 후입선출(Last In First Out, LIFO) 이다. ▶.. 2021. 3. 18. [Jungol] 정올 3293 비트연산 1 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2583&sca=50 Approach ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com (1) a가 홀수인지 if문과 비트 연산자를 이용하여 판별하고자 한다. ?자리에 들어갈 비트연산자는? if(a ? 1){} // c, c++인 경우 if((a ? 1) == 1 )) {} // java의 경우 if(a & 1){} if((a & 1) == 1 )) {} (2.. 2021. 3. 18. [Jungol] 정올 3101 요세푸스 문제 1 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2370&sca=50&sfl=wr_homepage&stx=comkiwer Approach N명이 원형으로 모여 앉아 있을 때, 기준으로 부터 시작하여 K번째 사람을 모임에서 제외한다. 이를 N번 실행한 경우 제외된 사람을 순차적으로 나열한 순열을 요세푸스(Josephus) 순열이라고 한다. 배열에서 K번째 원소를 찾은 후, 제거된 순서대로 Queue에 넣어줍니다. K 번째 원소를 찾을 때 사용하는 배열을 원형 큐 구조로 구현 ▶ [큐] Queue란? [큐] Queue란? Queue란? 선입선출(First In First Out, FIFO)의 자료 구조 ▶ 큐(Queue)는 한쪽에서 삽입(Pus.. 2021. 3. 18. [Jungol] 정올 1337 달팽이 삼각형 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=609&sca=2020 Approach 아래와 같이 숫자를 채워갑니다. map[0][0]을 시작으로 달팽이 모양 방향으로 숫자를 채워가는데 3가지 방향으로 존재합니다. 방향 전환하는 시기는 배열의 범위를 벗어나거나 이미 숫자가 채워진 경우입니다. 또한 멈추는 시기는 방향을 전환한 다음 지점이 범위를 벗어나거나 숫자가 채워진 경우입니다. #include const int MAX_N = 100 + 5; const int MOD = 10; const int dx[] = {1, 0, -1}; const int dy[] = {1, -1, 0}; int map[MAX_N][MAX_N]; int N, r,.. 2021. 3. 17. [Jungol] 정올 1641 숫자삼각형 출처: http://www.hancom.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=914&sca=2020 Approach ① 홀수번째 줄은 윗줄에서 +1 처리 후, 값을 증가시키며 출력(해당 줄을 출력 후 마지막에는 감소시킵니다.) 짝수번째 줄은 해당 i번째 줄의 전체 개수(= i)개를 시작으로 감소시키면서 출력 ② 숫자 앞쪽에 공백 출력에 유의 첫번째 줄에 출력되는 0의 개수는 2 * N - 1이며, 그 다음 줄부터는 -2씩 감소됩니다. ③ 각 줄마다 [1, end]까지 숫자를 출력하며, end의 범위를 조정합니다. N / 2 +1 줄까지는 각 줄에 출력되는 개수가 증가하다가 그 이후부터는 다시 감소합니다. #include int N, M; int main().. 2021. 3. 17. [Jungol] 정올 1495 대각선 지그재그 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=767&sca=2020 Approach - 영역을 2개로 나눕니다. - 각 영역을 아래와 같이 숫자를 채워갑니다. #include const int dx[] = {1, -1}; const int dy[] = {-1, 1}; int N, x, y, dir, val; int map[101][101]; int main() { // freopen("input.txt", "r", stdin); scanf("%d", &N); // 시작점 x = y = 1; // 첫번째 영역 for (int i = 1; i = 1; --i) { map[x][y] = ++val; for (int j = 1; j < i; +.. 2021. 3. 17. 이전 1 2 3 4 5 ··· 11 다음 반응형
