기타/SW 사관학교 정글
-
[SW 정글 12일차] 스택과 큐 알아보기기타/SW 사관학교 정글 2021. 8. 13. 22:30
오늘은 스택과 큐에 대해 정리해보려고 한다. 스택과 큐가 대충 어떠한 성격의 자료구조인지는 알고 있었지만 세세하게 알아본 적은 없었다. 기본적인 자료구조인 만큼 내가 공부한 내용을 정리하며 개념을 제대로 잡고자 한다. 1. 스택 (stack) 스택은 데이터를 임시로 저장하는 자료구조로 후입선출(LIFO)방식이다. 후입선출(LIFO)은 먼저 들어온 데이터가 나중에 나간다는 의미이다. 이렇게 말로만 설명하면 감이 잘 안올텐데 프링글스를 생각해보자. 단, 깨진 짜잘짜잘한 조각들은 생각하지 않고 프링글스를 만들 때는 과자칩을 하나하나 통에 넣을 것이다. 이렇게 하나, 둘 쌓인 과자칩은 우리가 가게에서 사게 될 것이고 우리는 프링글스를 위에서부터 하나씩 꺼내서 먹을 것이다. 위에서부터 꺼내 먹게 되면 들어온 순서..
-
[SW 정글 11일차] 검색 알고리즘기타/SW 사관학교 정글 2021. 8. 12. 23:22
오늘은 2주차 시작으로 검색 알고리즘에 대해 공부를 시작했다. 검색 알고리즘에 대해 거의 모르다시피 살고 코딩테스트에서는 in 을 써서 값이 배열 안에 있는지 없는지 확인만 하는 수준이였다. 오늘부로 검색 알고리즘 개념을 잡고자 한다. 1. 선형 검색 (linear search) 선형 검색은 배열에서 원소를 검색하는 방법 중 가장 기본적인 알고리즘이다. 원하는 값을 찾기 위해 배열의 맨 앞부터 순서대로 확인하며 검색하는 것이다. 어떠한 방식으로 검색이 이루어지는지 아래의 그림을 보며 이해해보자. 배열의 맨 앞부터 순서대로 3인지를 확인하고 아니면 다음 원소로 넘어가면서 3인 원소를 찾았을 때 검색을 멈추게 된다. 선형 검색의 종료 조건은 2가지가 존재한다. - 찾고자하는 값을 찾지 못하고 배열의 맨 끝을..
-
[SW 정글 10일차] 전역 변수와 지역 변수 참조기타/SW 사관학교 정글 2021. 8. 11. 22:50
오늘은 백준에서 문제를 풀면서 처음 경험하는 현상을 발견하여 그 현상과 원인을 정리해보려고 한다. 현상에 대한 원인을 알려주신 분은 코발트에서 개발자로 일하고 계신 이선협님이다. 내가 겪은 현상은? 먼저, 내가 푼 문제는 백준 알로리즘 저지에 있는 외판원 순환 2라는 문제이다. https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 완전탐색으로 모든 경우의 수를 구해 접근하려 했고 처음에는 시간초과가 났다...
-
[SW 정글 9일차] 순열과 조합 사용하기기타/SW 사관학교 정글 2021. 8. 10. 22:56
오늘은 알고리즘 문제를 풀면서 사용한 순열과 조합에 대해서 정리해보려고 한다. 문제를 보고 '아, 배열 안에 있는 수를 순서를 바꾼 모든 경우를 얻고 싶은데 어떻게 하지..'라는 생각을 가진 적이 많고 그 때마다 항상 인터넷 검색을 하고 순열을 쓰면 되는구나 혹은 조합을 쓰면 되는구나 했다. 오늘은 이렇게 글로 정리하면서 다음부터는 바로바로 떠올릴 수 있도록 해보고자 한다. 1. 순열 (permutation) 순열을 사용하는 경우는 어떠한 경우일까? 먼저 순열은 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 말한다. 여기서 더 깊게 얘기하면 수학적인 개념을 얘기해야하므로 간단히 순열이 무엇인지만 얘기하고 넘어가겠다. 이러한 순열은 우리가 어떠한 배열을 가지고 있는데 그 배..
-
[SW 정글 8일차] 정렬 알고리즘 2기타/SW 사관학교 정글 2021. 8. 9. 22:33
오늘은 어제에 이어 정렬 알고리즘에 대해 더 공부해보려고 한다. 정렬 알고리즘만 이틀연속 공부한 것이 아니라 토요일부터 재귀함수의 늪에 빠져 헤어나오느라 시간을 꽤 많이 소비했다. 어제는 기본 정렬 알고리즘을 공부했다면 오늘은 시간복잡도 면에서 더 개선된 알고리즘을 공부하여 정리해보려고 한다. 1. 셸 정렬 (shell sort) 셸 정렬은 단순 삽입 정렬의 문제점을 보완하여 더 좋은 시간복잡도를 가지는 알고리즘이다. 단순 삽입 정렬의 문제점은 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아지는 것이다. 아래의 배열을 보면 다섯 번째 위치에 있는 0은 앞의 것이 정렬되어있음에도 불구하고 삽입 정렬을 위해 5번에 걸쳐 이동해야한다. 이를 보완하기 위해 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠..
-
[SW 정글 7일차] 정렬 알고리즘 1기타/SW 사관학교 정글 2021. 8. 8. 23:08
오늘은 정렬 알고리즘에 대해 정리해보려고 한다. 정글에 들어오기 전, 정렬 알고리즘을 나동빈님 책과 유튜브 강의로 본 적은 있지만 파이썬에서는 sort() 내장함수가 시간복잡도 면에서 좋기 때문에 정렬 알고리즘을 파헤치기 보다는 그냥 정렬 문제면 sort()써야지라는 생각 뿐이였다. 오늘 이렇게 나에게 시간이 주어진만큼 정렬 알고리즘을 제대로 공부를 할 수 있었다. 1. 버블 정렬 (bubble sort) 버블 정렬은 정렬 알고리즘 중 기본적인 알고리즘으로 이웃하고 있는 두 원소의 대소 관계를 비교하여 자리 교환이 필요할 시에 교환을 반복하는 알고리즘이다. 아래의 배열을 버블 정렬을 이용하여 오름차순으로 정리한다고 해보자. 뒤에서부터 이웃한 원소 2개씩 대소 비교를 하며 왼쪽의 값이 오른쪽의 값보다 작거..
-
[SW 정글 6일차] 몰랐었던 배열 비교기타/SW 사관학교 정글 2021. 8. 7. 22:49
오늘은 정글 6일차, 어제에 이어 알고리즘 기초공부를 이어나갔고 제공된 기초문제 중 뒷부분은 다소 시간이 걸리는 문제이기에 팀원과의 리뷰는 오늘까지 이루어졌다. 오늘 정리할 내용은 알고리즘과 자료구조에 대한 공부는 했었지만 내가 모르거나 혹은 대충 알고 넘어갔던 부분을 정리해보려고 한다. 1. 비교 연산자로 배열의 대소 또는 등가 관계 판단하기 먼저, 기존에는 모르고 있었던 배열과 배열사이에 비교 연산자를 사용하는 것이다. 간단하게 배열에 대해 설명하면 배열은 기본 자료구조 중 하나로 어떠한 값들을 묶음 단위로 저장하여 데이터가 모여있는 자료구조이다. 배열에는 객체가 저장되고 배열에 저장된 객체 하나하나를 원소(element)라고 한다. 그리고 이 원소(element)는 각각 인덱스(index)번호를 부..
-
[SW 정글 5일차] 유용한 파이썬 문법기타/SW 사관학교 정글 2021. 8. 6. 22:57
오늘부로 정글에 들어온 지 5일차가 되었고 앞으로 4주동안 알고리즘과 자료구조 지식을 쌓게 될 예정이다. 오늘은 알고리즘 기초부터 시작해 간단한 구현문제를 풀면서 알게된 유용한 파이썬 문법을 정리하려고 한다. 참고하고 있는 서적은 자료구조와 함께 배우는 알고리즘 입문 파이썬 편이고 백준 온라인 저지문제를 풀고 있다. Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - YES24 기업 코딩 테스트와 모든 시험의 기초가 되는 ‘자료구조와 알고리즘’!213개의 그림과 136개의 파이썬 실전 예제로 빠르고! 쉽게! 배운다.자료구조와 알고리즘은 국내외 IT 기업의 면접과 코딩 www.yes24.com 1. 포맷 문자열 리터럴 먼저, 포맷 문자열 리터럴이다. 포맷 문자열 리터럴은 f-문자열이라고도 ..