오늘 목표 TIL 작성 필수 과제 풀기 학습한 것 오늘은 그래프의 기초적인 부분을 학습하면서 공부했는데 아직 이해가 잘 되지 않은 부분이 많아, 월요일에 그래프 탐색을 하면서 그래프의 내용을 좀 더 정리하면서 작성해야겠다. 좋았던 점 heapq를 사용하면서 그냥 쓰기만했었지, 자료구조의 시간복잡도나 공간복잡도에 대해서 제대로 생각해보지 않은 것 같다. 근데 오늘 멘토링을 하면서 멘토분과 팀원들과 함께 heapq 내의 heapify나 heappush 같은 함수들이 왜 O(N), O(logN)인지, 정렬 알고리즘들은 왜 그런 시간 복잡도를 가지고 있는지 내부적인 로직에 대해서도 고려해볼 수 있었다. 아쉬웠던 점 오늘 문제는 그래프와 관련된 것이 아니라 지금까지 풀었던 문제들을 종합적으로 풀어보는 문제였다. ..
취리코
오늘 목표 TIL 작성 필수 과제 모두 풀기 학습한 것 이진 탐색이란? 정렬이 이미 되어 있는 리스트에서 탐색의 범위를 절반씩 줄여나가며 데이터를 탐색하는 방법을 의미한다. 다음과 같은 특징을 가진다. 변수 3개를 사용해 탐색한다.(start, mid, end or left, mid, right) start: 시작 범위 mid : 중간 위치에 있는 데이터 end : 끝 범위 탐색의 범위를 절반 단위로 줄이기 때문에 시간 복잡도는 O(log₂N) 이다. 다음과 같은 예시를 통해서 이해해보자. 코드 및 실행 예시 # 시작 데이터 arr = [1,2,3,4,5,6,7,9,10] # 찾으려는 값 target = 8 # 1회 탐색(start = 1, mid = 5, end = 10) # mid의 값보다 찾으려는 ..
[학습 내용] 오늘은 힙에 대해서 학습했다. 1. 힙 힙은 완전 이진 트리의 일종으로 부모 자식 노드 사이에 특정 조건을 만족하는 자료구조를 말한다. 완전 이진 트리란 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 리프 노드를 제외한 모든 노드가 완전히 채워져 있는 구조를 말한다. 힙은 기준점에 따라서 최소 힙과 최대 힙으로 나눌 수 있는데, 다음과 같은 특징이 있다. 최대 힙은 모든 부모 노드가 그 자식 노드보다 크거나 같은 값을 가지는 특성을 가지고 있어 루트 노드는 전체 힙에서 가장 큰 값을 가지고 있다. 반대로 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 특성을 가지기 때문에 루트 노드가 전체 힙에서 가장 작은 값을 가진다. 파이썬에서는 heapq 라이브러리를 활용해서 생..
[학습 내용]오늘은 알고리즘 및 자료구조의 입문 단계라고 할 수 있는 스택과 큐에 대해서 학습했다. 그중에서도 스택을 알아보자.1. 스택(Stack)스택은 '쌓는다' 라는 이름의 어원처럼, 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 LIFO(Last In First Out)의 구조를 가진 자료구조이다. 일상 생활에서도 많이 볼 수 있는 형태인데, 곽티슈나 좁고 긴 바구니에 물건을 넣는다면 이런 구조를 지닐 것이다. 실제 프로그램 내부에서도 이런 구조를 지닌 대표적인 예는 우리가 함수를 형성하고 저장할 때, 함수가 메모리의 스택 영역에 실행 순서에 따라 차근차근 저장되고, 가장 나중에 호출된 함수부터 차례차례 해제된다. 이런 스택을 프로그램에서 차용하는 가장 큰 이유는 처음 실행했던 함수로 돌아가기 ..
[팀스터디에서 얻은 인사이트] 모든 문제를 푸는게 좋은게 아니라 정답률, 문제를 푼 사람 수 등 대중적으로 사람들이 많이 푼 알고리즘 문제에 대해서 먼저 고민하고 나서 심화 문제를 고려하는 것이 중요하다고 하셨다. 확실히 같은 알고리즘, 자료구조의 문제를 많이 풀 때도 위와 같은 우선순위를 두고 유형과 어느 정도의 정형화된 코드를 이해하고 나서 문제에 접근한다면 실전에 더 잘 풀 수 있다 싶다. 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠입니다. IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지 항해99는 실무에 집중합니다. 최단기간에 개발자로 취업하고, 현직자 코스로 폭발 성장을 이어가세요. 실전 프로젝트, 포트폴리오 멘토링, 모의 면접까지. hanghae99.spartacodi..
[팀스터디에서 얻은 인사이트] 2차원 배열 자체의 개념을 아는 수준으로는 알고리즘 문제는 손도 못 댔던 것 같다. 그나마 쉬운 난이도 문제들에서도 꽤나 긴 시간을 잡아 먹었고, 알고리즘을 접근하는 방식에 대해서도 꽤나 고민이 많았다. 문제를 풀 때 효율을 먼저 고려하는 게 아니라 해결하는 게 먼저인 것을 잊지말자. 최적화는 구현하고 나서 하는거지 구현하지도 않고 고려하는 건 아닌 것 같다. 추후에 가능하면 문제를 다시 한 번 더 풀어보는 게 좋겠다. 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2..
[학습 내용] 문자열에 대해서 어느 정도 알고 있다고 생각했었는데, 풀다 보니 기초적인 부분에서도 실수가 많이 나와 반성하게 됐다. 오늘 풀었던 문제들도 도움이 됐지만 자주 나올 패턴은 회문 관련되서 나올 것 같다. 그 문제 위주로 확인해보자.
[팀스터디에서 얻은 인사이트] 중요한건 각 알고리즘이나 문제 장르에서 공식적으로 들어가는 풀이 방법이 있다. 그 방법을 확실히 인지하기만 해도 대부분의 알고리즘 문제는 큰 틀에서 벗어나지 않는다. 정확히는 코딩테스트에서 출제하는 문제들은 그 틀에서 벗어나는 문제는 잘 출제되지 않는다. 그 공식을 얻으려고 하자 [학습 내용] 백준 문제 N과 M 문제를 처음에는 멘토님이 가르쳐주시지 않았더라면 파이썬에 있는 itertools를 이용해서 그저 단순하게 순열과 조합으로 풀어버렸을지도 모른다. 하지만 분명하게 백트래킹 문제라고 인지를 시켜주시고 해답을 알려주셨는데 제대로 공부한 적이 없어 코드의 실행 과정을 이해하는데 애를 먹었다. 백준 15649 N과 M(1) 15649번: N과 M (1) 한 줄에 하나씩 문제..
