본문 바로가기

전체 글

[코딩 테스트 합격자 되기 - 11주차] 시뮬레이션(Simulation) 뭔가 시뮬레이션은 어떻다기 보다는 많은 문제를 접하면서 내 생각대로 문제를 풀 수 있을까가 많이 중요해보임. 그렇기 때문에 기초가 더 중요한 챕터라고 생각함. 문제 65 - 이진 변환 반복하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 def solution(s): # [1] 0을 제거한 횟수, 2로 변환한 횟수 cnt_rm = cnt_2 = 0 # [2] s가 '1'이 아닌 동안 계속 반복 while s != "1" : # [3] 이진 변환 횟수 1 증가 cnt_2 += 1 # [4] s에서 '0'의 개수를 세어 cnt_rm 에 누적 cnt_.. 더보기
[코딩 테스트 합격자 되기 - 10주차] 정렬(Sort) - 2 문제 56 - 문자열 내 마음대로 정렬하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석하고 풀기 파이썬의 정렬 함수인 sorted() 함수를 사용해서 풀이 더보기 def solution(strings, n) : return sorted(strings, key=lambda x:(x[n], x)) 첫 번째 매개변수 strings는 정렬 대상, 두 번째 매개변수 key는 정렬 방법을 람다 함수로 전달한 것이다. lambda x:(x[n], x)는 x[n]을 기준으로 오름차순 정렬하겠다는 의미 N은 strings의 길이이다. sorted() 함수의 .. 더보기
[코딩 테스트 합격자 되기 - 10주차] 정렬(Sort) - 1 정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것을 말함. 정렬이 필요한 이유 데이터를 정렬하면 원하는 데이터를 쉽게 찾을 수 있다. 그 예시로 이진 탐색 트리가 있다. 만약 오름 차순으로 정렬이 되어있는 데이터가 있다면, 큰 수를 찾을 때는 오른쪽부터 찾는 것이 훨씬 쉽고 빠르게 찾을 것이다. 정렬은 알고리즘의 효율을 크게 높여줍니다. 이번에 알아볼 정렬은 다음과 같다. 정렬 방법 최악의 경우 최선의 경우 특이점 삽입 정렬 O(N ^ 2) O(N) 데이터가 거의 정렬되어 있을 때는 최고의 성능을 발휘함. 병합 정렬 O(N log N) O(N log N) 안정적인 성능으로 정렬할 수 있다. 병합 과정에서 추가적인 메모리가 요구된다. 힙 정렬 O(N log N) O(N log N) 안정적인 성능으로 정.. 더보기
[코딩 테스트 합격자 되기 - 9주차] 백트래킹(BackTracking) 완전 탐색 : 깊이 우선 탐색, 너비 우선 탐색과 같이 데이터를 전부 확인하는 탐색 방법을 의미한다. 우리는 이 글에서 공부해 볼 탐색 방법은 백트래킹으로 지난 깊이 우선 탐색, 너비 우선 탐색을 공부하던 중 탐색 진행이 더이상 불가능해 졌을 때 되돌아 오는 것을 착안해서 가능성이 없는 곳에서는 되돌아 가고, 가능성이 있는 곳을 탐색하는 알고리즘이다. 유망 함수 백트래킹 알고리즘의 핵심은 해가 될 가능성을 판단하는 것. 그리고 그 가능성은 유망 함수라는 것을 정의하여 판단한다. 유효한 해의 집합을 정의 위 단계에서 정의한 집합을 그래프로 표현 유망 함수 정의 백트래킹 알고리즘을 활용해서 해를 찾음 유망 함수가 백트래킹 알고리즘에서 어떻게 동작하는지 예제를 통해 알아보자 합이 6이 넘는 조합 알아보기 {1.. 더보기
[코딩 테스트 합격자 되기 - 후기] 이 글은 코딩 테스트 합격자 되기 - 파이썬 1독 스터디를 진행하고 느낀 점과 배운점, 그리고 보완해야할 점을 적는 글이다. 그래서 알고리즘을 검색하시다가 들어오신 분들은 뒤로 가기 하시길 바란다. 얼마 전 코딩 테스트 합격자 되기 - 파이썬 1독 스터디를 완주하였다. 블로그 글을 다시 봤을 땐 상당히 아쉬운 점이 많았다. 무엇보다 처음 글을 작성했을때는 어떤 것들을 작성해야할 줄 몰라 그냥 대충 적은 느낌이 강했다. 그리고 중반 이후 글은 그냥 복사 붙여넣기 한 것 같은 느낌이 들어 뭔가 내가 공부했다는 느낌을 받지 못하였다. 내가 이 책에 있는 정보 등을 포함하여 완전히 습득하지 못하였기 때문이라고 생각한다. 해야한다는 생각만 들어서 그냥 용량만 채운? 그런 느낌이 상당히 강했다. 이러한 기분이 많이.. 더보기
[코딩 테스트 합격자 되기 - 8주차] 그래프(Graph) - 2 그래프 최단 경로 구하기 최단 경로는 그래프 종류에 따라 그 진의가 다르게 해석될 수 있는 주제. 최단 경로를 구하는 대표적인 알고리즘인 다익스트라 알고리즘과 벨만-포드 알고리즘을 알아보자. 다익스트라 알고리즘 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘이면서 탐욕법(Greedy Algorithm)으로 분류되는 알고리즘이기도 하다. 시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련. 최소 비용을 저장할 공간은 매우 큰 값으로 초기화. (float('inf')) 직전 노드를 저장할 공간도 INF로 초기화함. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 한다. 해당 노드를 통해 방문할 수 있는 노드 중 현재까지 구한 최소 비용이 가장.. 더보기
[코딩 테스트 합격자 되기 - 8주차] 그래프(Graph) - 1 그래프는 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조 . 보통 그래프는 데이터 간의 관계를 표현하는 데 사용됨. 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현함. 간선은 방향이 있을 수도, 없을 수도 있음. 만약 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현하기도 함. 그래프 용어 정리 예를 들어 도시 간의 인구 이동을 그래프로 표현하면 다음과 같다. 그림에서 사각형으로 표현한 것은 노드(또는 정점), 화살표로 표현한 것은 간선, 간선 위에 숫자로 표현한 것은 가중치다. 노드에는 어떤 데이터가 들어있다. 인구 이동의 경우 어디서 얼마나 이동했는지 표시할 필요가 있으므로 간선에 가중치를 표현함. 흐름을 표현하는 방향성 간선은 방향을 가질 수도 .. 더보기
[코딩 테스트 합격자 되기 - 7주차] 집합(Set) 집합과 상호배타적 집합의 개념 개념 : 집합은 순서와 중복이 없는 원소들을 갖는 자료구조. A라는 그룹의 원소 구성이 {1, 6, 6, 6, 4, 3} 이라면, 이는 집합으로 생각할 때 중복을 제외해 {1, 6, 4, 3}으로 생각해야 한다. 순서를 따지지 않는다. 집합의 종류 유한 집합 : 원소의 개수가 유한함. 무한 집합 : 원소의 개수가 무한함. 공집합 : 집합이 비어 있음. 상호배타적 집합 : 교집합이 없는 집합관계 상호배타적 집합이란 ? 교집합이 없는 집합 관계. A = {1, 2, 3} B = {4, 5, 6, 7} 이 두 집합의 원소 중 겹치는 원소가 없으면 교집합이 없다고 할 수 있고 이를 상호배타적 집합이라고 함. 상호배타적 집합의 특성을 활용하는 분야 코딩 테스트에서 항호배타적 집합을 .. 더보기

티스토리툴바