전체 글101 [G5] 백준 1074 - Z (Python3) https://www.acmicpc.net/problem/1074💡 해결방법분할정복 알고리즘을 적용해서 문제를 해결했다.👀 풀이항상 2**(N*2) 매트릭스(r, c) 좌표 정보위 두 정보를 바탕으로 (r, c)가 몇 사분면에 있는지 파악해서 N 번만에 몇 번만에 방문하는지 계산한다.🧾 코드# 1074N, r, c = map(int, input().split())ans = 0while N: N -= 1 # 제1사분면 if r = 2**N: ans += 2 ** (N*2) c -= 2**N # 제2사분면 elif r = 2**N and c = 2**N and c >= 2**N: ans += 3*(2**(N*2)) r -= 2.. 2024. 11. 10. 코틀린 기초 - 변수, 형변환, String, 입력, 반복문, 조건문 코틀린은 main 함수가 있어야지 실행이 가능하다.Java와는 다르게 세미콜론(';')을 붙이지 않는다. 붙여도 바르게 동작은 한다.변수 선언 var코틀린은 타입을 추론하는 기능이 있어서, 타입을 지정해주지 않아도 괜찮다.하지만 명시적으로 지정이 가능하다.var i = 10var i : Int = 10var name : String = "JJong"var point : Double = 11.28 상수 선언 val자바의 final과 동일하다. 자바는 클래스 안에, Main 함수로 실행했지만 코틀린은 클래스가 없이 main 함수만 있어도 실행할 수 있다.* 컴파일 타입 상수const를 앞에 붙임으로써 main 함수보다 우선해서 컴파일이 된다.형변환fun main() { var i = 10 var l =.. 2024. 10. 20. Tree (트리) 트리는 스택, 큐, 연결리스트와는 다르게 비선형적 자료구조이다.트리는 계층 구조로 이루어져 있다.계층 구조로 나타내기 적합한 자료는 가계도, 목차-내용, 폴더-파일 관계 등이 있다. 보통 일반 적인 경우에는 이진 트리를 많이 사용한다.특별한 경우(게임 맵, 웹사이트의 카테고리 등)에서는 삼진 이상의 다진 트리를 이용하기도 한다. 트리는 가지는 특징에 따라서 이진 트리, 완전 이진 트리, B-Tree, AVL트리, 레드 블랙 트리 등등 다양한 이름으로 불린다.마치 이브이같다.이 포스트에서는 트리의 특징에 대해서 설명하고, 트리의 개념을 이해하자.트리는 한 개 이상의 요소(노드)로 이루어진 유한 집합이다. 이들 중에서 특정 한 개의 노드는 root node라고 불리고, 나머지는 subtree(서브 트리)라고.. 2024. 10. 3. [Python] Dictionary 초기화, setdefault() setdefault를 언제 쓸까?Python에서 그래프를 Dictionary로 생성할 때에 귀찮은 점이 하나 있다.바로 Dictionary에서 새로운 key를 만들 때는 초기화를 해주어야 한다는 점이다.문제 코드,,N, M = map(int,input().split())G = {}for _ in range(M): p, k = map(int,input().split()) if p not in G: # 조건을 만들어서 초기화하기 G[p] = [k] else: G[p] += [k] if k not in G: # 양방향 그래프에선 이런 조건-초기화를 두 개 만들어야 한다. G[k] = [p] else: G[k] += [p]print(G)>> {1:.. 2024. 10. 3. [이것이 코딩 테스트다] 못생긴 수 - 다이나믹 프로그래밍 문제못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미합니다.1은 못생긴 수라고 가정합니다.이때 n 번째 못생긴 수를 찾는 프로그램을 작성하십시오. 입력 조건첫 째 줄에 n이 입력됩니다.(1 출력 조건n 번째 못생긴 수를 출력합니다.해결 과정첫번째 아이디어이다.1, 2, 3, 4, ..., n 순으로 탐색한다. 다시 말하면 1부터 n까지 선형탐색을 한다. 현재 위치의 수를 소인수분해해서 못생긴 수인지 파악하는 방법이다.하지만 소인수분해를 계산해야하는 시간적 번거로움이 생긴다.2, 3, 5로 나머지가 0이 아닐 때까지 나누는 함수를 만드는 것은 금방이다. 하지만 991번째 못생긴 수 부터 1000번째 못생긴 수를 보면, 소인수분해 계산에서 시간초과에 걸릴 수 있다고 생각했다.* [ ..., 5.. 2024. 9. 7. [이것이 코딩 테스트다] 효율적인 화폐 구성 - 다이나믹 프로그래밍 이 문제는 대학교 1학년 때 공부했던 이산수학에서 다룬 문제여서 금방 풀 수 있었다.그때 문제도 마찬가지로 2와 3의 화폐로 모든 화폐를 표현할 수 있냐는 문제였던 것 같다.2, 3, 2+2, 2+3, 3+3, ... 1 이하의 정수를 제외한 모든 화폐를 표현할 수 있었다. 문제의 입력 조건으로는 최대 입력이 100이라서 O(n^2) 으로도 충분하다. 그래서 2중 for문을 채택했다. 최소 화폐 단위가 2, 3, 7이라고 가정하자. 그러면a[i]를 위 화폐 단위로 만들 수 있을 때, a[i](최소 화폐 개수)는 min(a[i], a[i - 2]+1, a[i - 3]+1, a[i - 7]+1) 이다.이것은 이해를 돕기위해 세운 약간 어거지(?) 점화식이다. 실제로는 각 화폐 단위를 하나 씩만 비교하여 따진.. 2024. 9. 6. [S3] 백준 1463 - 1로 만들기(Python) https://www.acmicpc.net/problem/1463 풀이👀1부터 X까지 반복문으로 1회 순환한다.i (1에 대해서 dp[i]라 할 때, dp[i]는 1에서 출발하여 주어진 조건을 만족하며 i를 만들기 위해 필요한 연산 최소 횟수이다.그러면dp[i]는 (dp[i-1], dp[i//2], dp[i//3], dp[i//5]) 중에서 최솟값을 찾은 다음, +1을 한 값으로 결정난다.코드💻# 1로 만들기X = int(input())dp = [10**7] * (X+1)dp[1] = 0for i in range(2, X+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i//2] + 1, dp[i]) if i%3 == 0: .. 2024. 9. 5. [이것이 코딩 테스트다] 1로 만들기 - 다이나믹 프로그래밍 백준 1로 만들기와 같은 유형의 문제다.X에서 1로 만들기 방법이다. X에서 1로 한 번 순회한다.현재 위치 i (1에서 연산가능한 모든 숫자에 최소 연산 횟수를 기록한다.i가 1이 될 때까지 위 과정을 반복한다.# 1로 만들기X = int(input())dp = [10**8] * (X+1)dp[X] = 0for i in range(X, 0, -1): dp[i-1] = min(dp[i]+1, dp[i-1]) if i%2 == 0: dp[i//2] = min(dp[i]+1, dp[i//2]) if i%3 == 0: dp[i//3] = min(dp[i] + 1, dp[i//3]) if i%5 == 0: dp[i//5] = min(dp[i] + 1, .. 2024. 9. 5. 이전 1 2 3 4 5 6 ··· 13 다음
