쉽게 공부하는 컴퓨터과학

알고리즘의 효율을 측정할 때 우리는 복잡도(Complexity)라는 용어를 사용한다. 복잡도는 두 가지로 분류가 가능한데, 공간 복잡도(Space Complexity), 시간 복잡도(Time Complexity)이다. 공간 복잡도는 문제의 크기에 따라 알고리즘 수행에 필요한 메모리의 공간이 얼마나 필요한가를 의미한다.시간 복잡도는 문제의 크기에 따라 알고리즘 수행에 시간이 얼마나 걸리는가를 의미한다. 분석의 종류에는 여러가지가 있다. 입력 값들에 따라서 알고리즘의 수행 속도가 달라질 수 있다.예시로 수행 시간을 측정했는데 입력이 아주 운이 좋게 아무런 작업도 하지 않고 수행을 끝낼 수 있게 되는 최선의 경우(Best Case) vs 입력이 아주 나쁘게 들어와 한 번의 작업도 건너뛰지 말아야하는 최악의 경..

ADT(Abstract Data Type)는 직역하면 추상 자료형으로, 개발할 때 실제에서 쓰이기 위해 필요한 다양한 자료형들을 논리적으로 추상화하여 정의한 자료형을 의미한다.더보기이 때, ADT는 구현을 포함하지 않는다.우리가 흔히 알고 사용하는 자료구조들 또한 ADT를 기반으로 프로그래머가 실제로 구현해놓은 것이다.QueueStackLinked List이렇게 구현은 나중에 생각하고 어떤 기능들이 있는지 작성하는 것이 ADT라고 볼 수 있다.Java의 Interface와 유사하다고 보면 된다.interface 부분에서 함수를 정의해두고, 나중에 implements를 통해 구현을 하는 것과 동일하다고 볼 수 있다.

그림으로 이해하는게 훨씬 빠른 문제이다.(1) 1/1(2) 1/2(6) 1/3(7) 1/41/51/6(3) 2/1(5) 2/2(8) 2/32/42/5...(4) 3/1(9) 3/23/33/4......(10) 4/14/24/3.........5/15/2............6/1...............1이 입력으로 주어지면 1/1, 2가 주어지면 1/2, 3이 주어지면 2/1, 4는 3/1, 5는 2/2 ...나는 수학에 매우 약해서 문제를 거의 혼자 해결하지 못했다. 문제를 해결하기 위해선 '입력으로 주어진 수(이하 x)가 몇 번 대각선(이하 line)인가?'를 생각해야한다.1 = 12, 3 = 24, 5, 6 = 37, 8, 9, 10 = 4...이 후에는 1부터 line까지를 더한다.1 = 12..

A ^ B % C를 구하는 문제이다.파이썬으로 해결하면 너무너무 쉽게 해결할 수 있다.a, b, c = map(int, input().split())print(pow(a, b, c))이렇게 풀면 된다. 근데 이런 풀이는 내가 원하는 해답이 아니다. 실버 1이라는 난이도에 맞는 알고리즘을 사용해서 풀이하기를 원했다. 처음 고안한 로직이다.def pow(a, b) : if b 시간초과가 발생했다. 거듭제곱의 성질에 대해 찾아봤다. 찾아보니 거듭제곱을 할 때 A^B 제곱에서 B가 짝수이면 (A^(B / 2))^2 홀수면 A를 한 번 더 곱해주면 된다.10^4 == 10^2 * 10^2 10^5 == 10^2 * 10^2 * 10라는 것이다. 파이썬 재귀함수는 익숙치 않아서 찾아보고 작성했다.def div..

이 문제는 1406번 에디터 문제와 유사한 문제이다.1406번: 에디터[BOJ/백준] 1406번 파이썬 해결 [BOJ/백준] 1406번 파이썬 해결첫째 줄에 문자열이 주어지고, 둘째 줄에 명령의 수, 그 다음 줄 부터는 명령어가 주어진다.L은 커서를 왼 쪽으로 한 칸, D는 오른쪽으로 한 칸, B는 문자 삭제, P x는 커서 왼쪽에 x라는 문자를 추dev-crow.tistory.com다만, 차이점은 에디터는 한 줄에 한 명령어와 입력이 주어지고, 이 문제는 한 줄에 명령어와 입력이 한 번에 주어진다는 것이며, 최대 1,000,000개의 데이터가 주어진다는 것이다. 이 문제도 단순히 파이썬의 리스트를 연결리스트와 비슷하게 사용하겠다고 하면, 해결하지 못하는 문제이다.에디터와 유사하게 스택에 값을 데이터를 ..

요세푸스 문제이다. N명이 K번째 사람을 제거한다.처음엔 매우 쉽다고 생각하고 접근했었는데 시간초과의 벽에서 한 동안 헤메었다.josephus = [0]res = []n, k = map(int, input().split())for i in range(1, n + 1) : josephus.append(i)i = kprt_i = kwhile sum(josephus) : if josephus[i % (n + 1)] : if prt_i == k : res.append(josephus[i % (n + 1)]) josephus[i % (n + 1)] = 0 prt_i = 0 prt_i += 1 i += 1print(..

이 문제는 숫자 N(1 ~ 1,000,000)가 주어지고 N을 만들기 위해서 필요한 숫자 세트(0 ~ 9)가 몇 개인지 구하는 문제이다.9와 6은 뒤집어서 9가 6을, 6이 9를 표현할 수 있다.문자열로 n을 입력받아 리스트에서 해당 위치를 더하며 숫자 세트의 수를 구하는 로직을 짰다.n = input()set_arr = [0, 0, 0, 0, 0, 0, 0, 0, 0]for i in n : if int(i) == 9 or int(i) == 6 : set_arr[5] += 0.5 else : set_arr[int(i) - 1] += 1print(round(max(set_arr)))처음 짠 로직이며, 오답이다. 논리적으로 전혀 문제될 것이 없어서 조금씩 수정해가며 확인하..

첫째 줄에 문자열이 주어지고, 둘째 줄에 명령의 수, 그 다음 줄 부터는 명령어가 주어진다.L은 커서를 왼 쪽으로 한 칸, D는 오른쪽으로 한 칸, B는 문자 삭제, P x는 커서 왼쪽에 x라는 문자를 추가한다. 상세 조건은 위 문제를 참고한다.이 문제에는 알려지지 않은 조건이 몇 있었다.1. B 명령으로 문자열을 지운 후 커서는 어디에 있는가2. P 명령으로 문자열을 추가한 후에는 커서가 어디 있는가3. 시작 커서는 어디인가?그러나, 이 조건들은 이 문제를 파이썬 리스트나 배열로 해결할 때에나 의미가 있는 것이었다.즉, 시작 커서가 맨 오른쪽이라는 사실만 깨닫고 난 후에는 Stack을 이용하여 문제를 해결하는 것이 더욱 효율적이고 , 간단한 코드를 작성할 수 있었다.import sysinput = sy..

9명의 난쟁이들의 키가 주어진다. 이 중 7명의 난쟁이의 키를 오름차순으로 출력하면 된다.일곱 난쟁이의 키의 합은 100이다. 문제 해결문제 자체는 해결할 방법도 다양하고 쉽게 해결하는 방법도 존재한다.9 라는 한정된 입력과 7 이라는 정해진 출력을 고려하면 하나하나 비교해 볼 수도 있다.혹은 이중 for 문으로 두 명의 난쟁이를 계속 골라 빼보며 합이 100인지 찾아볼 수도 있다.찾아본 코드 중엔 combinations라는 것을 사용하기도 했지만 그것보다는 순수 파이썬으로 가장 효율적인 코드를 찾았다. 배열의 총합을 구하고 거기에 100을 빼서 가짜 난쟁이 두 명의 키를 구한다.이제 for문을 돌며 두 난쟁이의 키의 합에서 계속 빼서 남은 값이 리스트 안에 있는지 구한다. 단, 빼서 남은 값(다른 가짜..

본론에 들어가기 전에 이 작자가 왜 이렇게 오랜만에 글을 올리지 싶다면, 여러가지 사연이 있었다. 바쁘고 심한 일은 아니지만, 그냥 심적으로 많이 지쳤기 때문에 매우 오랜 기간 동안 쉬다 왔다. 라고 보는 것이 맞을 것같다. 또한, 대학에서 전공만 공부한다고 다가 아니라 교양 성적을 방어해야 하기에 더욱 좀 지쳤다고 봐야할 것이다. 가장 마지막으로 포스팅한 글이 파이썬 시작이었던거 같은데, 파이썬은 무난히 공부하고 있다.  추후 한번에 정리할 날이 올 것이다.그리고 마지막으로 C언어 뒷 부분도 중간고사가 끝난 후 한 번에 정리할 것이다. 그럼 이제 본론으로 들어가겠다. 이번 포스팅 주제로 들고 온 것은 천재들이 쓰는 노트앱, 나무위키를 사랑하는 사람들을 위한 노트앱, 본인이 ADHD라고 생각될 정도로 사..