오늘 할일

• 에라토스테네스의 체 복습
• 알고리즘 문제풀이
• 포트폴리오템플릿 찾기

오늘 한 것 & 배운 내용

알고리즘 문제 풀이

소수

• 에라토스테네스의 체 복습
  • 다시 읽어보니 2부터 시작하여 n의 제곱근까지의 모든 배수들을 지워주는 방식으로 진행이 된다(소수가 나오면 소수의 모든 배수들은 소수가 아니라는 정의를 이용한 방법)
    • 개념이 어렵다면 아래의 그림 링크를 클릭하면 한번에 바로이해할 수 가있다
    • https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FvcP21%2FbtqDp03wCZB%2F2zaIgivKDhL6PQp7AQpIb1%2Fimg.gif
  • 에라토스테네스의 체의 시간복잡도는 O(Nlog(logN)) 이라고 하는데 사실 잘이해하지는 n의 제곱근 까지 탐색하는 과정에서 탐색을 안해도 되는 수를 계속 줄여나가는 방식이기 때문에 빠를 수 밖에 없다는 것은 이해가 된다
  • 내풀이
    • 설명과 예제를 통해 소수 문제를 다시 풀어보았는데 확실히 성능면에서 좋아진 것을 확인할 수 있었다

단어 정렬

• 내풀이

  • 먼저 중복값은 한번만 출력하기로 했기 때문에 중복값을 제거하기 위해 Set을 이용하기로 하고 Set에 정렬할 모든 입력값을 입력하였다
  • Set으로는 정렬하기 어렵기 때문에 Set을 다시 List로 바꾸어주었다
    • ArrayList의 생성자에 아규먼츠로 set을 넣어주면 간단하게 list로 변환이 가능하다
  • 단어를 길이순으로 우선 정렬하고 길이가 같으면 사전순으로 정렬하는 것이지만 먼저 사전순으로 정렬을 해두어 길이만 한번더 정렬할 수 있도록 한다
    • 미리 사전순으로 정렬해 놓으면 후에 길이순으로 정렬하더라도 같은 길이의 단어는 사전순이 유지가 되기 때문이다
  • Comparator을 구현한 ListComparator 클래스를 만들어 단어의 비교를 하도록 하고 list.sort(new ListCompartor)를 통해 사용한다
  • List를 순회하며 정렬된 값을 출력한다

• 다른사람풀이

  • 참고 : https://st-lab.tistory.com/112

    • 입력된 단어들을 배열에 넣는다

    • Arrays.sort를 사용하고 람다식을 이용해 Compartor를 재정의 한다

      • 길이가 같을때는 String에 compareTo 메소드를 이용하여 사전순으로 비교하고 그외에는 길이를 비교하도록 재정의한다

    • 출력할 때 값을 체크해 이전 값과 같은 값이면 출력하지 않도록 하여 중복값 체크를 해준다

• 배운점

  • 정렬을 위해 Comparator 를 재정의 해서 사용하는 것을 연습해 볼 수 있는 좋은 문제였다
  • Compartor를 람다식을 이용해 깔끔하게 재정의하는 방법을 연습할 수 있었다
  • String은 compareTo 메소드를 이용해 정렬하는 것을 다시한번 생각해볼 수 있었다
  • compare의 return은 양수,음수,0 이면 되기 때문에 3가지 상황으로 나누어서 조건문을 만들었지만 구지 그렇게 하지 않고 s1 - s2 같은 수식으로 표현하면 알아서 return값이 정해진다

덩치

• 내풀이
  • 처음엔 정렬을 통해 정렬을 해놓고 값을 비교해서 rank를 ++해가는 방식으로 풀려고했는데 출력되는 순서가 rank순이 아닌 입력받은 순이어서 풀이방법을 변경하였다
  • 키와 몸무게를 입력받을 이중 배열을 만들고 순위를 기록할 배열을 하나 만든다
  • 2중 for문을 통해 입력값으로 배열을 초기화하면서 순위 배열도 모든 값을 1로 초기화 해준다
  • 2중 포문으로 완전 탐색이 가능하도록 작성하여 처음 값부터 n-1값 까지 하나씩 뽑아서 index상 뒤에 있는 모든 값과 비교하여 둘다 큰경우, 둘다 작은 경우로 나누어 비교한다
    • 원래 값이 비교값보다 둘다 작다면 원래 값의 순위를 ++하고 원래 값이 둘다 크다면 비교값의 순위를 ++해준다
    • 위의 경우가 아닌경우 같은 rank로 보고 아무것도 더해주지 않는다
  • 계산된 순위 배열을 StringBuilder를 이용하여 출력한다
• 다른사람풀이
  • 참고: https://st-lab.tistory.com/99
    • 순위 배열을 만들지 않고 모든값을 그대로 비교하여 값만 StringBuilder에 추가해주는 방법이 있었고 성능도 더 좋은 것 같다
• 배운점
  • 문제를 꼼꼼히 읽어서 모든 조건을 확인해야 중간에 풀이방법을 바꾸는 불상사가 일어나지 않을 것 같다

좌표 정렬하기

• 단어 정렬과 거의 비슷한 유형의 문제로 복습을 위해서 풀었다

• 내풀이

  • 2중 배열을 만들어 입력값을 초기화한다
  • Arrays.sort로 정렬하되 Comporator를 람다로 재정의하여 x값 으로 정렬하되 같으면 y값으로 정렬하도록 한다
  • 정렬된 배열을 출력한다

요세푸스 문제

• 원을 돌듯이 값을 뽑기 위해서 index를 배열의 길이가 넘어가면 배열의 길이로 나누어주어서 나머지를 다시 +해주는 방식으로 풀기로 계획

• 내풀이

  • 값을 빼기 쉽도록 배열이 아닌 List를 활용해서 1~N까지 값을 초기화한다
  • while문을 만들어 n >0인 범위내에서 돌아가도록 만든다
    • n은 값을 뽑을 때마다 줄어들기 때문에 값이 하나도 없을 경우까지는 반복이 되어야 한다
  • index 변수를 만들어 while문이 돌때마다 +k를 시켜주어서 몇번째 index에서 값을 빼와야 되는지 기억하게 한다
    • index는 1이 아닌 0부터 시작해야되니 -1로 초기화 한다
  • index의 값이 n을 초과하면 index를 n으로 나눈 나머지를 다시 index에 대입하여 한바퀴 돈것처럼 index가 작동하도록 조건문을건다
  • 조건문을 빠져나온 index를 list에서 remove 메소드에 넣어주어 값을 뽑음과 동시에 StringBuilder로 추가하게 한다
  • 값을 하나 빼왔으니 원의 크기가 줄어든걸 표시하기 위해 n을 --해주고 index도 하나씩 줄어들기 때문에 index도 --를 해준다

• 다른 풀이

  • 리스트가 아닌 큐를 이용해서 푸는 풀이를 찾아보았다
    • 참고 : https://steady-coding.tistory.com/21
  • 큐를 1~N 까지 초기화한다
  • while문을 만들고 q의 size가 1보다 클동안 돌아가도록 한다
    • 마지막 출력이 조금 다르기 때문에 0까지 돌리지 않고 마지막은 따로돌려준다
  • for문을 k-1번 돌려 queue에서 값을 poll 해서 다시 offer를 하여 원을 돌리듯이 값을 돌려준다
  • 한번더 poll을 하여 k번째 값을 꺼내 출력하는 것을 큐의 size가 1남을 때까지한다
  • 마지막 한번더 poll을 하고 ">"을 붙여주어 출력해준다

• 배운점

  • Queue를 통해 원을 돌듯이 자료구조를 구현하는 것을 더 직관적으로 구현할 수 있음을 배웠다
  • List로 구현한것이 시간+메모리 적으로 훨씬 효과적(5배 이상)이 었지만 구현이나 가독성은 Queue로 구현한 것이 더 직관적이었다
    • 알고리즘을 푸는 방법은 여러가지지만 성능이야 가독성이냐의 선택은 푸는 사람의 몫이되는 것 같다

체스판 다시 칠하기

• 8X8사이즈로 잘라서 체크하되 가로세로로 늘어나는 것을 체크해주기 위해 가로 축 세로축을 추가하여 4중 for문을 통해 모든 경우의 수를 다 체크해보기로 계획을 세웠다
• 나의풀이
  • 입력값을 받아 2중 배열을 통해 체스판을 초기화 하였다
  • 4중 for문을 만들고 세로축 가로축인 i,j는 각각 n-8 m-8로하여 최소 8X8을 탐색할 수 있는 범위를 지정하여 완전탐색하도록 하였다
    • k, j 는 범위를 0에서 8미만으로 하여 가로세로 8개칸을 체크할 수 있도록 범위를 설정하였다
  • 가장 왼쪽위에 칸을 기준점으로 삼아 00~ 7,7 까지 모든 칸을 체크하는데 한칸체크할 때마다 기준이 되는 글자를 뒤집어서 체크함으로 페인팅해야될 칸을 count했다
  • count를 마치면 min값과 비교해서 더 작으면 min값에 넣고 다음 체스판을 체크하도록 하였다
    • 연산을 줄이기 위해 칸을 체크하는 중에 현재의 min값보다 커지면 반복문을 빠져나가 다음 체스판을 체크하도록 하였다
  • 이렇게 까지 풀었는데 예제는 맞는데 제출시 답이 맞지가 않아 한참을 디버깅하고 검색을 해보다가 반례를 찾았다
    • 첫값을 기준으로 체스판의 페인팅할 곳을 찾았는데 반례를 보니 첫 값만 바꾸면 모두 맞아지는 경우도 생기기 때문에 첫값이 W인 경우와 B인경우를 모두 따져봐야됬다
  • k,l 반복문 이전에 2번반복하는 반복문을 추가해 B인경우와 W인경우 모두 돌수있도록 해서 제출했더니 통과하였다
    • 당연히 왼쪽 맨위가 기준이라고 생각했는데 생각해보니 기준은 최소 값인 것이지 왼쪽위는 아니었다..
• 다른사람풀이
  • 다른부분은 크게 다르지 않았는데 백색 흑색으로 나뉜 것을 boolean으로 표현한 것과 백으로 시작한 경우와 흑으로 시작한 경우를 따로 중복문을 이용하지 않고 64-다른한쪽으로 구한값으로 하여 한쪽을 그만큼 칠하면 다른쪽으로 시작햇으면 전체에서 그만큼을 빼준 만큼이 될거라는 자명한 사실을 이용했다
    • 참고 : https://st-lab.tistory.com/101
• 배운점
  • 아직 문제 해석이 부족함이 보이지만 이런 케이스들을 계속 쌓아가다보면 발전할거라고 생각한다
  • 전체케이스에서 한쪽으로 구한케이스를 빼줌으로 다른 케이스를 구하는 방법 같은건 두고두고 써먹을 수 있는 방법같으니 기억해두면 좋을 것 같다
  • 중복문자체가 많아져서 이렇게 풀면 안될거라고만 생각해봤는데 시간복잡도를 생각하면 계속 n만큼 증가되는게 아니었으니 중복문이 몇개인지 보다는 그 안에서 얼마나 연산이되는지를 체크해보면서 사용하는게 더 좋은 접근인 것 같다

포트폴리오 템플릿찾기

• 토요일날 미리조사해둔 것 위주로해서 포트폴리용 웹페이지 템플릿을 찾고 있다
  • 노션을 이용해 포트폴리오를 만든사람들도 있었는데 생각보다 괜찮아보였다
• 템플릿을 찾더라도 사용방법에 대해서 제대로 정리해두지 않으면 사용할수가 없어서 아쉬운경우가 생겨서 맘에드는 걸 찾더라도 사용법이 제대로 되어있나 찾게된다
  • https://github.com/saadpasta/developerFolio
  • 위의 사이트가 굉장히 자세히 나와있어서 한번 천천히 따라해보는 것으로도 다른 템플릿 적용할때도 도움이될 것 같아서 내일해보기로했다
• 다른 사이트보단 Github에 공유된 템플릿이 사용하기 익숙해서 위주로 찾다가 토픽에 portfolo-template란이 있는걸 발견하고 더 깊게 찾아보기로했다
  • https://github.com/topics/portfolio-template

내일 할일

• 알고리즘 문제풀이

• 포트 폴리오 예시템플릿 적용해보기

• 포트 폴리오 템플릿 찾기