본문 바로가기

백준

 (81)
2563)색종이 https://www.acmicpc.net/problem/2563 흰색 도화지에 검은색 색종이를 붙인 후 검은색 색종이의 넓이를 구해야한다. 도화지에 색종이를 붙인 후 넓이를 어떻게 표현해야 할까? 검은색 색종이를 겹쳤을 때 중복 영역을 어떻게 처리해야 할까? 이차원 배열이 도화지나 색종이의 넓이를 표현하기에 적합하다.가로 5, 세로 5인 도화지를 위 그림처럼 5x5 이차원 배열로 표현할 수 있다. 좌표와 각 격자 공간의 중심이 일치하지 않기 때문에 격자 공간의 좌하단 좌표가 격자 공간을 대표한다고 간주한다.(0,1)에 2x2크기의 검은색 색종이를 붙였다.(2,1)에 2x2 크기의 검은색 색종이를 붙였다. 즉 2차원 배열에 색종이의 면적만큼 TRUE로 바꿔주고 그 수를 세기만 하면 된다. 중첩 영역은 T..
1789)수들의 합 https://www.acmicpc.net/problem/1789 S는 서로 다른 자연수 N개의 합이다. 문제는 최대인 N을 찾는 것이다. 그러니까 서로 다른 자연수를 최대한 많이 더해서 S를 만들어야 한다. S가 200이라 가정하고 바꿔서 생각해보자. 자연수를 최대한 많이 더해서 200을 만들려면 자연수 몇 개가 필요할까? 1을 200번 더해서 200을 만드는 방법이 가장 많은 갯수를 필요로 한다. 여기서 서로 다른 자연수가 될 수 있도록 200을 만드는 1들을 가능한 많이 묶는 방법이 뭘까? 하나의 묶음에 1을 하나씩 늘려나가는 것이다. (묶어서 합하면 서로 다른 자연수가 된다.) 그러나 이렇게 묶으면 마지막 1 몇 개를 하나로 묶기에는 갯수가 모자란다. 이 1들을 다른 묶음에 하나씩 보내주더라도 최..
10798)세로읽기 https://www.acmicpc.net/problem/10798 5개의 문자열이 주어지면 각 문자열의 i번째 낱말로 세로 단어를 만들고 이를 이어붙여 출력하는 문제다. C언어는 문자열의 끝이 NULL로 끝난다. 각 문자열의 길이가 달라 어떤 문자열의 i번째 낱말이 NULL일 수 있다. 이 경우 무시하고 넘어간다. i번째 낱말이 NULL이 아니면 verticalWord[t]에 넣고 t를 하나 증가시켜준다. 이를 출력해야하므로 마지막에는 NULL을 저장한다. 각 문자열을 저장할 때 배열에는 가비지 값이 있었다. 만약 이 길이를 다 채우지 못하는 문자열을 받고 세로 단어를 만들 때 가비지 값은 NULL이 아니기 때문에 가비지 값도 세로단어의 낱말로 취급된다. 그래서 배열을 할당할 당시 배열을 NULL로 초..
6376)e 계산 https://www.acmicpc.net/problem/6376 e를 구하는 공식도 나와있어서 풀기에 어려운 문제는 아니다. 그렇지만 팩토리얼 값과 e값을 i값에 따라 처음부터 구해가는 것이 아니라 동적 계획법으로 이전에 구했던 값을 이용하는 형태로 f와 e를 구했다. double형으로 표현된 정수를 구분하기 위한 방법도 사용됬다. 1234567891011121314151617181920212223242526272829303132#include#define MAX 9 int main() { double e[MAX+1] = {0.0}; int f[MAX+1]; f[1] = 1; for (int i = 2; i
4659)비밀번호 발음하기 https://www.acmicpc.net/problem/4659 주어진 입력이 3 가지 제약 조건을 지키는 지 확인하는 문제다. 제약 조건이 어떻게 구현되는가를 연습해볼 수 있었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include#include#define TRUE 1#define FALSE 0 int isVowel(char c) { int isVowel = FALSE; switch (c) { case 'a': isVowel = TRUE; break; case 'e':..
3460)이진수 https://www.acmicpc.net/problem/3460 십진수를 이진수로 만들고 최하위 비트의 자리가 0번일 때, 비트값이 1인 비트의 자리를 출력해야 한다. 십진수를 이진수로 바꾸기 위한 가장 쉬운 방법이 어떤 수를 2로 계속 나누어 그 나머지를 취하는 것이다. 가장 먼저 나누어 얻은 나머지는 최하위 비트이다. 이 순서대로 배열에 저장하면 거꾸로 이진수를 저장하는 셈이지만 인덱스를 차례로 증가시켜 출력해 문제의 요구를 만족시키엔 적합하다. 우선 주어진 수가 몇 개의 비트로 표현될 수 있는지 갯수를 센다. 그 수만큼 배열을 할당한다. 주어진 수를 2로 나눈 나머지를 배열에 차례로 저장하고 마지막엔 몫을 저장한다. 배열에 접근하며 각 비트값이 1인 인덱스만 출력한다. 123456789101112..
2799)블라인드 https://www.acmicpc.net/problem/2799 어려운 알고리즘을 요구하는 문제는 아니고 구현 실력을 시험해보기 위한 문제같다. ################ #****#****#****# #****#****#****# #****#....#****# #....#....#****# ################ #....#****#****# #....#****#....# #....#....#....# #....#....#....# ################입력이 이렇게 주어져도 한 줄 씩, 한 문자씩 모두 읽고 각 창문의 블라인드 상태를 파악할 필요는 없다. 창문은 세로로 4칸으로 이루어져 있고 *를 만날 때마다 상태를 하나씩 증가시키면 된다. 예를 들어 두 번째 층의 첫 번째 창문은..
2822)점수 계산 https://www.acmicpc.net/problem/2822 쉬운 문제여서 예전에 배웠던 퀵 정렬을 사용해서 풀었다. 정렬한 뒤 상위 5개의 점수합을 구하고 상위 5개 문제의 인덱스를 순서대로 출력해야 한다. 퀵 정렬을 살짝 변형했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include#define NUM 8 void swap(int *A, int *B) { int temp; temp = *A; *A = *B; *B = temp;} int partition(int A[],int B[],int p ,int r) { int i = p-1;..

티스토리툴바