본문 바로가기

분류 전체보기215

백준 1149: RGB거리(java/python) 문제풀이 동적 프로그래밍을 이용해 풀이하는 문제다.다른 DP 문제와 유사하나, N번 집의 색이 (N-1)번째 집의 색과 달라야 한다는 조건을 추가로 처리해 주어야 한다. 열의 원소가 0, 1, 2일 때를 각각 빨간색, 초록색, 파란색일 때라 하면dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + arr[n][0]dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + arr[n][1]dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + arr[n][2] 와 같이 나타낼 수 있다.  집의 개수와 집마다 각 색으로 칠하는 비용을 행과 열로 가진 2차원 배열 arr와 n번째 집까지의 비용 합을 저장할 2차원 배열 dp를 사용하였고, 이때 메모이제이션을 .. 2024. 9. 26.
백준 1914: 하노이 탑(java/python) 문제풀이 하노이 탑 문제는 재귀(recursion)를 이용해 풀 수 있다.hanoi(N, from, temp, to)원판의 개수 N과 세 장대 from, temp, to를 변수로 가지는 hanoi() 함수를 사용한다. 이때 hanoi() 함수는 ① N개의 원판을 ② temp 장대를 이용하여 ③ from 장대에서 to 장대로 옮긴다. N개의 원판을 from 장대에서 to 장대로 옮기려면, 우선 from 장대에 걸려 있는 원판들 중 가장 아래에 있는 것(=가장 큰 것)을 제외한 모든 원판을 temp 장대로 옮긴 뒤 남아 있는 원판을 to 장대로 이동시켜야 한다.hanoi(N-1, from, to, temp)이후, temp의 원판들을 to 장대로 옮기면 하노이 탑 문제를 해결할 수 있다.hanoi(N-1, t.. 2024. 9. 20.
순환-거듭제곱 계산 알고리즘(2) https://sysouthelloworld.tistory.com/81 순환-거듭제곱 계산순환을 사용하지 않고 x의 n제곱 값을 구하는 함수 작성double slow_power(double x, int n) { int i; double result = 1.0; for (i = 0; i - 루프 1회당 한 번의 곱셈이 필요하고 루프의 횟수는 n회- O(n)의 시간복잡도 sysouthelloworld.tistory.com위 글에 적지 않은 다른 방법이 더 있다.double pow(int x, int n) { int res = 1; int a = x; while (n > 0) { if (n % 2 == 1) { //excluded when remainder is 0 res = res * a; } a .. 2024. 9. 19.
백준 13909: 창문 닫기(java, python) 문제풀이 모든 창문이 닫힌 상태에서 시작한다는 것이 포인트이다. 창문이 마지막까지 열려 있으려면 창문의 상태를 바꿀 수 있는 사람이 홀수 명이어야 하므로, k번째 창문에 대해 k의 약수가 홀수 개이면 열려 있게 되고, 짝수 개이면 닫힌 채로 끝나게 된다. 따라서 n개의 창문이 주어졌을 때, n 이하의 약수가 홀수 개인 수의 개수를 구하면 해결된다. 어떤 수의 약수가 홀수 개이려면 그 수가 완전제곱수여야 한다.k의 약수들은 곱해서 k가 되는 쌍끼리 짝을 이루므로, k의 약수 개수가 홀수이려면 k가 완전제곱수여야 하는 것이다. 따라서 N 이하 완전제곱수의 개수가 정답이 된다. 1. javaimport java.util.Scanner;public class Main { public static void mai.. 2024. 9. 19.
백준 2003: 수들의 합(java) 문제풀이1. 이중 for문부분 수열의 왼쪽 인덱스를 i, 오른쪽 인덱스를 j라 한다. i가 n일 때 j를 n, n+1, n+2, ...로 증가시키며 합이 M이 되는 경우를 찾되, sum이 M을 처음으로 초과했을 경우 더 이상 탐색할 필요가 없으므로 반복문을 종료한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new Input.. 2024. 9. 9.
그래프 그래프(graph): 객체 사이의 연결 관계를 표현할 수 있는 자료 구조- 그래프 구조는 인접 행렬이나 인접 리스트로 메모리에 표현되고 처리- 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍으로 해결그래프의 정의와 용어 그래프: 정점(vertex)과 간선(edge)들의 유한 집합- 수학적으로는 G=(V, E)와 같이 표시- V(G)는 그래프 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합- 정점: 여러 가지 특성을 가질 수 있는 객체, 노드(node)- 간선: 정점들 관의 관계, 링크(link) 무방향 그래프(undirected graph): 간선을 통해서 양방향으로 갈 수 있는 그래프- 정점 A와 B를 연결하는 간선은 (A, B)로 표현- (A, B)와 (B, A)는 동일한 간선방향 그래.. 2024. 9. 6.

티스토리툴바