공부하자 - 1000dB

<서론>

한동안 알고리즘을 쉬고 있었다. 사실 한창 할때만큼은 아니라도 하루에 간단한 문제 하나 정도는 풀려고 했었는데, 태생이 나태한 인간이라 정말 몇 개월을 알고리즘 문제 하나 안풀고 보냈다. 그러다 최근 코딩 테스트를 몇 번 보게 될 기회가 생겼는데, 오랜만에 해서 그런지 역시나 제대로 풀 지 못했다. 특히 배열을 파라메터로 사용할 때 얕은 복사 문제가 발생해서, 계속 오답이 나오는 경우가 있었다.

그래서 이 글을 통해 JAVA 배열의 얕은 복사와 깊은 복사에 관해 정리하려 한다.

<본론>

얕은 복사와 깊은 복사는 자료형이 참조형(Reference type)인 경우에 나뉜다. 기본형(Primitive type)에 경우 값 복사만 이뤄지기 때문에 얕은 복사인지 깊은 복사인지 고민할 필요가 없다.

그래서 참조형의 얕은 복사와 깊은 복사에 대해 알아보자.

1. 얕은 복사

얕은 복사는 해당 객체의 주소값을 복사하는 것이다. 결국 객체명은 다를 지언정 같은 값을 참조하는 것이다. 객체명은 다르지만 각 객체의 주소는 같다.

위와 같이 그저 "="로 표시하면 얕은 복사가 된다.

위 코드에서는 얕은 복사가 되었기 때문에 orgArr의 원소 값이 변경되면 copyArr의 값도 같이 변화한다.

orgArr과 copyArr의 주소 역시 동일하다.

어찌보면 당연한 것일 수도 있지만 위 코드처럼 메소드의 파라미터로 배열을 사용하고

해당 배열을 메소드 내에서 수정한다면 당연히 배열 값도 변경한다.

나는 이 부분에서 원하지 않는 수정이 발생했기 때문에 고생을 했다.

이 부분을 해결하기 메소드 내에 깊은 복사를 진행하고 복사한 배열을 변경하도록 메소드를 수정했다.

2. 깊은 복사

깊은 복사는 해당 객체의 값을 복사하는 것이다. 따라서 해당 값을 갖는 또다른 객체를 신규로 생성한다고 생각할 수도 있다. 당연히 각 객체의 주소는 다른 값이다.

위 코드처럼 각 원소에 값을 직접 넣는 식으로 작성한다면 깊은 복사가 발생한다. 이 경우 orgArr이 변경되더라도 copyArr의 값은 변경되지 않는다.

반복문을 통해서 직접 값을 입력하는 방법 말고도 위 코드처럼 메소드를 사용하여 깊은 복사를 진행할 수도 있다. for문과 같은 반복문을 통해서 배열을 복사하는 것보다 위와 같은 코드로 배열을 복사하는 편이 좀 더 직관적인 것 같아서 위 방법을 더 사용한다.

https://stackoverflow.com/questions/18638743/is-it-better-to-use-system-arraycopy-than-a-for-loop-for-copying-arrays

Stackoverflow 형님들 글을 보자면, 반복문을 통해서 배열을 복사하는 것보다, System.arraycopy나 Arrays.copyOf가 더 빠른 것을 알 수 있다. 읽기에도, 쓰기에도, 성능에도 더 좋기 때문에 힘들게 반복문으로 쓰지 말자.

위의 메소드들을 응용하여 2차원 배열도 깊은 복사를 할 수 있다.

<결론>

원리를 안다면 정말 간단한 문제지만, 가끔씩 깜빡 잊고 넘어가는 부분이다. 이번에 코딩 테스트를 풀면서 이 문제 때문에 정말 아까운 시간만 많이 소비했었다. 평소 알고리즘 공부를 꾸준히 했으면 이런 문제는 일어나지 않았을 것이고, 혹시 똑같이 실수 했더라도 그 실수를 바로 잡는데 시간이 얼마 걸리지 않았을 것이다.

이번 코딩테스트를 하고 난 후 반성의 의미로 이 글을 정리했다. 앞으로는 실수하지 말자..

<참고자료>

https://dog-foot-story.tistory.com/27

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

<서론>

문제 링크는 위에.. 오랫동안 알고리즘 쉬다가 다시 공부를 시작하려한다. 이번 문제는 복귀 문제. 한창 풀때였으면 기계적으로 빠르게 풀었겠지만, 너무 오랜만에 해서 그런지 좀많이 허둥댔다. 역시 알고리즘은 빡세게 안할 때라도 하루에 한문제는 풀어야할 것 같다.

이번 문제는 제목에서 알 수 있듯이 경로 탐색 문제! 그럼 이번 문제도 풀어보자.

<본론>

이번엔 테스트 케이스 수를 입력 받아서 그 수만큼 반복문을 실행하는 것은 아니고, 테스트 케이스는 10개로 고정되어있다. 처음 받는 숫자는 테스트케이스 개수가 아니라 테스트케이스 번호라는 것을 알아야한다. 이걸 처리하는 방법은 많겠지만, 난 귀찮아서 입력만 받고 그냥 넘겼다. 이번 문제는 경로 문제답게 간단하게 bfs 방법을 이용해서 풀었다. 알고리즘은 별반 다를 것 없다.

1. 시작 좌표를 큐에 저장
2. 큐가 빌 때까지 또는 목표에 도착할 때까지, 다음을 반복
  2-1 큐 pop
  2-2 큐에서 꺼낸 좌표의 4방향 체크
    2-2-1 4방향에 있는 값을 방문한 적이 없고, 0이면 큐에 추가
    2-2-2 4방향에 있는 값을 방문한 적이 없고, 3이면 목표 도착 체크

평범한 bfs 문제였다. 특별히 신경써서 처리할 것도 없고, 최단 경로의 길이를 구하는 문제도 아니고 그저 도착할 수 있는지만 확인하는 문제. 그런데 오랜만에 풀어서 어처구니 없는 실수들을 반복했다. 다음은 실수들에 대한 정리이다. 바로 코드를 보고 싶은 사람은 바로 결론으로..

1. Input 값 처리 실수

이 문제를 풀 때 발생한 첫 예외처리. 로직을 확인하기도 전에 값을 입력받을 때 문제가 있었다. 아무 생각 없이 nextInt() 메소드를 이용해서 MAP[][] 배열에 값을 넣으려고 했는데, 모든 숫자가 붙어있어서 nextInt를 해버리면 1자리 숫자가 아닌 16자리 숫자로 입력되는 것이었다. 하는 수 없이 String 객체로 입력 받고, split 메소드를 이용해서 잘라 넣었다. MAP 배열을 String 배열로 선언해서 풀 수 있었지만, 이미 모든 로직을 정수형일 경우로 정해놓고 풀어서 input 값을 integer로 파싱했다.

2. 배열 범위 초과

입력 문제를 해결하자 곧바로 다른 예외 발생. 배열 범위를 벗어난다는 어처구니없는 오류였다. 배열을 0,0에서부터 15,15까지 4방향을 체크하게 짜두었는데 가장자리 부분에서 예외가 발생한 것이다. 정말 초보적인 실수를 하고야 말았다. 배열을 2칸 키워서 처리했다. 이래서 알고리즘은 쉬면 안되는 것이다.

3. 무한 루프

배열까지 처리했더니 프로그램이 종료가 안되는 것이었다. 그래서 디버깅 모드로 확인했더니... 블로그에 적지말까? 하고 고민했을 정도로 창피한 실수를 했다. que의 첫번째 원소를 가져오기만 하고 제거를 안한 것이었다. 큐가 빌 때까지 도는 반복문이었기 때문에 곧바로 무한루프.. 버그를 고치면서도 스스로 민망했다.

4. 시작점 설정 실수

아직도 실수가 남았다. 배열을 2칸 늘렸으니 저장되는 시작점의 위치도 그에 따라 바꿔야하는데 그러질 못했다. 그래서 자꾸 답이 다른 답이 나오는 것이었다. 디버깅할 때도 도대체 왜 시작점을 이상하게 잡는 건지 한참을 고민했다. 시작점을 찾는 if문에는 이쁘게 잘 j+1이라고 적어놓고선 실제로 저장할 땐 그냥 j만 저장했다. 간신히 찾고 다시 돌린 결과 정답.. 힘들었다.

<결론>

요약은 패스.

<서론>

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgqsAlKr9sDFAW0&categoryId=AWgqsAlKr9sDFAW0&categoryType=CODE&&&

스터디 중 D4 말고 D5를 도전해봤다. D5 중에서 가장 많은 사람이 제출한 문제인 이번 문제를 풀어보았다. D4만 풀었다가 난이도를 하나 올려봤는데, 이번 문제는 어렵지 않은 문제였던 것 같다. 매일 알고리즘 한 문제 이상은 풀려고 하고, 한 문제 이상은 포스팅하려고 하는데.. 문제를 푸는 것보다 포스팅이 더 어려운 것 같다.

아무튼! 오늘도 풀어봅니다.

<본론>

이 문제는 입력 값이 10^12 까지라서 int 형태로는 입력을 받을 수 없다. 따라서 long 형태를 사용했다. 이 문제에서 핵심은 가장 가까운 제곱근을 구하는 것인데, Math 클래스를 사용하면 쉽게 가까운 제곱근을 구할 수 있다. 처음에는 Math 클래스의 sqrt 메소드 말고 for문을 이용해서 풀려고 했지만, 시간 초과가 나서 포기. 결국 Math 클래스를 사용했다. 입력값에 따라 범위를 나눠서 풀었다면 시간초과는 해결했으려나..

아무튼 이 문제는 제곱근만 구하면 되는 문제라 다른 설명은 모두 결론에 넣겠다.

<결론>

요약

1. 이 문제의 핵심은 가장 가까운 제곱수 찾기(큰 수들 중)

 1.1 +1은 값이 커지는 것

 1.2 제곱근은 값이 작아지는 것.

 1.3 제곱근할 수 있으면 무조건 제곱근하기

2. N의 제곱근을 구하고 정수로 파싱

3. 파싱한 값을 다시 제곱했을 때, N과 같은 지 비교

 3.1 N과 같다면 N을 제곱근한 값으로 N값 변경

 3.2 같지 않다면 N을 (루트(N) + 1 ) 로 N값 변경( 이때 (루트N +1)^2 에서 N의 차이만큼 카운트(ans) 증가)

4. 카운트 1 증가

5. 2가 될때까지 반복

<서론>

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

예전에 풀었던 문제! 링크는 위에.. 코드는 결론에.

처음에는 막막하기만 했었는데, 조금 하다보니 감이 왔다. 물론 감이 오고 나서도 시간이 오래 걸렸다. 음, 풀고 나니 별거 아닌 문제였지만 풀 당시에는 너무 어려웠던 문제. 문제 풀었던 기억이 더 희미해지기 전에 빠르게 포스팅 해본다.

<본론>

이 문제를 풀 때, DFS나 재귀는 괜찮았지만 BFS로는 문제를 거의 풀어보지 못했다. 최단 경로 문제는 BFS로 풀어야한다고 어디서 주워들은 건 있어서 이 문제를 BFS로 풀려고 했다. BFS에 대한 감이 별로 없던 상태에서 무턱대고 BFS로 풀려 했으니, 삽질을 꽤 많이 했다.

그래도 이 문제 덕분에 나름 BFS로 문제를 푸는 감도 익힌 것 같다.

탐색했을 때 그 먹이까지의 거리가(여기서는 시간이) depth이기때문에 가지고 거리를 판단했다.

거리가 같을 때 우선순위는 더 위에 있거나 y축 값도 같다면 왼쪽에 있는 걸 먹도록 분기처리도 하였다.

탐색은 현재 위치를 기준으로 상하좌우 4방향을 탐색했고,

1. 해당 방향의 위치가 탐색한 곳이 아닌 경우

2. 자기 자신(상어)보다 숫자가 작거나 같은 수인 경우

위 두가지 경우에만 탐색을 진행했다.

위 두가지에 해당하는 곳은 visited 배열에서 true 값으로 바꿔주었고

먹이인 경우(0이 아니면서 자기보다 작은 경우)와 길인 경우(자기 자신과 숫자가 같은 경우)로 나누었다.

먹이인 경우에는 food 객체에 값을 넣었고, 길인 경우에는 que에 해당 좌표를 넣었다.

탐색이 다 끝나면 먹이를 향해 이동했고(먹이가 없는 경우에는 프로그램 종료), 먹이를 먹고 성장할지 안할지도 판단했다.

이제와서 보니 비효율적으로 짜여진 곳이 많은데, 저 문제를 풀 당시에는 문제를 푸는 것만으로도 너무 버거워서 일단 답을 뱉어내는 코드를 만들었다.

그래도 이 문제 덕분에 BFS 풀이에 대해 조금 알 수 있게 된 것 같다.

<결론>

요약

1. 먹이 or 탐색위치를 담을 Class 생성.(필드로는 x,y 좌표, 거리)

2. 탐색 조건(자신보다 작은 수, 방문하지 않았던 곳)에 맞는 곳을 BFS로 탐색

3. 먹이를 발견했을 경우, que에 넣지 않고 따로 food 객체에만 저장

4. 같은 depth에서 다른 먹이 발견 시, 우선 순위(1. y값이 더 아래, 2.x값이 더 아래)에 맞게 food 저장값 변경

5. 먹이로 이동 후 성장할 지 확인.

6. 더이상 이동할 수 없을때까지 반복.

<서론>

https://swexpertacademy.com/main/code/problem/problemDetail.do

정답 코드는 결론에..

위 링크는 문제 링크이다.

D4를 다 풀어보자! 라는 마인드로 D4문제를 풀고 있는데, 음.. 아직까지는 조금 쉬운 느낌이다. D5로 올려서 풀어야하나. 암튼 제출이 많은 순서대로 문제를 풀어보기로 했다! 그 중 첫번째가 바로 "3752 가능한 시험점수" 이다!

<본론>

처음 문제를 접했을 때, 이건 모든 경우를 다 구해서 set에 넣고 set의 사이즈를 구하면 되지 않을까 했다. 그리고 모든 경우를 combination 풀 듯 구해볼까 했다.

그런데..

만약 문제의 수가 최대 100개일때, 100 C 50은 어마어마한 경우의 수가 나오는 것이었다. 결국 다른 방법으로 풀어야겠다 생각하고 고민..

아무리 고민해봐도 이 문제는 모든 경우를 다 구해서 set에 넣는게 맞는 것 같았다. 그래서 모든 경우를 조금 다르게 구해보려 했다.

만약 N이 1이고 배점이 A라면

N=1 :0,  A

요렇게 2개가 나올 것이다. 근데 만약 여기서 B가 추가된다면?

N=2 : 0, A, B, A+B

이렇게 2개가 더해져 4개의 결과가 나왔다. C까지 추가된다면?

N=3 : 0, A, B, A+B, C, A+C, B+C, A+B+C

이렇게 4개가 더해져 8개가 되었다!

그렇다! 느낌 왔다! 문제가 x개 라면, x-1개 일때의 모든 경우의 수에 +x번째 수를 더한만큼 더 있으면 되는 것이었다!

중복값이 생겨도, set에 들어가면 중복이 제거되니 저런 식으로 구하고 set에 add만 해주면 되었다!

처음에 조금 생각을 했지만, 결국 금방 풀 수 있었다!

<결론>

SET은 중복을 허용하지 않는다.

<서론>

이번에 포스팅하는 알고리즘 문제는 최근 스터디를 진행하게 되면서 첫번째 과제로 하게 된 세 문제 중, 가장 난이도 낮은 문제다. SW Experts Academy에서 제공하는 문제 중 D4 난이도의 문제는 몽땅 다 풀어버려야지! 하는 마음 가짐으로 접근했는데, 생각보다 쉽지 않았다. 아무튼 각설하고 가장 쉽게 풀었던 7465번 문제를 본격적으로 포스팅하겠다.

참고로 문제 링크는..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE

<본론>

첫번째와 마찬가지로 완성 코드는 결론에 놓겠다.

알고리즘 문제 풀이의 첫번째 글의 문제를 풀었을 때보다 2달이 지난 다음에 풀어서 그런지, DFS 문제는 손쉽게 풀 수 있게 된 것 같다(물론, 이번 문제가 특히 더 쉽다).  다른 방법으로 풀 수도 있겠지만 가장 빨리 생각난 방법으로 문제를 풀었다.

큰 틀은 이렇다.

이 문제는 서로 알고 지내는 무리가 몇 개인지 구하는 문제인데, 이는 결국 그래프의 개수를 구하는 문제라고 생각했다.

따라서,

1. 임의의 노드에서 DFS 방법으로 완전 탐색을 진행한다.

2. 완전 탐색이 다 끝난 후에도 아직 방문하지 노드가 있는 지 확인한다.

3. 만약 방문하지 않은 노드가 있다면, 이것은 다른 그래프가 또 존재한다는 뜻.

4. 다른 노드를 정해서 완전 탐색을 진행한다.

5. 1~4 반복

이것보다 더 최적의 방법이 있을 수도 있다고 생각하지만, 일단 내가 생각할 수 있는 선에서는 이것이 베스트였다. 사실 다른 방법은 생각도 못했지만...

같이 스터디를 진행하는 팀원은 이 문제를 Union find로 풀었다. 처음 들어보는 알고리즘이었다. Union find가 무엇인지 공부하고 그 방법으로도 풀어봐야겠다.

<결론>

요약

 1. N을 입력 받고, N*N 크기의 2차 배열(graph), N 크기의 배열(visited), 정답으로 쓸 ans(초기값 1) 생성

 2. 1번부터 시작해서 DFS 방법으로 완전 탐색

 3. 완전 탐색 후 visited 배열에 false값 있는지 확인

  3.1 false값이 있는 경우 ans++ 후 break

 4. ans 값 출력

<서론>

이 문제를 풀었을 당시에 나는 dfs와 bfs에 대해 하나도 모르는 상태였다. 알고리즘 문제를 푼다는 행위 역시도 매우 매우 낯설었기 때문에 15683번인 감시를 푸는 일은 내게 굉장히 힘든 일이었다. 게다가 알고리즘 문제를 재귀로 풀 생각을 아예 못했었을 정도니... 아무튼 삼성 기출 문제라고 하길래 풀어보았다.

서론을 이런 식으로 쓰는 이유는.. 난 이 문제를 일반적인 dfs 풀이로 풀지 않았기때문이다. 나는 무려 8번의 for문을 사용해서 풀었다. 만약 이 문제가 막혀서 해결하고자 오신 분들이면 이 글을 추천하지 않는다. 만약 당신이 왕초보 코더가 간신히 푼 문제를 비웃고자 한다면 이 글을 계속 읽어도 좋다.

<본론>

** 요약

핵심 : 8중 for문 사용(최대 카메라 수 만큼), for문 순서는 카메라 역순(제일 밖 for문 : 8번 카메라, 제일 안 for문 : 1번카메라)

1. 기본적으로 4방향이기 때문에 for문 인덱스는 0~3 까지 확인, 카메라가 없는 경우는 0만 되게 설정(for문 1번은 돌아야하니)

2. for문 인덱스 번호를 방향으로 그 for문의 카메라 감시영역을 7로 바꿈(int 배열이라 7로 표현, changeToS 메서드)

3. 만약 그 번호 카메라가 존재한다면, 지금 상태 감시 상태 저장(나중에 원복할 때 사용할 예정, 굳이 for문마다 안해도 되는 기능 - 실수 )

4. 모든 카메라를 다 체크했다면, 전체 배열을 체크하면서 0의 개수 파악(countZero 메서드) -> 현재값보다 작으면 저장

5. 카메라 감시방향 리셋

완성 코드는 결론에 적겠다.

우선, 나도 처음에는 코드를 멋지고 간결하게 짜고 싶었다. 하지만 태어나서 이런 류의 문제는 처음이었고, 뭔가 오기가 생겨서 주변 도움은 하나도 받지 않은 상태로 문제를 해결하고 싶었다. 짜내고 짜내다가 내린 결론은 for문을 카메라 수만큼 사용하는 것이었다.

이런 극단적인 선택을 할 수 있었던 이유는 전체 경우의 수가 4^8 = 65,536 가지 뿐(카메라 8개, 확인하는 방향 4개)이다. 내가 컴공은 아니라 정확히는 모르지만, 저정도 경우의 수면 아무리 for문이 8중이라도 시간 초과는 나지 않을 것 같았다.

for문을 8개 만들고 나니, 안쓰는 포문에 대해서도 고민했어야 했다. 그래서 카메라 뒷번호일수록 바깥쪽 for문으로 설정했고, 카메라 개수인 cCnt에 따라서 for문의 반복 회수도 결정했다. 즉, 모든 카메라에 대해

for(aa1 = 1; a11<a1; a11++)

for(int aa1 = 1; aa1<a1; aa1++)

이런 식으로 설정했고 카메라가 4개라면 a1 ~ a4까지는 4, a5 ~ a8은 1로 설정해서 a4까지는 4번 돌고, 나머지는 한번만 돌게 설정했다. 그리고 각 카메라의 번호와 위치, 방향 정보를 보내서 감시영역을 7로 바꿔주는 메서드를 호출했다.

모든 카메라의 감시영역이 칠해지면 그 후 0을 세는 메서드를 사용해서 최소 사각지대를 구했다.

이렇게 코드를 짜서 제출했고, 답은 맞았지만 지금 코드에서 굉장히 비효율적인 부분이 있다. 8중 for문을 쓴 것이 아니라 다른 부분에서의 비효율이다.

현 프로세스는

1. 카메라의 감시 방향 결정(여기서는 for문의 인덱스)

2. 감시 방향대로 지도에 표시

3. 현재 방 상태 저장

4. 모든 카메라를 확인할 때까지 1~3 과정 반복

5. 사각지대 수 확인

6. 첫 번째 카메라 감시영역 표시 전으로 원복

7. ...

위와 같이 작성하였다. 즉 카메라 감시 방향이 정해지면 바로 칠하고 다음 카메라로 이동하는 것이 문제인 것이다.

그렇기 때문에 카메라 별로 감시 전과 후를 위한 2차 배열이 필요했다.

이를 개선한다면, 모든 카메라의 감시방향을 다 정한 후, 감시 영역 표시는 그 후에 한꺼번에 이루어 지는 것이 간편할 것이다.

그렇게 되면 원복용 2차 배열도 1개만 있으면 될 것이다.

답은 맞았지만, 이부분을 고려하지 못한 것은 무척이나 아쉽다.

<결론>

아래에 무시무시하게 긴 코드가 있다. dfs, bfs도 그렇고 재귀 함수에 대해 매우 몰랐던 탓에 이렇게 무식한 코드가 나왔다. 이번 문제를 풀고 dfs와 bfs에 대해 공부를 해야겠다! 라는 마음도 생겼고, 무식하지만 그래도 나 혼자만의 힘으로 풀었다는 것에 뿌듯하기도 했다. 물론 이 한문제를 풀기위해 너무나 많은 시간을 쏟았지만 그래도 다 풀고, 맞았습니다! 를 보았을 땐 정말정말 기뻤다.

이 재미에 알고리즘 문제를 푸는 것 같다.