버블 정렬Bubble Sort

버블 정렬Bubble Sort 알고리즘의 특징

  • 인접한 두 원소를 검사하여 정렬하는방법

  • 느리지만 코드가 간단하여 자주 사용된다.(라고는 하는데 개인적으로 학부때 수업들을때말고는 사용해본적이 없긴하다.)

  • 프로세스 방법

    • 인덱스 0 과 인덱스 1의 값을 비교한다.

    • 0번째의 값이 1번째의 값보다 크다면 스왑 한다.

    • 인덱스1과 인덱스 2의 값을 비교한다.

    • 1번째의 값이 2번째의 값보다 크다면 스왑 한다.

    • 인덱스를 증가시키면서 n 까지 반복한다.

    • n까지 반복하면 가장 큰 값이 맨 n에 위치하게된다.

    • 이제 인덱스 0부터 n-1 까지 반복한다.

    • 하나의 원소만 남을때까지 위의 과정을 반복한다.

  • 장점

    • 구현이 단순하다. 
  • 단점

    • 속도가 느리다.

알고리즘 예제

매우 적절할 버블정렬을 춤으로 나타낸 동영상이다.

youtu.be/lyZQPjUT5B4

버블 정렬Bubble Sort 코틀린 코드

fun bubbleSort(arr: IntArray): IntArray{
   var temp = 0
   for(i in arr.indices){
       for(j in 1 until arr.size - i)
           if(arr[j] < arr[j-1]) {
               temp = arr[j]
               arr[j] = arr[j - 1]
               arr[j - 1] = temp
           }
       }
    return arr
}
  • 시간복잡도
    • O(n^2)
    • 정렬할 자료의 길이만큼 이중 반복을한다.
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

레코드, 키의 정의 및 검색 트리  (0) 2020.12.29
삽입정렬Insertion Sort  (0) 2020.12.27
선택 정렬Selection Sort  (0) 2020.12.22
앞으로 공부할 알고리즘  (0) 2020.12.22

선택 정렬Selection Sort

선택 정렬Selection Sort 알고리즘의 특징

  • 제자리 정렬(in-place sorting)의 하나이다.
    • 입력벼열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법.
  • 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘.
    • 첫번째 순서에 첫번째 위치에 가장 최소값을 넣는다.
    • 두번째 위치엔 남은값중 최솟값을 넣는다.
    • n 번째 위치엔 남은 값중 최솟값을 넣는다.
  • 프로세스 방법
    • 주어진 배열에서 최솟값을 찾는다.
    • 그 값을 맨앞의 값과 교체한다.
    • 맨처음 위치를 뺀 나머지 리스트를 같은 방법으로 교채한다.
    • 하나의 원소만 남을때까지 위의 과정을 반복한다.
  • 장점
    • 자료의 이동 횟수가 미리 결정된다.
  • 단점
    • 안정성을 만족하지않는다.

알고리즘 예제

선택정렬의 코틀린 코드

fun main(){

    print(selectionSort(intArrayOf(3,6,1,7,5,4,9)).joinToString(","))
    //1,3,4,5,6,7,9
}

fun selectionSort(arr: IntArray): IntArray{
   var minIdx = 0
   var temp = 0
   for(i in arr.indices){
       minIdx = i
       for(j in i+1 until arr.size   ){
          if(arr[minIdx] > arr[j]) {
              minIdx = j
          }
       }

       if(minIdx != i){
           temp = arr[i]
           arr[i] = arr[minIdx]
           arr[minIdx] = temp
       }

   }

    return arr
}
  • 시간복잡도
    • O(n^2)
    • 정렬할 자료의 길이만큼 이중 반복을한다.
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

레코드, 키의 정의 및 검색 트리  (0) 2020.12.29
삽입정렬Insertion Sort  (0) 2020.12.27
버블 정렬Bubble Sort  (0) 2020.12.26
앞으로 공부할 알고리즘  (0) 2020.12.22

앞으로 공부할 알고리즘. 공부가 끝나면 블로그에 정리 후 링크를 달아두기로한다. 

 

 

1. 정렬
  1.기본적인 정렬 알고리즘
    1. 선택 정렬Selection Sort
    2. 버블 정렬Bubble Sort
    3 .삽입 정렬Insertion Sort
  2. 고급 정렬 알고리즘
    1. 병합 정렬Merge Sort
    2. 퀵 정렬Quick Sort
    3. 힙 정렬Heap Sort
  3. 비교 정렬 시간의 하한
  4. 특수 정렬 알고리즘
    1. 기수 정렬Radix Sort
    2. 계수 정렬Counting Sort

2.선택 알고리즘
  1 평균 선형 시간 선택 알고리즘
  2 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

3.검색 트리  
  1. 레코드, 키의 정의 및 검색 트리
  2. 이진 검색 트리 
    1. 이진 검색 트리에서 검색
    2. 이진 검색 트리에서 삽입
    3 .이진 검색 트리에서 삭제
  3, 레드 블랙 트리
    1. 레드 블랙 트리에서 삽입
    2. 레드 블랙 트리에서 삭제
    3. 레드 블랙 트리의 작업 성능 분석
  4. B-트리
    1. B-트리에서 검색
    2. B-트리에서 삽입
    3. B-트리에서 삭제
    4. B-트리의 작업 성능 분석
  5. 다차원 검색 트리
    1. KD-트리
    2. KDB-트리
    3. R-트리
    4. 그리드 파일

4. 해시 테이블
  1. 해시 테이블 : 검색 효율의 극단
  2. 해시 함수
    1. 나누기 방법
    2. 곱하기 방법
  3. 충돌 해결
    1. 체이닝
    2. 개방 주소 방법
  4. 해시 테이블에서 검색 시간 분석

5. 집합의 처리
  1. 연결 리스트를 이용한 집합의 처리
    1. 작업의 개요
    2. 수행 시간
  2. 트리를 이용한 집합의 처리
    1. 기본 원리
    2. 연산의 효율을 높이는 방법

6. 동적 프로그래밍
  1. 어떤 문제를 동적 프로그래밍으로 푸는가
  2. 행렬 경로 문제
  3. 돌 놓기 문제
  4. 행렬 곱셈 순서 문제
  5. 최장 공통 부분 순서LCS

7. 그래프
  1. 그래프
  2. 그래프의 표현
    1. 인접 행렬을 이용한 방법
    2. 인접 리스트를 이용한 방법
    3 .인접 배열과 인접 해시 테이블
  3. 너비 우선 탐색BFS과 깊이 우선 탐색DFS
  4. 최소 신장 트리
    1. 프림 알고리즘
    2. 크루스칼 알고리즘
    3 .안전성 정리
  5. 위상 정렬Topological Sorting
  6. 최단 경로
    1. 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우 )
    2. 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)
    3 .모든 쌍 최단 경로 알고리즘
    4 .사이클이 없는 그래프의 최단 경로
  7. 강연결 요소

8. 그리디 알고리즘
  1. 전형적인 그리디 알고리즘의 구조
  2. 그리디 알고리즘으로 최적해가 보장되지 않는 예
    1. 이진 트리의 최적합 경로 찾기
    2. 보따리 문제
    3 .동전 바꾸기
  3. 그리디 알고리즘으로 최적해가 보장되는 예
    1. 최소 신장 트리
    2. 회의실 배정 문제
    3 .그 밖의 예
  4. 매트로이드 : 그리디 알고리즘으로 최적해가 보장되는 공간 구조
    1. 매트로이드의 정의와 예
    2. 매트로이드의 확장과 포화
    3. 매트로이드 구조이면 그리디 알고리즘으로 최적해 보장
    ★ 4. 문제 공간 탐색 관점에서 본 매트로이드

9. 문자열 매칭
  1. 원시적인 매칭 방법
  2. 오토마타를 이용한 매칭
  3. 라빈-카프 알고리즘
  ★ 4. KMP 알고리즘
  5. 보이어-무어 알고리즘

10. NP-완비
  1. 문제의 종류
  2. Yes/No 문제와 최적화 문제
  3. NP
  4.. 다항식 시간 변환
  5. NP-완비
  6. NP-완비 문제들
  7. NP-하드를 최적화 문제로 확장하기
  ★ 8. 근사해 구하기
  ★ 9. 현상금 걸린 문제들

11.상태 공간 트리의 탐색
  1. 상태 공간 트리
  2. 백트래킹
    1. 미로 찾기 문제
    2. 색칠 문제
  3. 한정 분기
  4. A* 알고리즘
    1. 최단 경로 찾기 문제
    2. TSP
  Drift 공간 탐색과 끌개

반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

레코드, 키의 정의 및 검색 트리  (0) 2020.12.29
삽입정렬Insertion Sort  (0) 2020.12.27
버블 정렬Bubble Sort  (0) 2020.12.26
선택 정렬Selection Sort  (0) 2020.12.22

스프링 부트에서 스프링 시큐리티를 사용할때 템플릿 엔진을 머스타쉬를 사용해서 로그인 / 회원가입등을 시도할경우 미리 설정한 리다이렉트 주소로 가게 되는경우가있다. 

이때 에러로그가 안찍혀서 난감해지는대 이럴땐 로그레벨을 낮추면 더 자세한 로그를 볼 수 있다. 

#application.properties

#logging
logging.level.root=debug

위와같이 application.properties 파일에 로깅 레벨을 디버그로 설정해준다( 디폴트는 info)

설정하고 다시 로그인 혹은 회원가입을 시도하면 아까랑은 다른 메시지를 볼 수 있는데 스프링 플터체인 로그가나오면서 "csrf"어쩌고 하는 로그가 나온다.

CSRF 란 Cross-site request forgery의 약자로 타사이트에서 본인의 사이트로 form 데이터를 사용하여 공격하려고 할 때, 그걸 방지하기 위해 csrf 토큰 값을 사용하는 것이다. 참조: velog.io/@max9106/Spring-Security-csrf

csrf에대해 서치를해보니 mustache는 csrf토큰을 기본적으로 제공을 안해주기때문에 생기는 문제였다. 
서치를 좀 해보니 인터셉터를 구현해서 모델에 어트리뷰트로 넣어주는 방법이 있었으나... 그럴리가 없다는 생각에 좀더 검색해보니...

스택오버플로우에서 발견했다. stackoverflow.com/questions/26397168/how-to-use-spring-security-with-mustache
역시 설정에 있었다. 다시한번 어플리케이션 프로퍼티를 열고 

#application.properties

#logging
logging.level.root=debug

#mustache
spring.mustache.expose-request-attributes=true

spring.mustache.expose-request-attributes=true 라고 추가해준다.

이제 머스타쉬에서 csrf를 사용할 수 있다. 

 폼에

  <input type="hidden" name="_csrf" value="{{_csrf.token}}" />

 

이렇게 히든으로 csrf값을 넣어주면 csrf로 인한 필터는 통과할 수 있게되었다. 

반응형

'프로그래밍 > 삽질내역' 카테고리의 다른 글

Intellij 톰캣 에러로그 한글깨짐현상  (0) 2019.11.12

유저생성

create user 'ms'@'%' identified by '1234'

% ==> 모든 도메일


**
create user '유저명'@'도메일' identified by '비밀번호''

 

권한부여 

grant all priviliges on test.* to 'ms'@'%' ; 

**
grant all priviliges on [db명].* to 'user name'@'domain';

참조 : www.codingfactory.net/11336

반응형

docker 마리아db 실행 

docker exec -it mariadb bash 


**
docker exec -it [docker name] [실행시킬 툴]
**

 

참조 : happygrammer.github.io/docker/mariadb/

 

도커에 Mariadb 설치

 

happygrammer.github.io

 

반응형

깃허브에 저장소를 생성 후 로컬 프로젝트를 푸시하는 방법입니다.

  1. 깃허브에 레포지토리를 생성한다.

  2. git bash / terminal 등을 연다.

  3. 푸시할 프로젝트 디렉토리로 이동

  4. 디렉토리에서 깃 init실행

    git init 
  5. 첫 커밋을 위해서 git add .

    git add .
  6. 첫 커밋 실행

    git commit -m "initial commit"
  7. 생성된 깃 레포지토리의 url 복사

  8. 커맨드창에서 리모트 레포지터리 url추가
    In the Command prompt, add the URL for the remote repository where your local repository will be pushed.

    git remote add origin [remote repository URL]  
    
    git remote -v
  9. 푸시

    git push -f origin master
반응형

'프로그래밍 > git' 카테고리의 다른 글

[git] git 공식 튜토리얼 문서. 깃튜토리얼  (0) 2015.03.21

맥에 스팀을 깔면 시작시 자동실행되서 여간 거슬리는게 아닙니다. 

 

이제 이걸 꺼보기로합시다.

1. 왼쪽 위에 사과모양을 클릭해서 '시스템 환경설정'에 들어갑니다. 

 

2. 시스템 환경설정에 들어왔으면 '사용자 및 그룹' 에 들어갑니다. 

 

3.'로그인 항목' 탭으로 이동 후 스팀을 클릭하고 '-' 버튼을 울러줍니다.

 

끝.

반응형

안녕하세요 예지우랑입니다.
본인은 Intellij를 매우 좋아하는데 그 이유는 정말 인텔리하기때문입니다.

스프링 프로젝트를 하는데 이상하게 톰캣 로그의 한들이 깨지는 형상이 있어서 여러가지 삽질을 해봤습니다.
다음은 해당 현상을 해결하기위한 노력에대한 글입니다.

1. vm옵션 인코딩 설정
intellij 설치 폴더에 가시면 intellij.exe.vmoption 과 intellij64.exe.vmoption 라는 파일이있습니다.
해당 파일을 메모장으로 여시고

-Dfile.encoding=UTF-8

라고 추가해줍니다.
그후

Edit Configurations 를 클릭하시고

이렇게 추가해줍니다.

결과는 -실패

2.  위에 1에서 했던 editconfiguration에서 vmoption에

-Duser.language=en
-Duser.region=US

이렇게 추가해줍니다.

이러면 로그가 영어로나오면서 한글이 깨지는 현상은 사라기지게 됩니다.

결과는 성공!

 

원인은 톰캣이 한글판이라서 로그를 한글로찍기때문이라는걸 어디서 읽었는데 정확히 확인해보진않았습니다.
어쨋든 로그나 오류메시지는 영어가 더 읽기 좋기때문에 영어로 사용하기로합시다.

감사합니다.

반응형

FIFO

메소드 : createQueue

enQueue: queue에 원소를 삽입

deQueue : queue에서 원소를 추출( 반환 후 삭제)

delete : queue에서 원소를 제거(그냥 삭제)

isEmpty

peek : 가장 먼저 들어와있은 원소를 검색하여 반환

 

선형큐 

연결큐

원형큐

덱(Deque, Double-ended Queue) 큐 양끝에서 삽입/ 삭제 발생 가능, 스택과 큐의 연산을 모두 가지고있다.

반응형

'프로그래밍 > 자료구조' 카테고리의 다른 글

스택  (0) 2019.06.09
연결 자료구조  (0) 2019.06.09

+ Recent posts