/Algorithm

Algorithm Study

Primary LanguageJava

Algorithm Site

Todo

알고리즘 시간복잡도를 최우선으로 두지 않습니다.

실제 프로그래밍 일을 진행 할 때, 필요할 요소를 고려하여 작성했습니다.

  • 코드 가독성

    • Java8 Stream API로 가독성을 높일 수 있는 코드는 최대한 Stream을 이용했습니다.

  • 객체지향 캡슐화

    • 요구사항을 클래스로 정의했습니다.
      • 너무 쉬운 개념은 굳이 클래스로 정의하지 않았습니다.
      • 분할 정복으로 생각해야할 문제가 있다면, 하위 문제로 정의된 것을 클래스로 표현하였습니다.
    • 디미터 법칙을 최대한 적용했습니다.

해당 문제를 푸는것 보다, 새로운 문제를 받았을 때, 접근할 수 있는 힘을 기르는것이 더 중요하다고 생각합니다.

  • 문제를 못 풀었을시, 답안을 참고 하되 배운점을 토대로 생각하는 방법에 대해 기술 했습니다.
  • 답안을 참고 해도, 이상하다 싶은 문제는 이상한 이유에 대해 기술 했습니다. (개인의견이라 틀릴 수 있음.)

알고리즘 개념에 대해 정리하고 공부합니다.

  • 외우는것이 아닌 이해하는걸 목표로 글로 작성하여, 설명했습니다.
  • 알고리즘 개념 공부 리스트를 참고해주세요.

Algorithm Concept

UnSolved List

도전 했지만 풀지 못한 문제 리스트 입니다.

Programmers

level name reason
2 H-Index 정렬 후, 큰 값에서 차례대로, h번 이상 인용된 논문을 찾는 코드에서 무엇이 틀렸는지 모르겠습니다.
3 종이접기
3 N으로 표현
3 입국심사 시간 기준 바이너리 서치로 문제를 해결하는 것은 좋지만, 발견된 해 보다 더 작은 시간이 있을 수 있다는 조건이 이상한거 같습니다.
3 브라이언의 고민
4 4단 고음

BOJ

number name reason
2866 문자열 잘라내기 이분 탐색으로 어떻게, 중복을 찾는지 이해가 가질 않습니다. 이분 탐색에 대해 한번더 공부하고, 이분 탐색에 관련된 쉬운 문제를 몇개 풀어본 후 해당 문제를 다시 분석해봐야 할거 같습니다.
1956 운동 플로이드 와샬 알고리즘을 응용해야 합니다. 플로이드 와샬을 연습 해본뒤 풀어봅니다.

What Learned

Programmers

level name reason
2 조이스틱 바꿀 문자열을 찾는 알고리즘를 그리디로 해결 해야하는지, NP로 해결해야 하는지 감이 오지 않은거 같습니다. 그리디 vs NP에 대해서 학습해야 합니다.
2 라면공장 스톡을 날짜에 맞춰 사용하는 불필요한 코딩을 하여, 알고리즘이 더 어려워졌습니다. 요구사항이 아닐시엔, 필요없는 로직은 작성하지 않기로 했습니다. 또한, 잘못된 동시성 생각이 이문제를 어렵게 생각한 이유습니다. 특정 날짜를 지나치면 그 날짜를 다시 못고를거라 생각했지만, 뒤늦게라도 그 날짜를 추가해주면 과거에 그날짜를 선택하고 나아간것처럼 만들 수 있어서, 최대 힙 자료구조로도 풀 수 있는 형태로 바꿀 수 있다는것을 배웠습니다.
2 영어 끝말잇기 끝에 다다르면, 다시 처음 순서로 돌아오는 구현을 Queue 로 시도했습니다. 이것도 나쁘진 않지만 컬럼의 수가 정해져 있다면, %연산과 / 연산으로 column , row 를 구하면 더 쉬운 코드가 됩니다. column = n % index, row = n / index
2 구명보트 처음에는, 무게가 작은 순서대로 사람을 태웠는데 그 풀이는 명수 제한이 없는 구명보트에 맞는 풀이법이다. 2명 밖에 못타므로, 구명보트에 탄 인원의 무게의 합이 가장 최대 일 경우가 구명보트에 최적화 되므로, 큰 무게 + 작은 무게의 합으로 생각해야 함을 알 수 있다. 제일 무게가 큰 사람과 제일 무게가 작은 사람이 함께 못 탄다면 제일 무게가 큰 사람은 죽었다 깨어나도 혼자 탈 수 밖에 없음을 생각할 수 있는것이다.
3 입국심사 완전 탐색이 아닌, 최소로 걸리는 시간과 최대로 걸리는 시간을 구할 수 있으면 그 시간 사이 에서의 경우로 문제해결을 시도할 수 있습니다.

BOJ

number name reason
2606 바이러스 서로소 집합으로 풀어야 하는것은 알고 있었지만, 각 원소를 root 로 설정해주는 코드가 항상 최상위 루트로 설정된다고 착각 했었습니다. 1->2 >> 2->3 순으로 순차적으로 그래프가 그려지면 이상적으로 root 가 1로 설정됩니다. 하지만, 2->3 >> 1->2로 설정할 시 3번은 1로 업데이트가 되지 않습니다. 그렇기에 마지막에 그룹을 찾을때도, find 메서드로 찾아야 합니다.
16234 인구 이동 visit 체크를 할 때, Stack 에서 Pop 된 원소를 기준으로 하느냐, Stack 에 넣을 다음 원소를 기준으로 체크를 하느냐의 기준을 생각할 필요가 있습니다. 이는 복잡도를 증가 시킬 수 있으므로, from -> to 를 체크 해야 하느냐 자기자신만 체크하면 되느냐를 생각해야 합니다.

Union-Find 개념으로 순회시 다수의 그룹군을 생성하는 방법도 있지만, 순회안에서 하나의 그룹만을 목표로 찾는 코드도 가능합니다. 그룹군이 만들어진 요소는 visit 표시를 하여, 중복으로 순회하지 않도록 하는것이 핵심입니다.
1620 나는야 포켓몬 마스터 이다솜 데이터를 양방향으로 조회 할 필요가 있어, Map을 두개 만들어서 처리했습니다. 하지만 데이터 포맷을 String 으로 설계하면, 굳이 Map 두개를 사용할 필요 없이 Map 하나로도 조회 할 수 있습니다. ex) Key: 숫자문자열, 이름문자
6603 로또 dfs 탐색시, 결과값 저장은 단일 인스턴스 자료구조로도 가능합니다. 이유는 해를 하나 찾을 때 까지, 다른 연산이 관여하지 않기 떄문입니다. 다음 해를 찾을 때는 덮어씌우기 때문입니다. 물론, 자료구조의 크기가 해의 크기 보다 큰 경우는 이전에 답을 찾은 결과물이 남아 있을 수 있는것에 주의해야합니다.
2799 블라인드 단순히 order 순으로 블라인드 종류의 인덱스 번호로 사용해서 풀었지만, 블라인드 종류 자체를 인덱스 번호로 사용하는 아이디어를 배웠습니다.
1296 데이트 특정 값을 구할 때, 조건이 여러개 인 경우에 값을 모아서 정렬로 특정 값을 구했습니다. 하지만, 하나의 값을 지정해놓고, 값이 구해 질 때마다 조건을 검사해서 값을 하나 남기는것이 더 효율적입니다.
10708 크리스마스 파티 조건에 맞지 않는 카운트를 구할 때, 이미 만들어진 자료구조에 쌓을 수 있는 구조면 굳이 카운트를 하지 않고 자료구조에 쌓으면 되는 아이디어가 있습니다.
2800 괄호 제거 무작위로 지운 값들의 조합이라면 중복이 생길 수 있다는 사실을 생각해야 합니다.
5177 괄호 제거 두 값을 비교할 때, 데이터 정제를 미리 하는 경우가 훨씬 유리하다면, 시간복잡도를 조금 포기하더라도 정제 부터 진행하는게 좋은거 같습니다.
11725 트리의 부모찾기 visit 을 체크할 때, 방향까지 체크 해야 하는지 노드 방문만 체크 하면 되는지 기준을 잘 생각해봐야 합니다. 더불어 방향 체크는 메모리를 무척 많이 쓰게 됩니다.

열

What To Do

Programmers

level name reason
2 타겟 넘버 dfs 탐색에서 습관적으로 for문을 사용했는데, 해당 문제는 for문이 필요 없었습니다. 동전문제를 풀 때, for문을 사용했던기억이 있는데 차이점이 무엇인지 공부가 필요합니다.