본문 바로가기

전체 글215

백준 11050: 이항 계수 1(java/C) 문제 풀이 이항 계수는 주어진 집합에서 주어진 개수만큼 순서 없이 뽑는 조합의 가짓수를 말한다.이항 정리로 전개했을 때 계수 어쩌고... 라고 뜰 텐데 그냥 고등학생 때 확통 순열 조합 하면서 배운 nCr이다.nCr 공식만 알고 있으면 해당 공식 그대로 이용해 쉽게 풀 수 있다. 팩토리얼을 구하기 위해 팩토리얼 계산 메소드 getFactorial()을 사용하여 풀이했으며, 이는 순환 알고리즘을 이용해 작성할 수 있다.  [JAVA]늘 그렇듯 BufferedReader 사용String[] input=in.readLine().split(" ");readLine()은 한 줄 전체를 읽는 메소드이므로 split()을 이용하여 띄어쓰기 단위로 한 번 나눠 주었다.Scanner 사용하려면 띄어쓰기 고하지 않고 ne.. 2024. 7. 6.
백준 2292: 벌집(java/C) 문제 풀이 중심(1)으로부터 떨어진 바퀴 수? 에 따라 나눌 수 있다중심을 0번째라고 하면 2~7은 1바퀴째, 8~19는 2바퀴째... 이런 식으로정리하면 아래와 같습니다.같은 구간에 속하는 방들끼리는 1번 방에서부터의 경유 방 개수(이하 거리라 하겠음)가 동일하고(원-반지름 개념으로 생각하셔도 괜찮을 듯)각 구간에 속하는 방 수는 다음 바퀴로 넘어갈 때마다 6개씩 증가한다. 같은 구간에 속하는 방은 중심에서부터 거리가 동일구간이 바뀔 때마다 거리가 1씩 증가이 둘을 이용해 풀이할 수 있다.int count=1; //중심일 때 거리 1int ran=2; //구간 최솟값 시작: 2if(N==1) System.out.println(1);else{ while(ran N이 1일 때는 1을 출력하면 되고, .. 2024. 7. 6.
백준 2775: 부녀회장이 될테야(java/C) 문제 풀이 2차원 배열을 사용해 풀 수 있을 것 같다 우선 k층 n호의 사람 수를 정리해 보면 아래와 같다.각 호실 별 사람 수를 저장할 int형 2차원 배열 aptArr를 설정했으며 층수에 관계없이 1호는 항상 1명이 거주하고, 0층의 k호에는 k명이 거주한다.그 외의 경우 (같은 층 바로 전 호의 사람 수) + (아래 층 같은 호의 사람 수)인 것을 알 수 있으므로aptArr[0][n]=n; //0층 n호는 n명aptArr[k][1]=1; //1호는 항상 1명aptArr[k][n]=aptArr[k][n-1]+aptArr[k-1][n];로 정리할 수 있다. for문을 사용하여 aptArr 배열을 먼저 완성한 다음, T 횟수만큼 k와 n을 입력받아 해당하는 호실의 사람을 꺼내 오는 방식으로 풀이하였다.. 2024. 7. 6.
배열의 응용: 다항식 표현 을 예시로 설명  1. 모든 계수를 배열에 저장하는 방법예시 다항식을 위와 같이 다시 쓸 수 있다. 모든 차수에 대한 계수 값들의 리스트인 (10, 0, 0, 0, 6, 3)을 배열 coef에 저장하고 다항식의 차수는 변수 degree에 저장하면, 하나의 다항식이 하나의 degree 변수와 하나의 coef 배열을 필요로 하므로 이들을 묶어 구조체를 만들고 이 구조체를 사용하여 하나의 다항식을 표현할 수 있다.#define MAX_DEGREE 101 //다항식 최대 차수+1typedef struct { int degree; //차수 float coef[MAX_DEGREE]; //계수 배열} polynomial;void main() { polynomial a = { 5, {10, 0, 0, 0, 6, 3} .. 2024. 7. 5.
순환-하노이탑 문제 하노이탑 문제- 막대 A, B, C가 주어졌을 때 막대 A에 쌓여 있는 원판 3개를 막대 C로 옮기되 아래 조건들을 만족해야 함한 번의 하나의 원판만 이동맨 위에 있는 원판만 이동크기가 작은 원판 위에 큰 원판을 쌓을 수 없음중간의 막대 B를 사용할 수 있으나 앞의 조건들을 지켜야 함- 막대의 개수가 많아질수록 문제가 복잡해짐→ 순환을 이용하여 문제 해결(순환이 일어날수록 문제의 크기(=옮겨야 하는 디스크의 개수)가 작아짐) n개의 원판이 A에 쌓여 있는 경우1. 위에 쌓여 있는 n-1개의 원판을 B로 이동2. 제일 밑에 있는 원판을 C로 이동3. B에 있던 n-1개의 원판을 C로 이동void hanoiTower(int n, char A, char B, char C) { //A에 쌓여있는 n개의 원판을 .. 2024. 7. 3.
반복-피보나치 수열 계산 피보나치 수열- 앞의 두 숫자를 더해 뒤의 숫자를 만듦- 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 순환 호출을 사용하여 구현int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n - 2) + fib(n - 1);}- 순환 호출이 진행될수록 계산 횟수 증가- 복잡도 T(n)=T(n-1)+T(n-2)+C- 시간 복잡도 O(2^n) 반복을 이용하여 구현int fib_iter(int n) { if (n == 0) return 0; if (n == 1) return 1; int pp = 0; int p = 1; int result = 0; for (int i = 0; i - result=p+pp: 앞.. 2024. 7. 3.
순환-거듭제곱 계산 순환을 사용하지 않고 x의 n제곱 값을 구하는 함수 작성double slow_power(double x, int n) { int i; double result = 1.0; for (i = 0; i - 루프 1회당 한 번의 곱셈이 필요하고 루프의 횟수는 n회- O(n)의 시간복잡도 순환을 사용하여 x의 n제곱 값을 구하는 함수 작성 1. 알고리즘power(x, n) :if(n==0) return 1;else if(n==짝수) return power(x^2, n/2);else if(n==홀수) return x*power(x^2, (n-1)/2);- x^n=(x^2)^(n/2)이므로double power(double x, int n) { if (n == 0) return(1); else if ((n % 2) .. 2024. 7. 3.
순환 순환(recurion): 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ex) 팩토리얼- n!을 정의하는 데 (n-1)!이 사용- (n-1)!을 정의하기 위해 다시 (n-2)!가 필요int factorial(int n){ if(n- C언어로 팩토리얼 계산 구현순환 호출의 내부적인 구현- 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일- 복귀 주소가 시스템 스택에 저장되고, 호출되는 함수를 위한 매개변수와 지역 변수를 할당받음→ 자기 자신의 시작 위치로 점프 순환 알고리즘의 구조- 자기 자신을 호출하는 부분과 순환 호출을 멈추는 부분으로 구성- 멈추는 부분이 없다면 스택을 모두 소모할 때까지 순환 호출을 반복하다 오류 발생if(n 순환 vs 반.. 2024. 7. 3.
자료구조와 알고리즘 자료구조와 알고리즘 자료구조(data structure): 프로그램에서 자료들을 정리하여 보관하는 여러 가지 구조- 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정됨 알고리즘(algorithm): 컴퓨터로 문제를 풀기 위한 단계적인 절차- 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것- 특정한 일을 수행하는 명령어들의 집합 입력: 0개 이상의 입력이 존재해야 함출력: 1개 이상의 출력이 존재해야 함명백성: 각 명령어의 의미가 명확해야 함유한성: 한정된 수의 단계 후에 반드시 종료되어야 함유효성: 각 명령어들은 실행 가능해야 함자연어흐름도(플로우차트)의사 코드(pseudo code): 알고리즘 기술에만 사용되는 언프로그래밍 언어.. 2024. 7. 3.
[명품자바] 7장 실습문제(10~13) 10. 그래픽 편집기 작성 [난이도 7]- Vector 이용- 추상 클래스 Shape와 이를 상속받는 Line, Rect, Circle 클래스- "삽입", "삭제", "모두 보기", "종료" 4가지 그래픽 편집 기능abstract class Shape { public Shape() {} public void paint() {draw();} abstract public void draw();}class Line extends Shape{ @Override public void draw() { System.out.println("Line"); }}class Rect extends Shape{ @Override public void draw() { System.out.println("Rect"); }}cl.. 2024. 7. 1.

티스토리툴바