SLENDER ANKLES's 개발블로그

아 정말 복잡하고 더럽고 어려운 문제.

내가 푼 방법이 위와 같을 수도.

문제정리)

여러 개의 문자열이 주어지는데, 이 중 오버랩 조건(한 문자열의 끝과 다른 문자의 시작점 사이가 같은 것)으로 이어서 그 길이가 가장 최소인 문자열의 길이를 찾아라.

문제를 이해하는데도 오래 걸렸고, 풀다가 잘 못 이해한 부분 때문에도 멘붕

테스트케이스가 주어지지 않으면 풀기 정말 까다로운 문제인거 같다.

문제 풀이)

문자열들이 일렬로 나열되는 모든 경우의 수를 구해야 한다. 한마디로 완전탐색 후 조건에 맞추어 문자열을 정리해야한다.

문제를 이해하면서부터 풀이에 대한 몇 가지 이슈에 대해서 정리해보면

- 주어진 원소들을 이용하여 겹침없이 만들 수 있는 모든 경우의 수를 구해야 한다.

- 두 문자열이 overlap 되는 부분을 어떻게 비교 할지에 대해서

    => 1) 앞 쪽 단어(누적처리된 문자열)를 순회하며 뒤 쪽 단어의 첫 번째 문자와 일치하는 것을 찾는다.

        2) 찾았으면 찾아진 앞쪽단어(누적처리된 문자열)의 인덱스부터 뒤쪽단어와 1대1비교한다.

            -- 달라지는 게 있다면 실패

            -- 달라지는 게 없이 끝까지 간다면 해당 문자열을 더 해주어 갱신해준다.

   마지막에 총 합쳐진 문자열의 길이를 통해 최소값을 갱신해주도록 한다.

- 문자열 각 번째와 그 다음번째를 비교하는 것이 아닌 앞까지의 연산이 완료된 축적된 문자열과 그 다음 문자열의 비교를 해야되는 함정이 있는 문제 ㅜㅜ 

암걸리는 문제다.

문제정리)

1900년부터 1900 + n - 1년 12월 31일까지의 매월 13일의 요일 분포를 {토,일,월,화,수,목,금}으로 출력하는 문제이다.

1900년 1월 1일은 월요일이다.

윤년을 고려해서 답을 구해야한다. 

문제풀이)

처음에는 어떤식으로 접근해야 하나 고민했다. 

맨처음은 년, 월, 일을 다차원배열로 표현해야 하나? 생각했는데 13일의 요일분포를 구하는데는 적절하지 않는 방법이라고 생각.

그 다음은 전체일수를 하나의 배열로 표현하여 각 날짜들을 count하는 방법으로 생각했다. 

이 방법이 옳은 방법이라고 생각했다. 

년 -> 월 -> 일 을 1차원 배열의 날짜로 표현하기 위해서는 

3중 for문으로 표현하되 각 월과 일의 조건을 몇 개 넣어주면 되겠다고 생각했다. 

그리고 결과적으로 구해야하는 요일 분포를 현재까지의 결과 일수에서 % 7 하면

0은 월요일, 1은 화요일, 2는 수요일, 3은 목요일, 4는 금요일, 5는 토요일, 6은 일요일로

표현가능하여 요일분포배열에 담아서 구현했다. 

윤년을 구하는 방법은 인터넷을 통해서 정확하게 이해했다. 

4로 나누어지는 년도, 100으로 나누어지는 곳은 윤년 아님, 그러나 400으로 나누어지면 윤년

이 조건을 if문으로 적당히 걸어주어서 윤년정보를 적용시켰다. 

다차원 배열을 다루는 부분이 쉬운 줄 알았는데 의외로 조금 시간이 걸렸다.

더군다나 마지막에 엄청난 오류를 범해서 틀린 것이 있었다. 

이 문제는 다차원배열을 이해하고 활용하는데 아주 좋은 문제이기 때문에 몇 번이고 다시 풀어볼 필요가 있을 것 같다.

문제정리)

5 * 5배열에서 어망을 투하해서 가장 많은 수확을 할 수 있는 범위와 그 값을 구하는 문제였다. 

문제풀이)

우선 5*5배열이기 때문에 어림잡아 5 * 5 * 5 * 5 * 5 * 5 이하의 순회를 하게 되는데 , 

15625번? 물론 이 것보다 훨씬 적게 반복문을 수행하는데, 어쨋든 1억번까지 수행하지 않으므로 1초안에 무조건 해결 가능하다. 그렇기 때문에 완전탐색으로 풀면 된다. 

배열의 인덱스 x, y에 접근하게 되면 그 점을 기준으로 오른쪽으로 아래쪽으로 사각형을 모두 만들어보면서 답을 구했다. 

1번째 for문과 2번째 for문으로 사각형의 범위를 잡고

3번째 for문과 4번째 for문으로 영역에 속하는 합을 구했다. 

사각형의 범위는 

세로는 1부터 ~ 6 - 현재점x   까지의 범위를 

가로는 1부터 ~ 6 - 현재점y   까지의 범위를 잡았다.

그 안에 속한 사각형의 어획량을 계산하는 부분에서는

현재점부터 어획량의 범위까지의 길이까지를 반복문을 통해 잡아주었다. 

이 것은 말로 설명하기보다 몇 번이고 다시 풀어보면서 머리속으로 정리해주어야 하는 것 같다.

또 하나 나를 애먹인건 

정사각형과 직사각형의 차이였다.

중고등학교 때 잘못된 지식을 가지고 있어서 애를 먹었다. 

-직사각형은 4각이 90도이고 마주보는 한쌍의 길이가 같은 사각형이다. 

-정사각형은 4각이 90도이고 마주보는 두쌍의 길이가 모두 같은 사각형이다.

직사각형은 무조건 마주보는 한쌍의 길이만 같아야 되는 줄 알았다. 

인터넷을 찾아보니 직사각형은 정사각형에 포함되는 사각형이란다. 

처음에 방향을 잘 못 잡아서 다소 몇 시간 헤맸다.

실전에서 이런 문제를 만나도 잘 풀기위해서는 어떤식의 사고 방식을 가져야 할지 모르겠다.

가로 * 세로 크기의 크기의 색종이에 

가로, 세로 마다 줄이 쳐져 있고, (배열이라는 소리)

자르는 인덱스가 주어진다. 

자르는 색종이들중의 크기 중 가장 최대의 것을 찾는 문제이다. 

문제풀이)

처음에는 장애물을 주어지고 dfs를 수행 할려고 했다. 세 시간을 생각해보아도 명확하게 코딩 할 수 있는 방법이

떠오르지 않았다. 

사각형의 넓이에 범위에 대해서 부분, 부분 나눌 수 있는 방법에 대 해서 생각 해보았다. 

좋은 아이디어가 발견됐다. 

예제를 통해서 설명하면

가로 10, 세로 8

가로 커팅이 2, 3번째 선이라고 입력으로 들어 오고,

세로 커팅이 4번째 선이라고 입력으로 들어온다면,

잘린 세로의 선들을 나열하면 0~2까지 선, 2~3까지의 선, 3~8까지의 선 이렇게 3개다.

잘린 가로의 선들을 나열하면 0~4까지 선, 4~10까지의 선 이렇게 2개다.

이 모든 선들을 가로 * 세로 구하면 모든 사각형의 넓이를 구할 수 있게 되는 것이다.

즉!

결국 잘린 선 중에 가로의 최대 길이,

세로의 최대 길이를 구해서 둘이 곱해주면 최대값을 구할 수 있다는 것이다.

간단하게 생각해서 각각의 사각형의 가로 세로 길이를 구해서 넓이를 구하려고 하다보면 내가 푼 아이디어까지 도달할 수 있게 된다.