공부하자 - 1000dB

<서론>

프로젝트 진행 중, 전날까지 잘되던 프로젝트가 서버 구동만 하면 콘솔에 어떤 글자가 써지기도 전에 오류 메시지창이 뜨면서 서버가 시작도 하지 않는 것이다. 잘되다가 갑자기 왜 그럴까 하고 구글링.. 비슷한 에러들은 많이 보이지만 나와 같은 에러는 없었다. 아마 "프롤로그에서는 콘텐츠가 허용되지 않습니다" 라는 말이 한글이라 검색결과가 잘 안나온 것 같아 이 부분을 "Content is not allowed in prolog" 로 바꾸고 검색했더니 스택오버플로우에 나왔다. 스택오버플로우 분들 감사합니다.

<본론>

헛소리는 이쯤하고 해결법부터 적어본다.

1. Eclipse 종료
2. [workspace]/.metadata/.plugins/org.eclipse.wst.server.core 폴더로 이동
3. tmp# 폴더를 삭제(#에는 번호가 들어간다. 예. tmp0, tmp1)
4. Eclipse 실행
5. tomcat, project clean

이렇게 했더니 처음처럼 아주 잘 돌아간다.

<결론>

tmp 폴더 내의 xml 파일이 꼬여서 그런 것 같기때문에 tmp 폴더를 그냥 다 날림으로써 해결했다. 매우매우 간단한 문제였는데, 한글로 검색하니 안나오고, 영어로 검색하니 나와서 다행이었다. 순간적으로 '영어로 검색해보자!' 라는 생각을 안했다면 아마 하루종일 고생했겠지..

다시한번 스택오버플로우 회원들에게 감사한다.

<참조>

https://stackoverflow.com/questions/36196734/removing-obsolete-files-from-server-could-not-clean-server-of-obsolete-files

ISNULL( SUM( column ), 0 ) - 권장

SUM( ISNULL( column, 0 ) ) - 이건 성능 저하. 무의미한 함수 발생

Null값은 연산을 하지 않으니 굳이 NVL 혹은 ISNULL 필요 없음

Oracle에서는 공백('')은 null 취급하지만

MSSQL에서는 공백과 null이 다르다... 이거 주의하자!

2020.01.31 추가

Null 값은 비교할 수 없다.

예)CASE WHEN A.col = '0' THEN ...

예2) CASE WHEN ISNULL(A.col, '0') = '0' THEN -- orcale : NVL(A.col,'0')

예)와 같은 쿼리에서 많약 A.col에 Null 값이 있다면 해당 조건은 무조건 false를 반환.

예2)와 같이 Null을 처리해줘야 CASE 문이 원하는데로 작동한다.

A.col = Null - 잘못된 방식

A.col IS NULL - 올바른 방식

A.col <> Null - 잘못된 방식

A.col IS NOT NULL - 올바른 방식

위에도 가끔 실수한다. 잘 고치자.

MAX( ISNULL( A.col, 0 ))

ISNULL( MAX( A.col ), 0)

큰 차이는 없지만 가끔 값이 다를 수 있다. Null 처리할 땐 조심하자

해당 내용은 내가 사용하려고 백업 용도로 올리는 글이다.

설명이나 이런 건 없다...

SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED
SELECT * FROM SYS.TABLES
WHERE OBJECT_ID IN (SELECT OBJECT_ID FROM SYS.COLUMNS
WHERE NAME = 'APPL_TOT_DLV_AM')

<서론>

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

코드는 결론에, 문제는 위 링크로

하루 2포스팅! 사실 포스팅 거리가 밀려서 바쁘게 글 올려야하는데, 귀찮아서 못올리고 있다. 일단 올리기 편한 알고리즘 문제들부터 빨리 해치워야지. 이 문제 역시 스터디를 위해 푼 문제고 제출순으로 했을 때 2번째로 많이 제출한 문제다(2019.04.24 D4 기준). 본론에서 말하겠지만 미리 말하자면 매우 단순한 완전 탐색 문제! 한 번 풀어보자.

<본론>

문제를 보자마자 '이거 dfs든 bfs든 6번 이동만 시키고 결과를 set에 넣으면 되겠다' 라는 생각이 들었다.

graph는 4*4로 고정이고 메서드마다 파라미터로 싣기 귀찮아서 static으로 선언했다.

가장자리 부분일 때 분기처리하기 귀찮아서, 1칸씩 여유를 줬고 가장자리에는 다 -1을 넣었다. 그래서 이동하고자 하는 칸이 -1이면 이동하지 않고 넘어가게 처리했다.

음... dfs로 풀었는데, 따로 설명할 건 없는 것 같다.

다만 이 문제를 처음 제출했을 때, 테스트케이스 하나만 맞고 틀렸다 나와서 약간 멘붕했었는데..

틀린 이유는 static으로 선언한 set을 각 테스트케이스마다 초기화해주지 않아서 일어난 일이었다.

이거때문에 알고리즘 문제인 줄 알고 한참을 고민했다.....

<결론>

1. 이중 포문을 이용해서 모든 점에서 move 메서드 호출

2. 이중 포문 끝나고 set의 사이즈 확인.

// move 메소드

1. 이동을 6번 했는지(depth==7) 확인

 1.1 이동을 6번 다했다면 지금까지 누적된 str을 set에 add

2. 현재 str에 현재 graph의 값을 더하기

3. 현재 점에서 동서남북 4방향으로 move 메소드 실행

 3.1 단, 다음 방향이 -1이 아닌 지점인 경우에만

 3.2 depth는 +1 하기

<서론>

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에 대해 공부를 해야겠다! 라는 마음도 생겼고, 무식하지만 그래도 나 혼자만의 힘으로 풀었다는 것에 뿌듯하기도 했다. 물론 이 한문제를 풀기위해 너무나 많은 시간을 쏟았지만 그래도 다 풀고, 맞았습니다! 를 보았을 땐 정말정말 기뻤다.

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

SET

1.     Select 쿼리 결과갑을 입력하지 않고 직접 변수에 값을 입력하는 경우

2.     Null 결과 값을 입력하는 경우

3.     여러 변수 타입의 결과값을 입력하고 사용하는 경우

SELECT

1.     한 번에 여러 변수값을 할당하는 경우

2.     쿼리 결과 값 즉, 하나 이상의 값을 할당하는 경우

3.     @@ROWCOUNT, @ERROR를 사용하는 경우