Language/Python 검색 결과

35 개의 검색 결과가 있습니다.

Language/Python

[ALGORITHMS]문제 16 미로 찾기 알고리즘

문제 16 미로 찾기 알고리즘 다음 그림과 같이 미로의 형태와 출발점과 도착점이 주어 졌을때 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 만들어보세요 1. 문제 분석과 모델링 주어진 미로는 연필을 들자마자 풀어 버릴 만큼 간단한 문제입니다. 하지만 이 문제를 컴퓨터에게 풀어 보라고 하려면 어떻게 해야 할까요? 사람에게는 정말 쉬운 문제지만 컴퓨터에게 이 문제를 이해하고 풀게 할 아이디어는 선뜻 떠오르지 않습니다. 이떄 필요 한것이 바로 모델링입니다. 모델링이랑 주어진 현실의 문제를 정혀화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽게 설명 할 수 있도록 다시 표현하는 것을 말합니다. 미로 안의 공간을 정형화 시켜보도록하겠습니다.4x4로 구성된 간단한 미로입니다. 먼저 이동 가능한 위치..

2017. 9. 5. 04:46

Language/Python

[ALGORITHMS]문제 15 친구의 친구 찾기(그래프)

문제 15 친구의 친구 찾기 친구 관계를 이용하여 어떤 한 사람이 직접 또는 간접으로 아는 모든 친구를 출력하는 알고리즘을 만들어 보세요 1. 용어 정리 - 친구 : 어떤 두 사람이 직접 아는 사이일 때, 즉 서로 친구 요청을 수락한 경우 친구라고합니다ex)A가 B의 친구이면 B도 A의 친구입니다 - 모든 친구 : 어떤 사람이 직접 아는 친구들과 그 친구들의 친구들, 즉 직간접으로 아는 모든 사람을 말합니다(자기자신도 포함)ex) A와 B가 친구이고 B와 C가 친구이고 C와 D가 친구이면 (A-B-C-D), A에게는 A,B,C,D, 전부가 '모든 친구'입니다 - 친밀도 : 어떤 사람 두명이 서로 직간접으로 아는 사이일때 두 명이 서로 몇단계를 거쳐 아는지 나타내는 숫자입니다(자기 자신의 친밀도는 0)ex..

2017. 9. 4. 21:46

Language/Python

[ALGORITHMS]문제 14 동명이인 찾기 2(딕셔너리)

문제 14 동명이인 찾기 2 (딕셔너리) n명의 사람 이름 중에 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 만들어보세요 문제 3에서 살펴본 동명이인 찾기 문제를 다시 풀어 보겠습니다. 동명이인 찾기 문제는 사람들의 이름이 나열된 리스트 안에 같은 이름이 있는지 확인해서 중복된 이름들을 집합으로 돌려주는 문제였습니다. 예를 들어 ["Tom", Jerry", "Mike" "Tom"] 이 입력으로 주어지면 "Tom"이 중복되므로 이를 집합에 넣은 {"Tom"}을 결과로 돌려주면 됩니다. 이번에는 파이썬의 딕셔너리(dictionary, 사전)라는 자료 구조를 이용해서 동명이인 문제를 풀어 보겠습니다. 1. 딕셔너리 파이썬의 딕셔너리는 정보를 찾는 기준이 되는 키(key)와 그 키에 연결된 값(valu..

2017. 9. 4. 16:44

Language/Python

[ALGORITHMS]문제 13 회문 찾기

문제 13 회문 찾기 문자열이 회문인지 아닌지 판단하여 회문이면 True, 아니면 False를 결과로 알려주는 알고리즘을 만들어보세요 이번에 풀어 볼 문제는 회문 찾기 문제입니다. 회문은 조금 생소한 단어인데 순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말이나 문장'을 뜻합니다. 낱말 사이에 있느 공백이나 문장 기호 등은 무시하므로 다음 낱말과 문장은 모두 회문입니다. 가장 기본 자료 구조인 큐와 스택을 알아본다음, 큐와 스택의 특징을 이용해서 회문을 판단하는 방법을 살펴보겠습니다 1. 큐와 스택 두 자료 구조는 자료를 넣는 동작과 자료를 뺴는 동작을 할 수 있으며, 들어간 자료가 일렬로 보관된다는 공통점이 있습니다. 하지만 자료를 넣고 뺼 때 동작하는 방식이 서로 다릅니다. * 큐 큐는 '줄 서기'..

2017. 9. 4. 04:58

Language/Python

[ALGORITHMS]문제 12 이분탐색

문제 12 이분탐색 자료가 크기 순서대로 정렬된 리스트에서 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘을 만들어 보세요. 리스트에 찾는 값이 없으면 -1을 돌려줍니다 이번 문제는 숫자가 여러개 들어 있는 리스트에서 특정한 값이 있는 위치를 돌려주고 리스트에 그 값이 없으면 -1를 결과값으로 돌려주는 문제 7과 똑같습니다. 다만 이번에는 리스틩 자료가 순서대로 정렬되어 있으므로 훨씬 더 빠르게 탐색할 수 있습니다. 1. 일상생활 속의 탐색 문제 사람들은 일상 생활 속에서 알게 모르게 굉장히 많은 탐색 문제를 풀면서 살아갑니다. 첫번째 예로 두꺼운 책을 한권 앞에 두고 특정한 쪽 수(618쪽) 를 찾는 과정을 떠올려 봅시다 1. 우선 택의 중간쯤을 펼쳐 쪽수를 보니 520쪽입니다 2. 찾고자 하는 ..

2017. 9. 4. 03:44

Language/Python

[ALGORITHMS]문제 11 퀵정렬

문제 11 퀵정렬 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어 보세요 앞서 병합 정렬로 줄 세우기는 학생들을 일단 두 그룹으로 나눠 각각 병합 정렬을 한 후, 정렬된 두 그룹에 있는 학생들의 키를 다시 비교하여 한 줄로 합치는(병합) 과정이었습니다. 이번에 배울 퀵정렬은 '그룹을 둘로 나눠 재귀호출'하는 방식은 병합 정렬과 같지만, 그룹을 나눌때 미리 기준과 비교해서 나눈다는 점이 다릅니다. 즉, 먼저 기준과 비교해서 그룹을 나눈 다음 각각 재귀호출하여 합치는 방식입니다. 1. 퀵정렬로 줄 세우기 1. 학생들에게 일일이 지시하는 것이 귀찮아진 선생님은 학생들이 알아서 줄을 서는 방법이 없을지 고민입니다. 그렇다고 열 명이나 되는 학생들에게 한번에 알아서 줄을 서라고 하면..

2017. 8. 31. 18:58