열심히해보겠씁니다

수열의 어디서부터 출발해서 어떤 것을 골라야 가장 긴 증가하는 수열이 될까를 판단해야 한다. 이를 위해 위치별로 시작해보는 일도 필요하고, 해당 위치에서 가장 긴 수열은 무엇인지도 판단해야한다. 1. 정해진 위치에서 가장 긴 수열 2. 최적화 이 문제는 DFS로 접근했다. 예시의 경우로 보면, 10 20 10 30 20 50 의 index를 1, 2, 3, 4, 5, 6 으로 둔다. 그리고 index별로 차례대로 DFS를 수행하여 조건에 맞는 가장 긴 수열을 찾는다. 이 때도 길 찾기와 마찬가지로 분기별로 나뉘어서 수행하며 가장 길게 가는 수열을 찾아야 한다. int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a..

꽃을 하나 피우기 위해서는 위 그림의 (b) 모양 처럼 + 형태의 땅을 모두 빌려야하므로 최소 5칸을 빌려야한다. 거기에 꽃잎이 화단밖으로 나가면 죽고(?) 다른 꽃잎과 만나도 죽는다(개복치냐) 두 가지의 접근 방식이 필요하다. 하나는 특정 위치에 씨앗을 심을 경우 5칸의 비용이 얼마인지를 알아야한다. 또 하나는 꽃잎이 죽지 않는지를 판단해야한다. 나의 경우 (쓸데없이) 각 위치에서 비용이 얼마인지를 먼저 저장해놓고 그것을 토대로 Depth-First Search(DFS) 방식으로 접근한다. #include #include #include #include using namespace std; int Garden[11][11]; int Cost[11][11]; int Visited[11][11]; int ..

해당 문제는 Breadth-first-search(BFS) 방식으로 풀었다. 문제는 c언어로 해결하려할 시 BFS에 거의 필수적인 queue 를 구현해야한다는 것이었다. 근데 거기까진 아직 안배우고 익혀보지 않았기 때문에 우선 문제풀이를 위해 c++ 의 라이브러리를 이용해 문제 해결에 집중했다. BFS 방식은 너비우선탐색으로 가장 기초적인 탐색법으로 많은 경우에 사용된다. 특히 가장 빨리 탈출하는 문제에 특화되어 있는데, 내가 서있는 위치 기준으로 몇 번만에 목표지점까지 이동할 수 있느냐를 구하는데 아주 유용하다. BFS 의 작동 방식은 위의 그림과 같다. 현재 위치 기준으로, 과거에 방문하지 않은 곳, 갈 수 있는 곳을 기준으로 점차 넓혀가며 탐색한다. 이 때도 2가지 방식이 있는데, 만약 내가 END..

백준 1747번 소수 & 팰린드롬 특정 숫자를 입력할 시(1

1. 문제의 접근 수가 최대 500,000개 주어지고, 각 정수의 절대값은 4,000을 넘지 않기 때문에 최대의 경우로 계산해도 20억이 가능하므로 배열은 Integer type으로 만든다. #include #include #include #define INF 987654321 struct st { int tag; int fre; }Fre[4000 + 4000 + 1] = { {0,0} }; 하지만 여기서 일반 배열로 선언하기보다 최빈값을 구하기 위해서 숫자와 빈도를 기록하는 구조체를 선언한다. tag 는 해당 구조체가 저장하는 숫자이고, fre 는 몇 번 나왔는지 기록하기 위한 수이다. 배열의 개수 4000+4000+1은 정수의 절대값이 4000이 넘지 않기 때문에 -4000~-1, 1~4000 개의 ..

*주의 - 개인적으로 학습한 내용이므로 틀린 부분을 알려주시면 진심으로 감사드리겠습니다. 1. 선행처리기 선행처리기는 compiler 가 본격적으로 compile 하기 전에 header file과 source 파일을 미리 읽어와 선언해주고, 선행처리기의 연산자로 사용한 문장들을 미리 처리해준다. 이게 무슨 소용이냐 싶겠지만, compiler 는 딱 주어진 문장만 compile하여 assembly 언어로 바꿔주기 때문에 compiler가 주어진 문장을 번역할 수 있게 preprocessor 가 준비해준다고 생각하면 편하다. 선행처리기의 연산자들은 #을 사용하여 표기한다. 가장 먼저 우리가 계속해서 사용해오던 #include가 있다. 1-1. #include include 는 preprocessor에게 해당..

*주의 - 개인적으로 학습한 내용이므로 틀린 부분이 있으면 알려주시면 진심으로 감사드리겠습니다. 1. 비트 연산자 비트 연산자는 이름 그대로 비트 별로 계산을 하겠다는 뜻이다. integer type 의 경우 4B를 차지하고 있고, 비트별로 2의 배수를 뜻한다. 예로 10진수로 24는 2진수로 11000(2) 처럼 각 bit 별로 0 혹은 1로 표시한다. 이걸 bit 별로 0 혹은 1로 바꾸고 싶을 때 쓰는 것이 비트 연산자이다. 비트 연산자에는 & ^ | > ~ 가 있다. &과 ^ 과 | 과 ~는 이미 우리가 논리 회로에서 본 적이 있다. &는 and 연산으로 둘 다 1이어야 결과가 1이 나왔었고, ^는 xor 연산으로 비교 대상 둘이 서로 달라야 1이 나왔다. 또한 |는 or 연산으로 둘 중 하나만 ..

*주의 - 혼자 학습한 내용이므로 틀릴 수 있으니 알려주시면 진심으로 감사드리겠습니다. 1. 포인터의 개념 포인터는 C언어의 가장 어려운 부분이면서 하드웨어에 직접 접근이 가능한 장점을 가지고 있는 부분이기도 하다. 여기서 하드웨어는 메모리 영역을 뜻하며, 메모리의 특정 부분의 주소 값을 알고 직접 찾아가서 값을 건드릴 수 있다. 포인터는 주소값을 갖고 있으므로 크기는 4B로 정해져 있다. 배열 타입을 가리키는 포인터 변수도 4B의 크기를 가진다. 포인터의 선언은 변수를 선언하는 것과 동일하지만, type과 idenfier 사이에 * 기호를 입력하여 선언한다. 예시) int * a; char * b[4]; struct tag * c; 주의해야 할 것은 우리가 프로그램을 실행할 때 접근할 수 없는 메모리 ..

*주의 - 혼자 학습한 내용이므로 틀린 내용이 있을 수 있으니 알려주시면 진심으로 감사드리겠습니다. 1. 구조체(Structure) 같은 타입의 데이터가 여러 개 모여있는 것을 배열이라고 부른다. 만약 다른 타입의 데이터를 같은 곳에 묶어 여러개를 선언하고 싶다면 어떻게 해야할까? 이때 쓰이는 개념이 구조체이다. 내가 원하는 타입대로 만드는 덩어리이므로 전역변수로 선언을 먼저 해야 어디서든 쓸 수 있다. 기본적인 문법은 다음과 같다. #include struct Tag1{ int a; char b[20]; double c; }; struct Tag2{ int a; char c[20]; double b; }x={1, "HELLO~", 2.14}; int main(){ struct Tag1 y= {1,"HI..

*주의 - 혼자 학습하여 틀린 내용이 있을 수 있으니 알려주시면 진심으로 감사드리겠습니다. 1. 변수 변수의 종류는 2가지로, 전역변수(Global variables)와 지역변수(Local variables)로 이루어져있다. 둘의 구분은 선언시의 위치이며, 특정 블럭 {} 안에 선언하면 지역변수라고 부르며 그 외는 지역변수라고 부른다. 지역 변수는 기본적으로 블럭 안에서만 작동하며 지역변수로 선언하기 전에 이미 선언될 경우, 먼저 선언된 변수가 블럭을 벗어날 동안 보이지 않는 상태(invisible)가 된다. 변수는 앞선 페이지에서 언급한 것처럼 선언이 반드시 필요하며, 동시에 초기화도 진행할 수 있다. 초기화를 하지 않고 선언만할 시, 지역변수는 원래 메모리에 저장되어있던 쓰레기값(garbage)을 가..