[SWEA] 설날 밀린 문제 풀이

설날 연휴 기간에는 추가로 진도를 나가지 않아 그동안 풀지 않았던 문제들을 풀기로 하였다.

내 코드들은 깃허브에 커밋해두었다!

https://github.com/Ho-hoho/SWEA/tree/main

No3. 동아리실 관리하기 (SWEA 3316)

부원이 4명이기 때문에 비트마스킹으로 겹치는 사람들을 잘 확인하면 되는 문제였다. 처음엔 일일이 스위치문을 사용하여 ABCD 를 비트로 바꿨는데 다른 사람의 코드를 보니 1 << (str[date] - 'A'); 와 같이 쉽게 ABCD를 비트로 바꿀 수 있었다. 하지만 문제의 답이 잘 나오지 않았는데 알고보니 중간에 나눗셈하는 수를 실수할까봐 복사를 해왔는데 복사하면서 콤마도 같이 복사되어 프로그램이 잘 돌아가지 않았던 것이었다. 이런 실수는 더 안해야겠다!

 

No5. 수열편집 (SWEA 13501)

링크드 리스트 문제였다. 메모리풀을 사용하여 잘 구현한것 같은데 계속 세그폴트가 떠서 상당히 오래 고민한 문제이다. 어느 부분에서 세그폴트가 뜬다는 지 모르겠어서 구글링을 해봤지만 구글링을 해도 나오지 않는 문제였다. SWEA 홈페이지에 세그폴트 뜨는 사람이 올린 질문을 봤는데 그 문제가 나는 아니었다. 결국 친구의 코드를 받아 확인해봤는데 코드는 거의 같았다. 알고보니 처음 수열 제한은 1000이고 변형이 1000개가 들어올 수 있어 수열의 길이가 2000이상으로 잡아야됐는데 1001으로만 잡아서 터지는 것이었다. 링크드 리스트 문제라 포인터 문제라고만 생각하고 코드를 계속 봤는데 이걸로 크게 배운것 같다.

 

No4. 암호문3 (SWEA 1230)

이것은 수열편집과 거의 같은 문제여서 수열 편집의 코드를 조금 건드리니 문제가 풀렸다.

 

No10. 최대상금 (SWEA 1244)

처음에는 문자열을 훑으면서 한 문자 뒤에 나오는 제일 큰 수와 바꾸는 방법을 사용하였다. 하지만 예시를 보며 생각해보니 꼭 먼저온 숫자를 제일 뒷 숫자랑 바꾸면 안된다는 것을 알았다. 전날 푼 백준 문제도 이러한 생각을 가지면 재귀로 문제를 풀어야한다는 것을 알았기에 최대 문자열의 길이와 변형의 숫자가 6 과 10 밖에 되지 않아 충분히 재귀로 풀 수 있다고 생각해서 풀었으나 시간초과가 났다. 백트래킹을 하나도 하지 않아서 vis 배열을 만들어서 백트래킹을 해줬으나 2~3개가 풀리지 않았다. 다시 천천히 코드를 보니 맨 처음 재귀로 짤때는 뒤에 나오는 제일 큰 수와 바꾸는 방법을 사용했는데 꼭 클 필요는 없을 것 같아서 그 조건문을 지웠고 j=i부터 두번째 반복문을 시작했는데 이렇게 되면 자기 자신끼리 바꿀 수도 있다는 것이기 때문에 j = i+1로 바꾸어 주었다.

 

No11. 최장 공통 부분 수열 (SWEA 3304)

전형적인 LCS 문제였다. 이때 S 가 substring 이면 문자들끼리 붙어있어야 하고 subsequence(sequence)이면 붙어있지 않아도 된다. 이 차이는 붙어 있어도 된다면 비교하는 두 문자가 같지 않을 때 dp배열의 왼쪽이나 위에서 숫자를 큰 값을 가져오면 되고 붙어 있으면 안된다면 0을 값으로 주면 된다.

 

No12. 0/1 Knapsack (SWEA 3282)

문제이름이 스포였던 0-1 knapsack 문제였다. 0-1 knapsack 문제를 되게 많이 풀어봤는데 오랜만에 푸니 점화식 정도만 생각이 났다. 그래서 생각난 점화식으로 재귀로 점화식을 구현해봤더니 시간초과가 났다! 역시 유명한 dp 문제 답다. 그래서 살짝 구글링을 해서 문제를 풀었다. 두번째 for 문으로 w가 1부터 K 까지 갔다는게 낯설었다. 역시 아는 문제라고만 생각하고 풀지 않으면 까먹나보다!

 

No14. 광고 시간 정하기 (SWEA 9999)

분할정복 카테고리에 있어서 처음에 코드를 왼쪽 오른쪽 중앙으로 나누어서 코드를 짰는데 짜고 보니 재귀를 가지 않고 처음부터 모든 범위를 다 다루고 있었다. 그래서 재귀 하는 부분을 삭제하고 코드를 돌리니 답이 나왔지만 시간초과가 떴다. 그래서 친구한테 코드를 받아보니 사용하는 개념은 같았지만 코드는 훨씬 콤팩트하게 짜여져있었다. 나도 조금 더 생각했으면 저런 코드를 짤 수 있었을까?