오묘한

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221604689852) [파이썬으로 시작하는 삼성 SW역량테스트] - 7. DFS와 BFS의 활용 ※실제 시험 시itertools 모듈이 사용 불가능하다는 말이 있습니다. 게시글은 나중에 수정하겠습니다. 저번... blog.naver.com 1. DFS가 사용되는 방식 1. 연결된 그래프를 모두 탐색하는 데 사용 2. 특정 조합을 뽑는 경우에 사용. 3. 순열과 조합 구현 시 많이 사용. 2. BFS가 사용되는 방식 1. 연결된 그래프를 모두 탐색하는 데 사용 2. 특정 그래프에서 가중치가 모두 같을 경우 최단거리를 찾을 수 있다. 연습문제: 백준 2178 미로(https://www.acmicpc.net/prob..

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221598474816, https://m.blog.naver.com/wpghks7/221602789884) [파이썬으로 시작하는 삼성 SW역량테스트] - 5. DFS와 BFS 기초 1 일이 있어서 2주간 글을 못 올렸는데, 시간을 내서 글을 올려봅니다. 각설하고 바로 본론으로 들어가 볼게... blog.naver.com [파이썬으로 시작하는 삼성 SW역량테스트] - 6. DSF와 BFS 기초 2 ※실제 시험 시itertools 모듈이 사용 불가능하다는 말이 있습니다. 게시글은 나중에 수정하겠습니다. 1. ... blog.naver.com DFS, BFS는 그래프를 모두 탐색하는 데에 사용하는 알고리즘이다! 1. ..

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221585604878) [파이썬으로 시작하는 삼성 SW역량테스트] - 4. 순열과 조합 ※실제 시험 시itertools 모듈이 사용 불가능하다는 말이 있습니다. 게시글은 나중에 수정하겠습니다. 이번... blog.naver.com 파이썬에서는 itertools를 이용해 순열과 조합을 쉽게 찾아낼 수 있지만, 이 모듈은 실제 시험장에서 못 쓰게 할 확률이 높으므로 dfs를 이용해 순열과 조합을 찾을 수 있어야 한다. 아래의 블로그 글들을 참고하여 파이썬 상에서 dfs를 이용해 순열과 조합을 만드는 연습을 하자! 순열, 조합 with dfs def permutation(depth, r, arr, visited, re..

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221584442182) [파이썬으로 시작하는 삼성 SW역량테스트] - 3. 큐, 스택, 덱 이번에는 큐(Queue)와 스택(Stack) 그리고 덱(Deque)에 대해서 간단한 개념과, 큐와 스택, 덱 사용법에 ... blog.naver.com 1. 큐(queue) 먼저 들어온 데이터가 먼저 나가는 자료 구조(FIFO) 큐에서 주로 사용하는 연산 4가지 1. push : 큐의 가장 마지막에 데이터를 넣음 2. pop: 큐의 가장 앞의 데이터를 제거함. 3. front : 큐의 가장 앞의 값을 확인하는 연산 4. empty: 큐가 비어있는지 확인하는 연산 큐를 구현하기 위해 파이썬 상의 queue 모듈을 사용하면 된..

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221584382367) [파이썬으로 시작하는 삼성 SW역량테스트] - 2. 정렬 입력을 받았다면 앞으로는 필수적인 모듈과 내장함수를 공부하겠다. 아직 본론에 들어가기보다는 역량 테스... blog.naver.com 1) 오름차순 정렬하기 오름차순 정렬에는 두 가지 방법이 있다. 하나는 sort()를 이용해 배열 자체를 변환시키는 방법이다. # 오름차순 정렬하기 # a 자체를 변환시키는 방법 a = [1, 5, 7, 4, 6] a.sort() print(a) # 출력: [1, 4, 5, 6, 7] 다른 하나는 sorted(배열) 형태로 배열을 변경하는 대신, 반환값으로 정렬해 넘겨주는 방식이다. # 오름차순 정렬하..

한 달 정도 남은 삼성 하반기 코테때문에 고민이 많았다. 계속 백준 단계별을 풀며 기초를 차근차근 쌓는 것이 맞을지, 아니면 삼성 SW 테스트에서 빈출로 나오는 DFS, BFS, 시뮬레이션으로 바로 넘어가는 것이 나을지 말이다. 고민하다가, 속성으로 삼성 코테 유형을 연습할 수 있는 좋은 블로그 글을 발견해서 우선 여기 나온 문제들을 먼저 풀어보기로 했다. 삼성 기출을 속성으로 설명해주시고, 기출문제 중 아주 쉬운 것들을 먼저 추천해주셔서 빠르게 DFS, BFS유형을 복습하고 삼성 기출에 익숙해질 수 있을 것 같았다. (알파카고수 님의 블로그 글 참고:https://m.blog.naver.com/wpghks7/221584113312) [파이썬으로 시작하는 삼성 SW역량테스트] - 1. 입력받기 알고리즘에..

참고 : 완전 탐색(Brute-force Search) 모든 문제를 푸는 데 있어서 가장 쉽고 간단한 방법부터 짚고 넘어가 봅시다. 완전탐색, 브루트포스(Brute... blog.naver.com 완전 탐색(Brute force)는 가능한 경우를 모두 탐색하는 것이다. 틀릴 가능성은 적지만, 시간이 최대로 든다. 완전 탐색 시간을 줄이기 위해 정렬과 함께 사용하는 경우가 있다. SW 검정 시험 시, 우선 완전 탐색으로 접근한 후 성능 개선을 위해 다른 알고리즘을 사용하는 방식이 바람직하다. 연관 문제: SWEA- 5203. 베이비진 게임 백준 - 단계별 풀기 (https://www.acmicpc.net/step/22) 브루트 포스 단계 체스판을 만드는 모든 경우를 시도하여 최적의 방법을 찾는 문제 www..

배열의 삽입, 삭제, 탐색에 드는 시간 복잡도 삽입 : 최악의 경우, 가장 앞에 삽입 시 O(N) (새로운 값 들어오면 다른 값들이 하나씩 자리 옮겨야 함. 단 맨 끝에 새로운 값 삽입하는 경우는 O(1)) 삭제: 최악의 경우, 가장 앞에 걸 삭제 시 O(N) (다른 값들이 하나씩 자리 옮겨야 함. 단 맨 끝에 삭제하는 경우는 O(1)) 탐색: 최악의 경우, 찾는 값이 맨 끝에 있을 시 O(N) (처음부터 끝까지 탐색, 그러나 인덱스로 찾을 시 k번째 원소를 찾으려면 (k-1)인덱스를 참조하면 돼서 O(1) 걸림.) 파이썬 배열 메서드의 시간 복잡도 arr.find(x) = 처음부터 끝까지 탐색함.최악의 경우 O(n) arr.remove(x) = 삭제 후 이동. 최악의 경우 O(n) 동적 배열 정적 배열..

1) 시간, 공간 복잡도 공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는가. 시간적 효율성: 연산량 대비 얼마나 적은 시간을 요하는가. 효율성을 뒤집어 표현하면 복잡도가 되며, 이 복잡도가 높을수록 효율성은 낮아진다. 복잡도의 점근적 표기 이전에 재귀식에선 T(n)으로 표시했으나, 주로 Big-Oh 표기법 사용(예: O(n)) 1) 빅 오 표기 빅 오 표기는 복잡도의 점근적 상환이다. 가령 2a² + 2a + 2 라고 수식이 나올 경우, 상수를 빼고 O(n²)로 표기. f(n) = n²+n이고 g(n) = n³일때 f(n) = O(g(n))으로 나타낼 수 있음. f(n)의 차수가 g(n)의 차수보다 같거나 작다는 뜻. 예시) n^100 = O(2^n)은 참임. n이 충분히 크다고 가정했을..