인증이 되어있지 않은 사용자는 스프링 시큐리티의 필터링에 걸려 로그인 페이지로 향하게 된다. 나의 경우 처음에는 로그인을 성공했을 때 핸들러를 통해(SimpleUrlAuthenticationSuccessHandler를 상속받아 작성) 메인페이지로 돌아가게끔 URL을 지정하였다.


그렇다면 메인페이지말고 내가 로그인 페이지로 넘어가기전에 요청했었던 url로 넘어가고 싶다면 어떻게 해야 할까?


보통 다른 방법들을 찾아보았을 때 login페이지 컨트롤러에서 Session 값을 넣거나 하는 작업을 하는 것들을 보았는데, 사실 우리는 그럴필요가 없다. 



레퍼런스에서 발견한 내용인데 두번째 문단을 읽어보면 인증전의 요청을 세션에 저장하고 있다고 얘기한다.

그리고 세션에 저장되어 있는 속성의 이름은 SPRING_SECURITY_SAVED_REQUEST 이다. 그렇다면 이제 로그인을 성공했을 때 핸들러에서는 다음과 같이 작업을 하면 될것이다.




또 다른 방법으로는 위의 글에서 언급한바와 같이 핸들러를 작성할 때 SavedRequestAwareAuthenticationSuccessHandler

를 상속받아 사용할수도 있는 것 같다.




분할 정복 알고리즘이란 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 재귀 호출과 차이점은 이 부분 문제를 나누는 방법에 있어 재귀 호출은 작은 부분하나씩 분리해서 해결하지만, 분할 정복은 항상 비슷한 크기의 부분으로 나눈다는 것


분할 정복을 사용하는 알고리즘들의 세 가지 구성 요소

  • 문제를 더 작은 문제로 분할하는 과정
  • 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
  • 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제


분할 정복을 이용한 문제


1) 1~n까지의 합을 구하여라

재귀 함수를 이용하여 1~n 까지의 합을 구했을 때는 O(n) 시간 복잡도였지만

분할 정복을 이용한다면 O(log n) 까지 줄일 수 있다.


2)행렬의 거듭제곱

n*n 행렬을 m번 곱하게 된다면 일반적인 방법은 O(n^3)시간 복잡도가 걸린다면 분할 정복을 이용했을 때는 O(log m)이 걸린다.



절반은 어떠한 형태로 나누어야 할까?


A^m을 나눌 때는 어떤 형식으로 나누어야 할까


1) A*A^(m-1)

2) A^(m/2) * A^(m/2)


이것은 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예이다.


절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문이다. 예로 A(11)→A(5)*A(6)→(A2)(A3) * (A3)(A3)→... 이와 같이 반복되는 부분문제들이 많아지게 때문이다. 


3) 병합 정렬과 퀵 정렬


병합 정렬 = 병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬하는 알고리즘으로, 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.


분할 단계의 시간 복잡도 : O(1)

병합 단계의 시간 복잡도 : O(n)


퀵 정렬 = 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 분할.


이 두 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐, 병합 단계에서 하느냐가 다르다.


4) 카라츠바의 빠른 곱셉 알고리즘


카라츠바의 빠른 곱셉 알고리즘은 두 개의 정수를 곱하는 알고리즘이다. 기존의 두 개의 정수의 곱셈으로 사용했던 아이디어는 O(n^2)의 시간 복잡도를 요구하였지만 카라츠바의 바른 곱셉 알고리즘의 시간 복잡도는 O(n^log 3)이다. 단 카라츠바의 알고리즘 구현은 매우 복잡하기 때문에 입력의 크기가 작은 경우에는 O(n^2)의 알고리즘을 사용한다. 


5) 쿼드 트리 뒤집기 문제


알고리즘 설계 패러다임이란 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다.


무식하게 풀기


'무식하게 푼다'라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 "완전 탐색"이라고 한다.



재귀 호출과 완전 탐색


재귀 호출(=재귀 함수)이란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 말한다.


재귀 함수에는 '더 이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문(='거저 사례')을 포함해야 한다.

ex) if(n==1) return 1;


재귀 호출은 기존에 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공해 준다. 기존의 코드에 비해 재귀 호출을 통해 얻을 수 있는 별다른 이득은 없지만, 문제의 특성에 따라 재귀 호출은 코딩을 간편하게 해 줄 수 있는 강력한 무기가 된다.


재귀 호출을 이용하여 풀 수 있는 문제

1) 소풍 - 학생들을 두 명씩 짝 지어 주되, 친구인 학생들끼리만 짝을 지어줄 수 있는 방법의 갯수.

2) 게임판 덮기 - 격자 모양의 게임판에 ㄴ자 형식의 블록을 알맞게 삽입할 수 있는 경우의 개수.




최적화 문제(Optimization Problem)


문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제라고 합니다.


최적화 문제를 해결하는 방식 중 하나는 완전 탐색이다.


최적화 문제를 완전 탐색으로 풀 수 있는 문제 


1) 외판원 문제 - n개의 도시를 한 번씩 돌아서 돌아오는 데 걸리는 최소 거리.

2) 시계 맞추기 문제 - 


'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15

알고리즘이 존재가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 따라서 알고리즘의 정확한 증명은 각종 수학적인 기법을 기반으로 되야한다.


수학적 귀납법과 반복문 불변식



수학적 귀납법은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법.


귀납법은 크게 3가지로 나뉜다.

  • 단계 나누기 = 증명하고 싶은 사실을 여러 단계로 나눈다.

  • 첫 단계 증명 = 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 

  • 귀납 증명 = 첫 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다.

알고리즘은 어떠한 형태로든 반복적인 요소를 가지고 있기 때문에, 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법.


반복문 불변식 = 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는지..


불변식을 이용한 반복문의 정당성은 다음과 같이 증명한다


  • 반복문 진입시에 불변식이 성립함을 보인다.

  • 반복문 내용이 불변식을 깨뜨리지 않음 보인다. 시작할 때 불변식이 성립하면, 끝에서도 성립한다

  • 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음 보인다.

*불변식이 깨졌을 때 프로그램을 강제 종료함으로써 알고리즘에 문제가 있는지 없는지를 판단할 수 있다. 다만 엄청나게 많이 실행되는 반복문 안에 단정문을 배치하는 것은 삼가는 것이 좋다.


귀류법



귀류법은 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법.


알고리즘의 결과가 최선임을 보이기 위해 각 단계에서 최선의 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선의 선택을 한다면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명한다.


비둘기집의 원리



10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이 반드시 하나는 있게 마련이다.




'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15

1. final



1) 변수 : 변수가 초기화된 이후 변경되지 않는다.



2) 클래스 : 이 클래스는 서브클래스를 가지지 않는다. 다시 말해 이 클래스를 상속할 수 없다.




3) 메소드 : 해당 메소드는 서브 클래스에 의해 오버라이딩 되지 않는다.





2.finally



1) try - catch : try 혹은 catch가 실행된 후 실행



finalize



가비지 컬렉션에서 객체를 destroy 또는 delete 하기 전에 호출하는 메소드이다. 데이터베이스 커넥션이나,  네트워크 커넥션 같은 연관된 자원들을 해제한다. 기본적으로 Object에 선언되어 있으므로, 모든 객체는 finalize를 가지고 있다.



'Programming > JAVA' 카테고리의 다른 글

final, finally, finalize  (0) 2018.11.20
Comparison with Lambda  (0) 2018.10.29
자바 8 - Map  (0) 2018.10.19
캡슐화, 추상화, 인터페이스  (0) 2018.10.10
자바8 - List  (0) 2018.10.02
자바8 - 제네릭  (2) 2018.09.03

+ Recent posts