대엉코딩

https://www.acmicpc.net/problem/1541

-입력, 출력은 문제를 통해 쉽게 파악가능하고

- 이제 입력을 어떻게 받아와서 이론적으로는 -가 나오면 괄호를 열고

- 다음 -가 오기전에 괄호를 닫는 것인데

- 구현을 할 때 -가 처음나오면 check를 하고 tmp로 다음 연산부호가 오기전에 더해주고(string 즉 한글자씩이므로)

- 그다음부터는 그냥 -부호 붙은 수는 +붙은 수 그냥 다 빼주면 됩니다.

- 왜냐? 괄호는 무제한 이니까.....! 자신이 +면 가장 가까운곳에있는 -와 묶어서 빼면 되니깐....

<필기>

<코드>

https://www.acmicpc.net/problem/14502

이차원 배열을 통해서 map을 그리고 벽을 3개만 칠 수 있는데 벽을 3개를

쳤을 때 안전영역(바이러스가 퍼지지않는) 을 최대로 만들어 그 최대값을 출력하는 문제입니다.

초반에 어떠한 규칙을 세워야 좋을까 생각이 들었지만 너무 경우의 수가 많아 딱히

적용되는 규칙을 찾기 힘들어 모든 경우의 수를 다 세우고 그 경우의 수에 따라서 안전영역의 값을

구해 봐야되나....? 라는 생각을 한후 그럴경우 입력값의 조건들이 너무 크면 안되기 때문에 그를

확인해보니 (3<=N.M<=8) 이라 작은값임을 확인하고 그로 방향을 잡아 풀었습니다.

저는 [10][10] 배열을 만들어 index 0과9는 1로 채워서 벽같은 느낌을 주었습니다(바이러스가 퍼지지 못하게)

물론  조건문에 index를 걸어도 되지만 귀찮아서.....

아 그리고 벽이 세워질 수 있는 지역은 좌표를 구조체로 설정하여

벡터(vector)에다가 모두 넣은 다음 그 벡터에서 3개씩을 골라서 그 3개에 벽이 세워졌을 때 안전구역을 구하였습니다.

bfs를 통해서 -- 더이상 바이러스가 퍼질 구역이 없어서 큐가 비어있게 될경우 탐색을 멈춤

3중 반복문 이용(완전탐색) -- 이 과정에서 조건수정을 하느라고 시간이 좀 걸렸습니다.

<코드>

* 벡터(Vector) 란 ?

- 배열의 확장 느낌으로서 시퀀스 컨테이너의 대표적인 자료구조이다.

-  동적배열과 유사하다

- 자료들(data)가 구조적으로 인접한 위치에 있기 때문에 접근이 쉽고 메모리를 효율적으로 관리가능하다

- 배열과 같이 index를 통한 요소(data) 접근이 가능하다 .(매우 편리, 접근이 용이)

- 만약 맨뒤에 삽입이 아닌 맨 앞이나 중간, 임의의 위치 등에 삽입을 하려고 하는 경우 다른 요소들도

  재조정을 해야 하기 때문에 느리다 (비 효율적)

- 임의의 위치에 삽입, 삭제 등이 많이 일어나는 경우 벡터보다는 리스트를 활용하는것이 효과적이다.

* 벡터 ADT

- at( x ) (index가 x인 위치의 자료형 리턴)

- set(int x, object o) (index x의 위치에 o라는 객체 assign)

- insert(int i, object o) (index i의 위체서 o라는 객체 삽입)

- erase(int i) (index i에 있는 객체 삭제)

- size() (vector 의 사이즈 리턴)

- empty() (비어있는지 확인 -bool)

- push_back(object o) (vector 맨 끝에 삽입)

* ADT 시간복잡도 분석

- at(i),  set(i,0)   ----> O(1) ( vector는 index로 접근 가능 하므로 at, set은 모두 직접 접근하여 O(1) 타임에 가능하다.

- insert(i,o)  ----> O(n) (임의의위치 i에 자료를 삽입하는 경우 원래의 i위치 부터 끝까지 있던 자료들을 모두 한칸씩 뒤로 밀린다.)

-erase(i)  ----> O(n) (역시 비슷한 느낌입니다 ---앞으로 땡겨줘야함 )

* 벡터 활용의 예

- 정렬된 객체들의 집합들을 관리 해야할 때

* 벡터의 구현

<잘못된 부분이 있을 수 있습니다>

<알려주시면 수정 하겠습니다>

기본 크기를 64(index) 로 하고 만약 입력을 받다가 이크기를 넘어가게 되면

배열의 크기를 두배로 늘리고 기존의 자료구조들을 모두 옮기는 식으로 구현하였습니다.

* 큐(queue) 란 ?

- FIFO(First In Fisrt Out)

- 편하게 생각해보면 맛집에 줄 서있는 사람들을 떠올리면 될것이다.

  (먼저 줄을 선 사람 순서대로 식당에 들어간다.)

- 그외에 번호표, 버퍼(buffer) 도 같은 개념이라고 보시면 되겠네요 !

* 큐의 연산

- 삽입, 삭제, 비어있는지 확인, 맨 앞 (front) 확인,끝(rear) 확인 크기 등의 연산이 있다.

- 객체 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : enqueue(x)

           dequeue()

           front()              

           rear()

           peek() -> front에 위치한 데이터 확인

           empty()

- 시간 복잡도: (배열을 통한 구현으로 생각해보겠습니다.)

                   enqueue의 경우 배열 맨 끝에 추가하면 됩니다. O(1)

                   dequeue의 경우 배열의 앞에서 빼고 다른 요소들을 모두 하나씩 당기는 방식으로 구현할 경우 O(n)

                                         (이경우 front는 무조건 index가 0일 것이므로 따로 index변수를 관리 할 필요가 없겠죠)

                                         배열의 앞에서 빼고 front index를 따로 관리하여 +1만 해주는 경우 O(1) - 효율적

                   그 외 front(), rear(), peek() 등의 연산들은 index를 관리해줄 경우 모두 O(1) 타임 이겠죠?

* 큐 구현상의 문제점

                   만약 index를( 따로 front와 rear 를 가리키는) 관리해주는 방식으로  (효율적)

                   그럴 경우 배열의 크기는 정해져 있다는 것을 생각 해보면 계속 enqueue와 dequeue 작업을 수행하면

                   계속 뒤로 밀려지게 되다가 결국 배열의 크기를 넘어 가게 되면 오류가 발생하게 될 것 입니다.

                   이 때는 환형 배열을 이용 하면 이 방식의 문제를 해결할 수 있습니다.

                   만약 자료가 많아서 배열을 모두 채울경우 배열의 크기를 두배로 늘려서 다시 모든 요소들을 새로운

                   큰 크기의 배열로 옮겨주고 수행해야 하는 경우 enqueue 는 O(n) 타임이 걸릴 것입니다.

                   만약 연결리스트(링크드 리스트)로 구현할 경우 이러한 문제는 해결 할 수 있을것입니다.

                   하지만 링크드 리스트로 구현할 경우 코드상의 즉 런타임시간에 동적할당을 자주 해야 할것이고

                   이로인해 성능이 배열을 통해 구현한 순환큐 보다는 성능이 떨어질 수도 있습니다.

                   그러므로 만약 큐(자료)의 크기가 어느정도 예측이 가능할 경우 배열을 통한 순환큐가 

                   더 적절한 상황이 나타날 수 있습니다.

* 큐 활용의 예

(큐의 특성을 생각해본다면 매우 많겠죠???)

- 프린트기

- 너비우선탐색(bfs)

- 은행업무

- 그외 등등

* 큐의 구현

< 배열 이용한 구현>

https://www.acmicpc.net/problem/11724

연결 요소를 구하는 문제 입니다..

연결요소의 정확한 정의가 나와있지 않아 감은 대충 왔으나 검색을 한번 해보고 문제를 풀었습니다.

문제를 분석 하고는 dfs로 푸는 것이 편하겠다 싶어 dfs로 풀었습니다.

정점 index 순서대로 dfs를 도는데 이미 방문한 정점이면 dfs를 돌지 않습니다.

그리고 저는 처음에 아무것도 연결되지 않은 정점은 연결요소로 count를 하지 않는 다고 생각했으나

그럴 경우도 연결요소로 count를 하셔야 합니다 (즉 , 입력(6, 0) ---정점만 6개 일경우 결과값은 6입니다.)

은근 저와같은 생각을 하신분들이 있으시리라 생각합니다.....

그 외에는 쉬운 문제입니다.

<풀이>

<코드>

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다. 

https://www.acmicpc.net/problem/2875

- 흠... 문제 이해는 어렵지 않습니다만

- 일단 비율에 맞춰서 팀을 구성하고 남은 인원을 먼저 인턴쉽에 보내는 느낌(K에서 뺀다..)

-그리고 그럼에도 불구하고 인턴쉽에 인원을 더 보내야 할때는 팀에서 하나씩 빼는 수 밖에 없다.

-먼저 방향을 정하고 코드를 짰는데... 계속 틀렸습니다. 가 뜨길래 

-반례를 생각 해보다가 666을 했을때 2팀이 나와야 되는데 1팀이 결과로 나오는 것이였습니다.

-그래서 차근차근 계산해보니 코드를 잘 못 짰었다죠......

(말하자면 1명이 부족해도 2명이 부족해도 1팀이 빠져서 -1을 해놓았는데 3명이 부족할때는 K/3이 1이되면서

총 -2가 되는 코드를 짜놓고 있었던 것.....)

<필기>

<코드

>

https://www.acmicpc.net/problem/10610

- 일단 정수론을 저도 잘하지 않았지만 아주 기본인 3의배수 이려면 각자리 숫자의 합이 3의 배수여야 한다는 것.

- 그리고 출력 부분에 있어서 그리디 를 통해서 큰수부터 내림 차순으로 출력하면 된다는 것

- 그리고 입력은 매우 큰 숫자일 수 있으므로 문자열을 이용해야 한다는 것 

(정수 형을 나타내는 기본 자료형으로는 입력을 받을 수 없다.)

<필기>

<코드>