본문 바로가기

Study

 (47)
[Algorithm] 정렬: 버블 정렬, 삽입 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 정렬 문제 => n개의 서로 다른 수가 주어졌을 때, 이들을 이동하여 점점 커지게(오름차순), 또는 점점 작아지게(내림차순) 만드는 문제 ex) 9, 3, 5, 7 => 3, 5, 7, 9 - 한 문제를 풀기 위해서 여러가지 방법이 가능하다. - 방법마다 특징이 다르다. - 기본적인 문제이면서, 실생활에 자주 쓰인다. - 시간 복잡도, 최적성에 대해서 증명이 쉽다. 정렬할 데이터가 담긴 배열의 각 원소를 O(1) 시간에 접근 가능하다고 가정한다. (데이터가 메인 메모리에 저장되어 있다고 가정한다.) 버블 정렬 1. 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환한다. 2. 맨 끝까지 ..
[Algorithm] 알고리즘 기초 (3) + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 탐색 문제 1 정렬되지 않은 배열 E[1...n]에서, 어떤 값 k가 있는지 찾으시오. 만약 있다면 E[i]=k인 i를, 없으면 -1을 출력하라. ans = -1 E = list(map(int, input().split())) k = int(input()) for i in range(len(E)): if k == E[i]: ans = i break print(ans + 1) => 모든 원소를 하나씩 k 값인지 탐색 비교를 한 번 할 때마다, 원소 한개가 답인지 아닌지를 알 수 있다. 따라서 총 n번의 비교가 필요하다. - 비교를 하지 않으면 답인지 아닌지 알 수 없다. - n번 비교를 하지 않으려면 공짜로는 되지 않는다...
[Kotlin] 널 가능성 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. 널 (NULL) null은 아무 것도 참조하지 않는 참조 값의 특별한 상태이다. null에 대해서 멤버 접근을 시도하면 NullPointerException이 발생한다. (컴파일 시간에 파악이 되지 않아 최악의 에러 중 하나로 간주) Kotlin에서 일반 참조형에는 null을 담을 수 없다. (에러 발생 => NullPointer Exception 예방) // 문자로 이루어진 문자열인지 확인하는 함수 fun isLetterString(s:String): Boolean { if (s.isEmpty()) return false // 빈 문자열이라면 false for (ch in s) { // 문자가 아니라면 if (!ch.is..
[Algorithm] 알고리즘 기초 (2) + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 알고리즘 설계 과정 - 크고 복잡한 문제의 해법을 바로 설계하는 것은 어렵다. => 문제를 분석하여, 풀 수 있는 크기의 작은 문제들로 나누고, 이 문제들을 푼 후, 각 문제들 간의 관계를 이용하여 해법을 연결한다. 하노이 탑 문제 기둥 1에 있는 n개의 원반을 어떻게 규칙을 만족하면서 기둥 3으로 옮길 것인가? 규칙 1. 언제나 원반은 1개씩 옮길 수 있다. 규칙 2. 작은 원반위에 큰 원반은 옮길 수 없다. n = 1, 2인 경우에는 쉽게 풀 수 있으나 조금만 커지면 직접 푸는 것은 어렵다. => 알고리즘 설계 기법 중 되부름(recursion, 재귀)을 이용한다. n = 1인 경우, 그냥 ..
[Kotlin] 함수 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. Kotlin 함수의 예 import kotlin.math.PI // kotlin 패키지에서 PI 상수를 가져옴 fun circleArea(radius: Double): Double { // 함수의 정의 return PI * radius * radius } fun main() { print("Enter radius: ") val radius = readLine()!!.toDouble() println("Circle area: ${circleArea(radius)}") } Kotlin 함수의 특징 (1) - 파라미터의 타입은 항상 지정해야 한다. fun circleArea(radius: Double): Double // O f..
[Algorithm] 알고리즘 기초 (1) + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 알고리즘의 정의 - 어떤 문제를 푸는 알고리즘: 어떤 입력에도 정확한 출력을 유한한 시간에 내는 프로그램 1. 어떤 입력: 문제가 풀기 쉽든, 어렵든, 입력의 크기가 작건, 크건 문제를 풀 수 있다. => 어떤 경우에는 정답을 내지 못한다면, 우리는 그 프로그램을 믿고 쓸 수 없다. 2. 정확한 출력: 문제가 요구하는 조건을 만족한다. => 정답이 요구하는 조건이 무엇인지를 명시할 수 있다. (무엇이 정답이고, 오답인지 알 수 있어야 한다) 3. 유한한 시간: 무한 루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. + 튜링: 어떤 문제가 무한 루프에 빠질지 아닐지를 판단할 수 없다. (살아 생전에 답을 볼 수 없다.)..

티스토리툴바