비선형구조 1. 트리 (Tree) 사이클(순환)이 없는 연결된 그래프입니다. 트리를 구성하는 노드 간에는 단순 경로가 존재하는 특징이 있습니다. 여기서 단순 경로란 지나왔던 접점을 다시 지나지 않는 경로 입니다. 우리가 주로 쓰는 간단한 예시로는 폴더 구조가 있습니다. 트리는 일반트리와 이진트리가 있습니다. 차이로는 이진트리는 2개 이상의 노드가 존재하지 않는 구조라 생각하면 쉽습니다. ( 이진트리 - 각 노드가 최대 두개의 자식을 갖는 트리 ) 트리의 큰 특징으로는 1. 방향성 있음. 2. 각 노드는 어떤 자료형으로도 표현이 가능 3. 사이클이 존재 할 수 없다.(하나의 연결 그래프) 4. 트리는 이진 트리, 이진 탐색 트리, 균형트리 등이 있습니다. 2. 그래프 (Graph) 그래프란? 노드와 노드를..

- 자료구조의 분류 선형구조 1. 배열 (Array) (선형 리스트) 배열의 특징은 논리적 순서와 물리적 순서가 일치한다. 즉, index값을 통해 원소 접근이 용이하며, 구현이 쉽다. 하지만 단점으로 삽입, 삭제 등에 대한 연산에 필요한 Cost가 높다. 삭제를 하는 경우 순서를 맞추기 위해 뒤의 원소들을 앞으로 Shift 연산을 해줘야 한다. 삭제 1 2 3 4 5 1 2 삭제 4 5 1 2 4 5 1 2 4 5 2. 연결 리스트(LinkedList) 배열의 삽입/삭제의 단점을 극복하고자 만든 개념이 리스트이다. 배열은 논리적, 물리적 저장이 순서대로 되어 있다. 하지만 리스트는 논리적으로는 순서대로 되어 있으나 물리적으로는 순서대로 되어있지 않다. 대신 각 원소가 index위치에 ..

퀵 정렬 - 숫자를 오름차순으로 정렬하는 프로그램 - 기존 선택, 버블, 삽입은 N^2이라는 시간 복잡도를 가지고 있다. - 데이터가 무수히 많아 짐에 따라 좀 더 빠른 정렬을 생각 해볼 필요가 있다. - 이때 생각해낸 것이 퀵정렬이다. - 특정한 배열이 있을 때 "분할 정복" 알고리즘을 쓴다 & 재귀 알고리즘을 이용한 정렬이다. 기본원리 가운데 pivot값을 정한 후 작은값 + pivot값 + 큰값 같은 형식으로 정리하는 원리 이다. 코드는 직관성 있고 이해하기 쉽지만 효율적이지 않다. -메모리 사용 측면에서 좋지 못한 코드이다. 리스트의 정 가운데 있는 값을 pivot 값을 선택합니다. 시작 인덱스(low)는 계속 증가 시키고, 끝 인덱스(high)는 계속 감소 시키기위한 while 루프를 두 인덱스..

소프트웨어 개발 플랫폼 & 소스코드 호스팅 서비스 깃허브를 알기 위해서는 우선적으로 깃을 알아야 한다. 깃(Git)이란? - svn은 저장소 서버가 있으며, git은 저장소가 자신의 컴퓨터에 있는 것을 말한다. - 프로젝트를 관리하는 '분산 프로젝트 버전관리 소프트웨어'이다. 버전 관리 소프트웨어란? -개발 중 변경 내역을 추적할 수 있도록 개발된 소프트웨어 왜 깃을 사용하는가? 나와 동료가 동시에 같은 코드를 보고 업데이트를 하고 있다고 가정하자. 내가 소스를 저장하고 업로드를 한 상태에서, 그 파일을 동료가 쓴다면 상관이 없다. 하지만 동시에 쓸 때는 상황이 달라진다. 이러한 상황을 해결하고자 깃을 만든 것이다. 깃과 같은 버전 관리 앱은 동료는 같은 페이지에서 각자의 수정사항을 각각 업로드할 수 있..

삽입 정렬 - 숫자를 오름차순으로 정렬하는 프로그램 arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 삽입정렬은 앞의 있는 원소들이 이미 정렬되어있다고 가정을 한다 라는 특성이 있다. 즉, 하나의 원소를 선택 후 삽일 할 위치에 보내는 방법을 삽입 정렬이라고 한다. #1 [1, 3, 4, 5, 2] #1 선택해 맨 처음 자리로 이동 [(1) _, 3, 4, 5, (1), 2] 빈 공간이 있다고 생각하고 이동 #2 [1, 2, 3, 4, 5] #2 선택해 공간의 위치에 이동 1과 3 사이 [_, 1, (2)_, 3, _, 4, 5, (2)] #3 [1, 2, 3, 4, 5] #3 선택해 자리 이동 //변화 없음... #4 [1, 2, 3, 4, 5] #4 ..

버블 정렬 숫자를 오름차순으로 정렬하는 프로그램 하지만 쉽게 해석하려면 가장 큰 숫자를 맨 뒤로 보내는 것과 같다고 생각하면 된다. arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 두 수를 선택해서 큰값을 뒤로 보내는 방법을 버블 정렬이라고 한다. #1 [3, 4, 5, 1, 2] #3과 4을 자리 바꾸기 // 변하지 않음 #2 [3, 4, 5, 1, 2] #4와 5 자리 바꾸기 // 변하지 않음 #3 [3, 4, 1, 5, 2] #1과 5 자리 바꾸기 #4 [3, 4, 1, 2, 5] #2와 5 자리 바꾸기 순서로 진행된다. 결국 5가 가장 마지막이고 1은 가장 처음으로 온다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ''' 반..

선택 정렬 숫자를 오름차순으로 정렬하는 프로그램 arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 가장 작은 숫자를 선택해서 앞으로 보내는 방법을 가장 먼저 떠올릴 수 있다. #1 [1, 4, 5, 3, 2] #1과 3을 자리 바꾸기 #2 [1, 2, 5, 3, 4] #2와 4 자리 바꾸기 #3 [1, 2, 3, 5, 4] #3과 5 자리 바꾸기 #4 [1, 2, 3, 4, 5] #4와 5 자리 바꾸기 순서로 진행된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ''' #반복문 사용 i, j >>> 배열에 있는 원소 반복적으로 탐색 min_index >>> 최솟값 원소 "위치" ''' def selection_sort..

www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌�� www.acmicpc.net 문재해석 처음 보는순간 수열이라는 것을 쉽게 발견 할 수 있다. 솔직히 백준 수학 알고리즘 수학 1 파트를 풀고 있지만 규칙은 어렵지않게 발견했지만 구현이 쉽지가 않다. 이번에도 조금 힘들었다. 조건1) room은 초기방 숫자가+6씩 수열로 증가 할때마다 room +1 씩 해주면 된다. 코드를 풀어보자면 처음 숫자가 1번 일때는 그대로 출력 // #1번째 방 초기값을 7로 잡아서 구하고자하는 값이, 예를들어 6일때 ..

www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 문재해석 정말 애먹었다. 처음 해석은 쉬운데 이걸 구현하기가 생각보다 까다롭다. 다들 3의 배수 5의 배수로 생각을 하다가 생각해보면 의외로 그렇지 않는 경우도 있다. (예를들어 11의배수도 있고...) 아무튼 고민끝에 푸는 방법은 간단했다. 조건1) 5의 배수일때 무조건 5를 빼준다. 그리고 카운터 + 1 조건2) 5의 배수가 아닌거는 무조건 3을 빼준다. 그리고 카운터 + 1 이렇게 돌리면 11, 16과 같은 경우..

www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 문재해석 처음에는 for 문으로 곱하기를 해서 결과를 구하려고 했다. 하지만 몇번을 돌릴지 조건이 나와있지않았고, 더 까다롭다는걸 알았다. 그래서 고민끝에 알아낸 방법이 나누는 것이었다. (하지만 이미 많은 분들은 이렇게 푸셧다..) 뭔가 대단한걸 발견한줄 알앗는데 코드까지 똑같앗다. 조건1) b가 c보다 크거나 같으면 손익분기점이 절대 없다. 왜냐하면 a 를 더하기 때문이다... 무조건 차익에서 이득이 나야 수익이..

www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때� www.acmicpc.net 문제해석 문제 해석은 어렵지 않았다. 그룹 단어를 카운트 해야 되는데, 조건 1) 서로 다른 단어 일 경우 카운트 +1 조건 2) 같은단어가 연속으로 나오지만, 뒤에 연속으로 나왓던 단어가 나오지 않을 경우 카운트 +1 문제 해석은 쉬운데 구현이 어려웠다. 두문자를 비교하는 조건을 체크하는건 쉬웠는데, 그 후 카운터를 어떻게 올려야 할지 몰랏다. 여러 오픈소스를 보고 횟수만큼 ..

www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 문재 해석) 처음에는 이게 뭔말인가 싶었다. 하지만 출력 글을 읽어보니 크로아티아 문자열로 변환 후 그 문자열의 인덱스를 구하면 되는 것이었다. 이렇게 해석하면 간단하게 풀 수 있다. 1 2 3 4 5 6 7 str_list = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] s = input() for i in str_list: s..