본문 바로가기
  • Trace

취업/알고리즘이야23

DFS 깊이 우선 검색 딱히 저장공간이 필요하지 않은 듯. DFS 특징 : 스택을 사용함 1) 방문할 노드를 넣는다 2) 방문함 표시한다. 3) 재귀로 돌린다. (start는 다음 노드) BFS VS DFS 특징 : 큐를 사용함 1) 방문할 노드를 넣는다 #전용 queue 2) 방문함 표시한다. #전용 list 3) 방문한 노드에 연결되어있는 노드들을 큐에 다시 붙인다 특징 : 스택을 사용함 1) 방문할 노드를 넣는다 2) 방문함 표시한다. #전용 list 3) 재귀로 돌린다. (start는 다음 노드) # 다음 노드를 재귀로 접근 [굳이 자료형에 넣지 않고 그냥 재귀로 바로 접근] 구현이 생각보다 어렵지 않음 2022. 4. 13.
BFS 너비 우선 검색 특징 : 큐를 사용함 1) 방문할 노드를 넣는다 2) 방문함 표시한다. 3) 방문한 노드 빼고, 노드에 연관된 다른 노드를 큐에 더한다. 반복 2022. 4. 13.
[지금 하고 있는 것] * 알고리즘 + 자료 구조 지식을 까먹에서 youtube로 복구중.. * 프로그래머스 부지런히 * 백준? tier 시스템을 처음 사용했다! 열심히 레벨 올려야지ㅎㅎ 2022. 4. 6.
파이썬 함수를 생각없이 쓰면 피를 본다 max.. 2022. 4. 6.
프로그래머스 > 탐욕법 > 체육복 remove()가 리스트원본을 훼손시키는 경우, 반복문이 비정상적인 동작(요소를 건너 뜀)을 간과했음 여기서 뱅글뱅글 돌았음.. [hint] 1) 첫 번째 틀림 : 코드가 오름차순으로 진행되니까, 아래서부터 처리해야함. 2) 두 번째 틀림 : ????? -> 누군가 sort를 써보라 했는데, 다른 문제가 더 생겨났다? 3) 세 번째 틀림 : ????? -> 한창 찾다가 remove가 문제였음을 알았음 사실, 내 방식대로 하면, sort가 의미가 없음. 대신 효율성이 매우 떨어짐.. 나는 lost에 중점을 두었지만, 다른 분들은 reserve에 중점을 둔 듯 이후에는 이 코드를 개선해봐야겠다. 1) reserve 중심 2) 효율성 개선 풀이 코드 1) lost와 reserve의 중복 인원은 모두 제거 : .. 2022. 4. 6.
그리디 미래를 생각하지 않고, 현재 가장 최적의 방법을 취하는 것 그리디 : 특정 algo가 없 전제 1) 앞의 선택이 뒤의 선택에 영향을 주어선 안됨. 2) 문제의 최적 해가 부분 문제의 최적 해 여야 함 2022. 4. 6.
remove 반복문 주의 https://devpouch.tistory.com/110 [python] list로 for문 돌면서 remove할때 주의할점 원래 리스트를 for 문을 돌면서 원소를 하나씩 제거하려고 했는데 원하는 대로 되지 않았다. 문제는 다음과 같았다. 리스트를 돌면서 원소를 제거할때 >>> l = [1, 2, 3, 4, 5] >>> >>> for i in l: ... print(i). devpouch.tistory.com 리스트가 훼손되므로 a[:] 식으로 복사본을 사용해야함 2022. 4. 6.
헷갈림 : enumerate / iterator / generator iterable : 반복 가능한 객체 list, dict, set, str, bytes, tuple, range enumerate : 인덱스와 iterable 가능한 요소를 같이 반환 (튜플) box = ['a','b','c','d'] box_e =enumerate(box) for i, e in box_e: print(i, e) # 0, 'a' 이런식으로 출력됨 iterator : 값을 차례대로 꺼낼 수 있음 iter()로 이터레이터로 만들 수 있음 iter : 매직메소드 next : 이 메소드로 호출하여 iter의 객체를 하나씩 가져ㅐ올 수 있음 StopIteration 에러 : 요소가 다 반환되면, 해당 에러가 반환됨 a = [1.. 2022. 4. 2.
프로그래머스 풀면서 느끼는 점 프로그래머스 풀면서 느끼는 점을 수시로 추가하고자 한다. 수정일 : 03.20 1. 시간복잡성이 낮을 걸 써야한다! O(n) 조차도 적게 사용하기, 중복되는 반복문 줄이기 2. 반복문에서는 답이 나오면 바로 return 3. 자료형의 메소드 특징을 완전히 숙지 2022. 3. 20.
프로그래머스 > 스택/큐 > 프린터 리스트로 큐를 구성하는 것보다, deque를 사용하여 큐를 만드는 것이 더 시간 효율성이 좋다고 들었다. (나xx님 유툽) 조건을 지정할 때, 초기에 꽤나 까다로웠다. 같은 우선순위를 가진 작업 중 내가 원하는 작업을 어떻게 구별할 것인지에서 고민을 했었는데, 아래 두 요소로 풀 수 있었다. 첫번째 : 큐에서의 최대 우선순위 두번째 : 내 작업의 현재 인덱스 위치 일단, 작업물 중 최대 우선순위가 무엇인지 파악 전체 반복문에서 무조건 하나를 pop 하고 생각한다. 1) 최대 우선순위가 내 작업물 우선순위랑 동일한가? 1.1) 내 작업물은 pop된 작업물과 동일한 인덱스인가? 1.1 else ) 최대 우선순위이면 일단 작업 수행 1 else ) pop한 작업물을 뒤로 옮긴다. 각 과정에서 필요한 내 작업물.. 2022. 3. 19.
프로그래머스 > 해시 > 완주하지 못한 선수 처음으로 프로그래머스 문제를 풀어봄. 1번이라 껌이겠지~~ 했지만, 아니.. ㄷㄷ 예외 고려 + 효율성... 나는 개발을 다시 공부해야하는걸까..ㅎ 풀이 모듈 안쓰고 풀려고 함. 잘못풀이 1) in을 사용하여 조건에 따라 순차적으로 처리 -> 통과한 사람은 여분의 리스트에 저장하기를 했다. -> fail => 나중에 보니까 동명이인이 둘 다 통과할 경우를 고려하지 않았음 -> 반복문이 겹겹. fail.. -> 검색하니까, 리스트의 in은 O(n)이라 효율성이 나쁘다고해서 set or 딕셔너리를 찾아봄 2) set만 을 활용 -> 동명이인 처리할 방법이 생각 안남. 3) dic만 을 활용 -> 동명이인 처리할 방법이 생각 안남. -> 정 안되겠어서, 다른 사람들의 tip을 참고함. sort()를 썼더라고?.. 2022. 3. 19.

티스토리툴바