알고리즘

[백준 17143: 낚시왕] (C++)

삼성 SW 역량 테스트 기출 문제 https://www.acmicpc.net/workbook/view/1152 ㄴ낚시왕 https://www.acmicpc.net/problem/17143 l 문제 1. 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. ( R, C )는 가장 오른쪽 아래 칸 2. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 3. 매 초 마다 다음 순서대로 일이 일이 일어난다. l 순서 1. 낚시왕이 오른쪽으로 한 칸 이동한다 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 ..

[백준 17070: 파이프 옮기기 1] (C++)

삼성 A형 기출 문제 https://www.acmicpc.net/workbook/view/2771 ㄴ파이프 옮기기 1 https://www.acmicpc.net/problem/17070 l 문제 1. 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸(r, c)은 1부터 시작하며 빈 칸이거나 벽이다. 빈 칸은 0, 벽은 1로 주어진다. 2. 집 수리를 위해서 파이프 하나를 밀어서 이동시키려고 한다. 파이프는 →, ↘, ↓ 방향으로 밀 수 있다. 파이프는 밀면서 45도 까지 회전시킬 수 있으며, (→, ↘, ↓) 3가지 방향이 가능하다. 3. 놓여진 방향에 따라 이동 방법은 다음과 같다. 가로 : →, ↘ 세로 : ↘,..

[백준 16637: 괄호 추가하기] (C++)

삼성 A형 기출 문제 https://www.acmicpc.net/workbook/view/2771 ㄴ괄호 추가하기 https://www.acmicpc.net/problem/16637 l 문제 1. 길이가 N인 수식이 있다. 2. 수식(문자열)은 정수로 시작하고, 연산자와 정수 번갈아가며 나온다. 수식에 포함된 정수는 0이상 9이하, 연산자는 +, -, * 중 하나 3. 연산자 우선순위는 모두 동일, 수식 계산을 왼쪽에서부터 순서대로 한다. 3+8×7-9×2의 결과는 136 4. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 중첩된 괄호는 사용할 수 없다. 추가하는 괄호 수 제한 없다. 추가하지 않아도 됨 5. 항상 올바른 수식..

[실전 압축 알고리즘] - 실수형을 특정 소수점 까지 출력

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 몇 번째 자리에서 반올림 하여라. 또는 절대/상대 오차가 10^-9까지 허용한다. 이런식으로 주어지는 문제에서는 반드시 조건에 맞게 출력을 해주어야 합니다. 소숫점 9자리 까지 출력한다고 가정하였을 때 printf("%.9lf", a/b); cout > setprecision(8) = 33.14159200 ex) 3.141596 fixed >> setprecision(5) = 3.14160 정리 cout 사용시 n번째 자리 까지 출력해야 한다면 = 절대/상대 오차가 n 이라면 1. 정밀도를 위해 float형 대신 double형 쓰세요 2. fixed >> setprecision(숫자); // (꼭 fixed 를 붙여 자리수 넘어가면 0으로 채우..

[실전 압축 알고리즘] - C/C++ 문자 숫자 변환

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. C 스타일 변환 함수 변환 모습 설명 문자열 -> 숫자 #incldue (stdlib.h) 정수형 atoi, atol, atoll 실수형 atof int atoi (const char* str); "4" -> 4 "123" -> 123 문자열을 숫자로 변환해준다. 다른 형으로는 atof, atol, atoll 이 있다. 숫자 -> 문자열 #incldue (stdlib.h) char * itoa ( int value, char * str, int base ); 5 -> "5" 123 -> "123" value를 base진법으로 변환하여 str에 저장 비표준 함수이기 때문에 MS VS 에서만 가능 표준 호환 대안은 sprintf 일 수 있습니다 ...

[실전 압축 알고리즘] - 비트 연산

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. Bitwise Operators 연산자 예시 계산 쉬프트 과정 (2진법) 결과 활용 >1 5>>2 12 >> 2 2 * 2^-1 5 * 2^-2 12 * 2^-3 00010 -> 00001 00101 -> 00001 01100 -> 00011 1 1 3 2의 -n승 & (AND) 2 & 1 3 & 1 10 & 01 -> 00 11 & 01 -> 01 0 1 짝수 = 0 홀수 = 1 | (OR) 1 | 1 2 | 1 3 | 1 01 | 01 -> 01 10 | 01 -> 11 11 | 01 -> 11 1 3 3 방문 check ^ (XOR) 5 ^ 6 1 ^ 1 2 ^ 1 00101 ^ 00110 -> 00011 01 ^ 01 -> 00 10 ^..

[실전 압축 알고리즘] - C++ 입출력

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 입출력 언어 입력 출력 C++ scanf / cin printf / cout Java Scanner System.out Python input print C++ #define _CRT_SECURE_NO_WARNINGS #include int main() { int n; scanf("%d", &n); printf("%d", n); return 0; } #define _CRT_SECURE_NO_WARNINGS는 Visual Studio에서만 넣어주면 됩니다. scanf는 나온 지 오래된 함수라 입력 값의 길이를 설정할 수가 없습니다. 따라서 보안에 취약하기 때문에 Visual Studio에서는 사용하지 말라는 경고가 출력되고 컴파일 에러가 발생하는..

[실전 압축 알고리즘] - 시간, 공간 복잡도

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. C++ 기준으로 작성하였습니다. 시간 복잡도 작동하는 알고리즘의 수행시간을 정량화하는 것을 의미합니다. 시간 복잡도를 표기하기 위한 방법에 빅-오, 빅-오메가, 세타 등이 있으며 일반적으로 최악의 케이스(Worst Case)를 가정하고 계산 하므로 빅-오 표기법을 빅오 표기법은 최고차항의 차수만을 표기합니다. N^3 + N^2 + N + 1 = O(N^3) 숫자 빨리 읽기 0을 3개씩 묶어서 숫자 단위를 빠르게 파악하도록 암기합니다. 숫자 읽기 1'000 천 1'000'000 백만 1'000'000'000 10억 배열을 만들 때 arr[10000000] 보다는 arr[10'000'000] 이런식으로 작은 따옴표를 넣어서 가독성을 높이고 실수를 ..