동글동글이
2k
2019-07-12 17:24:46 작성 2019-07-12 17:26:26 수정됨
12
1036

알고리즘 문제 보다보면 ... 시간복잡도


이중 포문은 최대한 하지말라고 하잖아용?

시간복잡도 때문에

근데 이중 포문 안쓰려고 사용하는

API들을 보면 똑같은 것 같아서요

예로 들자면 배열의 sort라던지, equals라던지 

이런것들도 다 내부적으로 for문을 타서 작동을 하는걸텐데

어불성설 아닌가 싶어서..

어떻게 생각하세요 ㅎㅎ

알고리즘 초보라서 잘 모릅니다..


대표적인 걸로 아나그램이요 !

https://jaybdev.net/2017/06/11/Algorithm-8/

이 블로그 글 보다가 문득 든 생각이었어용

2
0
  • 댓글 12

  • ignoreOrange
    1k
    2019-07-12 17:49:34 작성 2019-07-12 17:52:43 수정됨

    이중포문까지는 하게되지 안나요

    링크걸어주신 본문에 나온

    Anagram 

    은 정말 쉽게 풀수있는 문제입니다. 2중포문을 사용한다는 거 자체가 너무 비효율적이라 나온 말 아닐까 합니다. 다른 문제들은 2중포문까지는 사용해야하는 문제들이 대부분이지 않나 쉽네요

    1
  • 흥미진진하군
    76
    2019-07-12 17:58:21

    ignoreOrange 


    1. 문자를 스플릿으로 배열로만든다

    2. 소트와 대문자 혹은 소문자로 정렬한다 

    3. 다시 역 스트링 후  equals 로 비교한다


    for 문이 전혀 필요가없네요 


    1
  • bh
    403
    2019-07-12 19:13:45 작성 2019-07-12 19:14:51 수정됨

    #흥미진진하군

    이미 정렬과, 역스트링 메소드

    자체 내부에 for가 들어가있죠.

    내가 직접 for문을 안 쓸뿐이죠.


    예를들어

    자바의 sort, reverse 그냥 호출해서 사용할꺼면

    굳이 알고리즘을 공부할 필요가 없죠.

    이미 최적 알고리즘 다 계산해서 만들어져있는 기능인데.

    그냥 호출해서 쓸꺼면 문제푸는 의미가..


    저는 알고리즘 수업때

     c++로 주로했는데 STL쓰면 바로 0점처리..

    거의 모든 문제를

    변수 / if  / for문 딱 3가지만 이용해서..

    1
  • bh
    403
    2019-07-12 19:21:06
    수업들은지 오래되서 가물가물하긴 한데

    음 알고리즘을 공부하다보시면 

    그래프탐색 알고리즘
    동적프로그래밍
    등등 

    은 거의 지금까지 알려진
    최적 알고리즘이 이중포문(즉 time complexity가 n^2)
    을 많이 활용할꺼에요.

    이중포문까지는 데이터 갯수 n이 몇개인지에 따라서
    상황껏 충분히 활용해도 됩니다.

    근데 그 이상으로 (삼중포문.. )등은
    완전탐색(그리디) 기법 아닌이상은 거의 못본거 같네요

    1
  • ISA
    1k
    2019-07-12 19:21:08

    2중포문을 거의 할 이유가 없습니다. 포문을 2번써야하면 순차적으로 사용하십시오 사용하는 자원이 다릅니다.

    -1
  • rezigrene
    1k
    2019-07-12 19:54:49

    질문자님이 말씀하신대로 내부에 for문이 존재합니다만,

    이중 for문을 안만드려고 하는게 아니라 기본으로 제공되는 건 활용하고 다른부분의 구현에 집중하는거라 보시면 됩니다.

    모든 알고리즘 해결을 위해 sort처음부터 구현할 필요까진 없으니.

    1
  • ISA
    1k
    2019-07-12 20:00:26
    Rezi //
    언어에 따라 다르지만 for문이 아니라 그보다 저수준 예를 들면 어셈블리어로 만들어진게 아닌가요? 정말 같은 for문인가요?
    -1
  • rezigrene
    1k
    2019-07-12 20:02:35

    추가로 말씀드리면 본문의 링크 두번째 해결책의 시간복잡도는 sort를 사용했으므로 NlogN 에 가깝습니다.


    좀더 잘짜면 N까지 가능하겠지만 sort등을 사용했을때보단 코드가 길어지겠죠.

    1
  • rezigrene
    1k
    2019-07-12 20:04:41

    // ISA

    반복하고 그만큼 시간을 소모한다는 본질은 변하지 않습니다. 어차피 다기계어로 번역될테니.

    2
  • ISA
    1k
    2019-07-12 20:16:31

    Rezi//

    전 체감하기를 다르게 체감해서 그런지 같은 for문이라는 생각은 안들었습니다 반복구조가 있지 for문을 써서 돌아간다? 라는건가요 아무튼 감사합니다. 고수준의 언어에서는 2중포문같은걸 사용할경우 리소스 사용이 심각한걸 경험한지라 동기 비동기 같은 맥락일 수도 있겠네요..감사합니다

    -1
  • Whislter
    370
    2019-07-13 00:09:25

    같은 이중 포문도

    N안에서 N만큼 도는거와

    N안에서 정해진 상수 횟수만큼 도는건 다릅니다.


    1
  • 원숭이부대
    691
    2019-07-14 13:22:18 작성 2019-07-14 13:57:34 수정됨

    자바API를 쓴다고 무조건 빠른건 아닙니다. API 나름입니다.


    예를 들어 자바에서는 Map 이라는 컬렉션이 존재하는데,

    if (Map.get() != null) 인 경우에 나온 값에 +1 해서 put()을 쓰는 경우 Intellij에서는 merge()를 사용하는건 어떠냐고 워닝이 뜹니다.


    Map.merge(key, 1, Integer::sum)  이런식으로요.

    Map의 upsert 메서드라고 보시면 됩니다.


    근데 알고리즘 문제 중 이 Map.merge를 사용해서 연산했는데 0.02초 정도로 성능이 안나와서 Performance 점수가 만점이 안되는 경우가 실제로 있었어요.

    merge를 쓰지 않고 get() 후 +1하고 put()을 쓰면 이 0.02초가 해결이 됩니다.

    (물론 get(), put()도 API지만..)


    실제로 merge() 소스를 까보면 내부에서 단순히 get -> 연산 -> put 이 아니라, 어떤 연산이 많더라구요.

    (뭔지는 다 보지는 않아서 모르겠어요)


    게다가 for문 내에서 merge를 쓴다면 오버헤드는 루프도는 배수만큼 추가되겠죠.

    이게 10~20ms 정도라면 사실 실무에선 엥간해서는 큰 문제는 안되겠지만요.


    자바 API를 쓰는건 소스도 짧아지고 편하긴한데, 위에 상황처럼 0.02초.. 즉 ms 단위 (0.02초는 20ms임)로 성능을 최대한 뽑아야 하는 경우에는 잘 알고 써야 만족스러운 결과물이 나올겁니다.


    자바 내부 API가 유용하면서도 빠른건 대표적으로 정렬이 있겠죠

    Arrays.sort()는 주어진 배열의 크기에 따라 정렬 알고리즘이 달라질 정도로 성능을 고려해서 짠거니까요.  

    (Collections.sort()는 내부적으로 Arrays.sort()를 쓰는 것으로 알고있음)


    소스를 까면 내부에 특정 사이즈가 하드코딩되어있는데.. 왜 이 값인가 싶었더니(7인가?)

    7 이하인 경우 / 7 이상인 경우 정렬 알고리즘 A, B의 시간복잡도를 각각 계산하였더니 그 경계값이 7이었습니다.


    빅오 표기법 기준으로 계산 시

    n이 7 이하면 A가 일반적으로 빠르고

    n이 7 이상이면 B가 일반적으로 빠르다는 수학적 계산이 들어가있는거죠.

    (근데 JDK가 업그레이드 되면서 위 로직은 안보이네요. 전에는 7로 하드코딩 되어있었는데 

    1.7인가 1.8 이후로는 팀소트, 듀얼피봇퀵소트 쓰는걸로 알고있습니다.  java.util.TimSort에서 7이라는 상수값이 있긴 하네요)


    위에 말씀하신대로 자바 API 중에서도 어느 개발자가 짠 것처럼 단순 for문 돌리는 것도 있기 때문에, 소스코드상에서 for 루프가 보이지 않고 자바 API를 쓴다고 해서 아예 안쓰는건 아닐 경우가 많죠.


    그래놓고 어? 나는 자바 API 사용했고 for도 사용 안했는데 왜 성능점수가 안나오지?

    라는 케이스는 애초에 그렇게 풀면 안되는문제였던거죠.

    아니면 그렇게 해도 되긴하는데 제가 말한 merge()와 같은 상황일 수도 있구요.


    좋은 고민같습니다. 성능안나오네? 소스짧으니 걍쓰지뭐 ~ 보단 낫죠.


    그리고 개인적으로 위에서 말씀하신 교수라는 분이 신입 나부랭이인 저보다 훨씬 고수겠지만,

    API를 안쓰게 하는건 사람의 관점의 차이지만 좀 아쉽습니다.

    다만,정렬을 쓰는 과제에서 API를 썼다면 그 API를 쓴 이유에 대해서 내부적으로 알고리즘적으로 설명과 함께 제출하라고 했다면 정말 연륜있는 교수님이라고 할 수도 있었겠네요.

    (내부 API를 잘 모르는 학생 입장에선 이게 시간이 더걸리겠죠. ㅋㅋㅋ)


    그래도 자바 수업이 아닌 알고리즘 수업이었고, 모든 알고리즘을 타겟으로 한다면 어느정도 이해는 가네요.

    3
  • 로그인을 하시면 댓글을 등록할 수 있습니다.