대엉코딩

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

<코드>

* 큐(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입니다.)

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

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

<풀이>

<코드>

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의 배수여야 한다는 것.

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

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

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

<필기>

<코드>

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

-문제를 읽어보고 예시를 한번 그려보았더니 로프가 버틸 수 있는 중량의 

-입력 값이 어떻게 주어지냐에 따라서 들 수 있는 최대 무게가 많이 달라질 수 있는 문제였습니다.

-몇개의 로프를 선택 하던 간에 그 로프들로 들 수 있는 중량의 최대 무게는

- (로프 중 가장적은 무게를 들수 있는 중량) * (로프의 개수) 입니다.

-로프  n개 선택 한다고 치면 큰 무게를 들 수 있는 로프를 두고 적은 무게를 들 수 있는 로프를 선택할 이유 가 없으므로

-큰것들 부터 n개를 선택 해 가면서 반복문을 1회 돌면서 그 값들을 비교하면 되는 문제 였습니다.

- 내림차순으로 정렬 후 앞에서 부터 로프의 개수를 하나씩 늘려가며 최대값만 저장 후 출력하였습니다.

<필기>

<코드>

동전 문제입니다.

처음에 입력조건을 꼼꼼하게 파악하지 않아 다른 경우의 수 를 생각 하다가

다시 문제를 보니 생각보다 훨씬 쉬운 문제였습니다..

필기노트에 기재되어 있습니다.

<필기>

<코드>

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

그리디 알고리즘 기본문제 인 것 같다.

대기시간이 최소로 되게끔( 대기시간의 총합)

어쩌면 형평성 측면에서는 잘못되었다고도 할 수 있겠다..... 오직 효율성 만을.....

문제자체는 간단하고 쉽습니다.

오름차순 정렬을 시킨후 이전까지 걸렸던 시간과 그 사람이 걸리는 시간을 합을 더해서 

총 결과(합) 에 더해주고 그 자신이 걸리는 시간이 들어있던 배열에 그 자신을 포함한 걸린 시간을 넣어주면 되겠습니다.

<필기>

<코드>