쉽게 공부하는 컴퓨터과학

그림으로 이해하는게 훨씬 빠른 문제이다.(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문을 돌며 두 난쟁이의 키의 합에서 계속 빼서 남은 값이 리스트 안에 있는지 구한다. 단, 빼서 남은 값(다른 가짜..

그림에서 주어지는 방식으로 점이 복제되는 사각형이 있다. N단계일 때 그 점의 개수를 출력하는 문제이다. 풀이

받아야 할 거스름 돈이 주어지면 몇 개의 동전을 주어야 하는지 출력하는 문제이다. 풀이

10진법 수 N을 B진법으로 변환하여 출력하는 문제이다. 풀이