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개다.

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

즉!

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

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

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

문제정리)

스위치개수와 현재 스위치 상태가 입력

학생수가 입력되고 

각 학생마다 학생성별, 학생번호가 입력됨

남자와 같은 경우에는 

학생번호의 배수의 인덱스를 가지는 스위치를 상태 전환

여자와 같은 경우에는

학생번호를 기준으로 좌우 대칭 되는 최대 범위만큼 스위치를 상태 전환

문제 풀이)

남학생은 반복문 수행하면서 자신의 인덱스로 나누어서 나머지가 0이면 그러니까 나누어 떨어지는 인덱스를

상태 변환시켜주면 된다. (i % 학생번호 == 0)

여학생이 조금 당황 스러웠는데,

좌우 대칭의 범위를 count변수로 관리하면서 하나씩 늘려나가면서 대칭되면 while문을 계속 수행하게 했고, 

대칭 되지 않으면 while문을 빠져나오게했다.

한 가지 예외는 범위를 늘리다가 할당된 배열의 범위를 넘어서는 경우가 있을 것이라고 판단했다. 

좌우대칭범위를 설정하는데, (count가 학생번호보다 커지면) 배열 인덱스가 음수가 되기 때문에 종료해야 한다.

count가 (전체 스위치 개수 - 학생번호보다 커지면) 할당된 스위치 개수 이상의 인덱스에 접근하기 때문에 종료해야 한다.

이 부분만 잘 처리해주면 크게 문제 없이 수행하는 코드가 완성

문제가 길다고 어려운 것은 아니다. 차근차근 읽어보고 해결책을 찾아보면

대개 긴 문제들이 오히려 쉬울 가능성이 높다는 것을 느낀다.

악보 (1<=N<=10000)개, 각 악 보당 비트(0<=bi<=120)의 정보가 주어진다. 

처음에는 2차원 배열을 쓰는 문제인가 생각하다가 

손으로 그려보면서 풀어보니 1차원 배열로 푸는 것이 답을 구하는데 더 좋다고 판단했다. 

1차원 배열의 범위는 10000 * 120 => 1200000

백이십만개 정도면 된다. 

악보의 비트 정보가 주어지면 

그 해당 배열에 악보넘버를 저장해주는 식으로 입력을 구성했다. 

for(악보범위 i)

while()

       arr[전역변수로 관리하는 인덱스, 곧 시간] = i(악보번호)

로 저장해주면 

ques가 날라왔을 때(시간) 바로 인덱스로 접근해서 답을 도출해내면 된다.

더블릿_더큰

쫌 고민을 많이 했다. 

우선 문제를 간단히 정리하자면

1<= x <= 999999 의 숫자가 입력되면

이 수에 포함되어 있는 숫자들을 이용하여 만든 수들 중에 입력된 수보다 큰 최소수를 구하는 문제이다.

다소 문제 설명이 어렵지만,

156을 보자면 156이 포함되어 있는, 156의 자리수로 만들 수 있는 숫자는

156, 165, 516, 561, 615, 651 등등이 있다. 

이 중 입력된 156보다 큰 최소 수는 165이다.

문제 풀이)

처음에는 어떻게 풀어야 되나 굉장히 고민을 많이 했다. 156의 자리수를 가지고 만들 수 있는 수들을 다 구한다음에 정렬하고, 

입력받은 수 보다 큰 숫자를 출력해야 되나? 가 첫 번째 떠오른 방법이었다. 일단 1~999999이기 때문에 숫자를 만드는 방법에 대해서 어려운 점이 있었다.

한번 더 생각해보니까 

1~999999까지 for문을 돌리면서 조건을 만족시키는 숫자를 캐치해내면 되겠다고 생각했다. 

예를 들어 156이 입력되면

1) 156~999999까지 반복문을 수행한다.

2) 각 숫자들마다 자리 수에 있는 숫자들을 판별하여 1,5,6에 부합한지를 체크한다.

3) 만약 조건에 부합하면 바로 출력하고 프로그램을 끝낸다.

4) 조건에 부합하지 않으면 0을 출력한다.

더블릿_빙고

1)나의 빙고판을 입력받는다.

2)사회자가 부르는 번호를 입력받는다.

3) 사회자가 입력되는 순서대로 내 빙고를 체크해준다.

** 빙고를 판별하는 것은 

// 대각선

[x][y] 좌표가 x == y일때와, x + y = 6일 때

// 가로

[x][y] 좌표가 x는 고정시키고 y를 1~5까지 순회

// 세로

[x][y]좌표가 y는 고정시키고 x를 1~5까지 순회

더블릿_wrap around

정말 느낀점이 많은 문제이다.

10*10 배열이 주어지고 상, 하, 좌, 우, 대각선의 5개의 합을 도출해내는 문제였다. 

정말 쉽다고 생각했다. 

현재 인덱스에서 +0, +1, +2, +3, +4 해주면서 그 값을 %10해주면 10을 넘어가도 인덱스가 순환할 수 있게 되어

원하는 답을 구할 수 있게 된다. 

그런데 내가 음수가 되는 부분에 대해서 예외처리를 안해주었다. ㅜㅜ 근데 황당한 것은 비주얼 스튜디오에서는 쓰레기값에 대한 처리가 리눅스와 달라서 답이 제대로 나오는데 제출되는 컴파일러에서는 그렇지 않아서 문제점을 찾는데 애를 먹었다.

다시 한 번 말하지만 로직을 짜기 전에 한 번 손으로 그려보고 맞춰보는 형태가 정말 중요하다는 것을 알았다. 

결국 인덱스를 좌로 가거나 상으로 가는 연산에서는 행에서 -1, -2, -3, -4해줄 때 원래 인덱스에서 10을 더해준다음에 연산을 수행해주면 아무 문제가 없다. 

더블릿_폭탄게임

행, 열 정보가 주어진다. A는 폭탄을 어느 한점에 숨겨둔다.

B는 폭탄을 떨어뜨려 보면서 A가 놓은 폭탄의 위치를 알아맞추는 문제였다.

처음은 굉장히 간단한 문제라고 생각하면서 풀어보다가 낭패를 맛 보았따.

반드시 예제의 테스트케이스를 손으로 돌려보면서 내 로직이 정확한 답을 내놓는지를 검사해봐야

시간 낭비를 줄일 수 있다고 깨달았다. 

처음에는 그냥 간단히 폭탄이 떨어지는 위치를 bool 배열을 이용해서 true false를 갱신해준 다음에 true인 배열의 개수를 통해

답이 도출되는 줄 알았따. 

그런데 폭탄을 떨어뜨릴 때마다 가장 최신의 정보를 가지고 점점 폭탄의 범위를 좁혀나가야 하는 문제였다. 

문제를 풀면서 몇 가지 이슈에 대해서 설명해 보자면

1) 폭탄의 범위를 설정하는 부분이다. 

어느 한 점 x, y가 주어지고 폭탄의 범위는 p(홀수)가 주어진다. 

손으로 대충 그려보니 폭탄의 범위를 설정해주기 위해서는

x - (p - 1) / 2  ~  x + (p - 1)/2 로 설정

y - (p - 1)/ 2  ~ y + (p - 1)/2로 설정

해주면 정확한 정사각형의 범위의 폭탄을 설정해줄 수 있다. 

그리고 폭탄의 위치는 단 한개이므로 폭탄이 떨어질 때마다 그 값들을 점차 증가시켜주면서 

마지막에 가장 많이 겹치는 부분을 답으로 도출해주었더니 답을 구할 수 있었다.

더블릿_계단오르기

문제정리) 

계단은 한 칸 오를 수 있고, 두 칸을 오를 수 있다. 

입력받은 계단까지 오르는 경우의 수를 출력하라

라는 것이 문제였다.

풀이정리)

재귀함수를 작성하는 것에 대한 좋은 연습문제였던 거 같다. 

항상 재귀함수에 대해서 정확히 어떤 메커니즘을 가지는 것인가에 대해서 많은 생각을 해보게 된다. 

좀 더 연습을 해야 겠지만 많은 문제를 풀어보면서 재귀에 대해서 알 필요가 있을 것 같다.

여태껏 느낀 것은 좋은 점화식을 통해서 답을 구해 낼 수 있다는 것이다. 

입력의 4번째 계단까지 오르는 경우의 수를 간단히 생각해보면

4번째 계단까지 오르는 경우의 수는 3칸까지 올라와서 1칸을 오르는 경우와 2칸까지 올라와서 2칸을 오르는 경우의 합이다.

대충 손으로 그려봐도 정확한 점화식을 구하기가 어려웠는데 이 부분에 대해서는 좀 더 연습을 통해 명확한 매커니즘을 

구축해야 될 필요가 있을 것 같다. 

너무 전형적인 문제여서 생각도 하기 전에 답이 떠오르는 문제였다. 

더블릿_비트패턴

재귀함수를 사용하는 문제에서는 언제나 어려움을 겪는다. 재귀적인 탐색방법에 대한 기본적인 개념이 부족한 듯하다.

재귀함수의 탈출 조건은 1을 k번만큼 썼을 때 출력하고 끝내게 했다.

아니면 현재의 인덱스가 n보다 크게 되면 탈출하게 했다. 

그 외의 상황에서는 1또는0을 바꾸어가면서 재귀적인 수행을 하게끔 코딩해줬다.

풀고 나서도 어떻게 답을 도출해냈는지에 대해서 명확하게 설명을 하기가 애매한 상황이다. 

이 부분은 반드시 다시 짚고 넘어가야 할 부분 같다. 패턴을 만들어내는 것이 내가 반드시 해야될 일인 듯하다.

다시 풀어볼 때 참고하기 위한 소스코드

더블릿_십자카드

엄청난 오류에 빠졌다. 요즘 왜 이렇게 문제에 대해서 잘 못 파악하고 시간을 낭비한 적이 많은지 모르겠다.

일단 무조건 문제에 주어지는 것을 고대로 코드로 옮기는 방법을 먼저 시도해야 된다고 생각한다. 그 동안은 자의적인 해석으로 더 좋은 방법으로 간단하게 풀고자 노력했었다. 하지만 이 것은 아닌 듯 싶다. 

십자카드를 만족하는 수들이 a, b, c, d로 완전탐색을 하면서 

이렇게 조건을 걸어 주었는데 =====>>>>>  (a <= b && a <= c && c <= d)

이 것은 엄청 잘 못 된 방법이었다. 문제를 제대로 파악하지 못 한 케이스였다. ㅜㅜ 

무조건 십자카드는 십자카드에 있는 순서대로 글자를 바꾸어가면서 최소값을 찾아봐야 하는데, 위의 로직은 그렇지가 않는다. 

일단 처음에 몇 가지 숫자들을 써보니까 되길래 했는데 이 것이 낭패였다. 

아무튼 숫자 네 개를 순서대로 돌려가면서 최소값을 찾는 과정을 반드시 해줘야 한다. 

 maketencard라는 함수를 사용해서 최소값을 구해주고 그 최소값이 완전탐색시의 a * 1000 + b * 100 + c * 10 + d와 일치하면 십자카드를 만족하는 수라고 판단하고 카운트를 올려주었다. 그리고 입력받은 수와 동일한 값이 나오면 빠져나오게 하고 카운트를 출력해주는 방식으로 구현했다. 

어려운 문제인줄 알았는데 쉬운 문제였다.

우선 완전탐색부터 해봐야한다는 것을 알았다.

문제를 푸는데 쫌 오래 걸리고, 안타까웠다.

처음에 제대로 된 접근을 했는데, 이상한 생각을 중간에 섞어서 풀지 못했던 것이었다. 

문제 정리)

윗 줄의 번호를 몇 개 뽑아 그 번호들과 아래 번호들이 일치하는 경우를 뽑는 것인데 최대인 경우의 뽑으라는 문제였다.

풀이정리)

반복문을 수행하면서

해당하는 두번째 줄값으로 다시 위의 인덱스를 타고 들어가면서 

처음에 시작한 위치로 돌아오면 이 것은 문제의 경우를 만족하는 것이다.

재귀를 수행할때마다 그 값을 temp라는 배열에 저장하다가 만족하면 result라는 결과값을 모아놓는 배열에

넣어주었다. 물론 방문점 체크 처리도 해야 한다.

시간안에 풀지 못해서 아쉽다