티스토리

작은 다락방

검색하기

블로그 홈

작은 다락방

beyond1.tistory.com/m

포도몽2 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

6603)로또 https://www.acmicpc.net/problem/6603 k개의 수가 있는 집합 S에서 6개의 수들로 만들 수 있는 조합을 모두 출력해야 한다. DFS를 변형해 문제를 푼다는 사실은 알았지만 어떻게 변형해야 할 지 몰라서 결국 다른 사람의 코드를 봤다. DFS에 시작값을 주고 시작값부터 k까지 i값을 증가시키며 DFS가 재귀 호출할 때 i+1을 넘겨주면 재귀 호출의 깊이가 깊어질 때 한 층 낮았던 i값을 다시 볼 필요가 없다. 예를들어 0~3까지 수열을 깊이가 3일 때까지 DFS를 수행할 때 DFS의 콜트리에서 i값은 아래 그림과 같다. 123456789101112131415161718192021222324252627282930#include#define LOTTO_NUM 6using names.. 공감수 0 댓글수 0 2019. 3. 16.
1260)DFS와 BFS https://www.acmicpc.net/problem/1260 DFS 조지는 중이라 DFS만 쓴다. 그래프의 크기와 간선에 대한 정보가 주어졌을 때 그래프를 DFS로 노드를 방문한 순서와 BFS로 방문한 순서를 각각 출력해야 한다. 지금은 DFS를 공부중이니 DFS로 풀어낸 방법을 복습겸 적는다. 우선 주어진 입력 중 노드의 갯수 n으로 인접행렬의 크기를 설정한다. 그리고 방문 여부를 결정하는 visited 배열을 n 크기만큼 할당받는다. 이후 노드간 연결 정보를 차례대로 입력받는다 무방향 그래프이기 때문에 , 모두 연결됬음을 표시해야 한다. 그래프 입력이 완료되면 DFS를 수행한다. DFS는 인접행렬 graph와 visited, 시작점 s를 넘겨 받고 그래프를 순회한다. graph에서 s에 접근한 .. 공감수 0 댓글수 0 2019. 3. 16.
1012)유기농 배추2(DFS) https://www.acmicpc.net/problem/1012 삼성 역테 준비할 겸 DFS 배우고 관련 문제 조지려 한다. 이 문제를 처음 풀었을 때 내가 문제를 푼 방식이 DFS인 줄도 모르고 풀었다. FM DFS와는 차이가 있긴 했지만 DFS의 변형인 것은 분명했다. 원래 DFS는 연결 그래프를 빠짐 없이 방문하는 순회 알고리즘이다. 그러나 DFS는 그래프만 다룰 수 있는 것이 아니라 배열도 순회할 수 있다. 그래프의 관점에서 배열을 바라보는 것이다. 2차원 배열의 격자 공간 하나하나가 노드이고 인접한 방끼리 연결되어있다 생각하면 편하다. 그렇다고 해서 배열의 방 갯수만큼 인접리스트나 인접행렬을 만드는 것은 좋은 방법이 아니다. 예를들어 4x4 배열을 DFS로 순회할 때 16개의 노드를 방문해야 .. 공감수 0 댓글수 0 2019. 3. 16.
1009)분산처리 https://www.acmicpc.net/problem/1009 정수 a와 b가 주어지면 1~a^b까지의 수를 1번부터 10번 컴퓨터로 보내야 한다. 공교롭게도 b의 크기가 최대 1000000이어서 직접 수를 구해 컴퓨터에 집어넣는다는 생각은 접어야 한다. 그러나 a를 b번 곱하더라도 일의 자리 한 자리만 생각한다면 수가 너무 커지는 것을 걱정할 필요가 없다. 예를들어 9를 625번 곱하는 경우를 생각해보자. 9 * (9*9*...*9)에서 오른쪽 그룹에 있는 9를 하나 가져와 왼쪽의 9와 곱한다. 그러면 81 * (9*9*...*9)가 되는데 일의 자리 한 자리만 생각해서 1 * (9*9*...*9)로 봐도 문제가 없다. 어차피 컴퓨터가 10대 있기 때문에 일의 자리가 n인 것들은 n번 컴퓨터로 보내.. 공감수 0 댓글수 0 2019. 3. 16.
3208)배고픈 애벌레 https://www.acmicpc.net/problem/3208 처음 이 문제를 접했을 때 시계 방향으로 배열을 순회해야 한다고 생각했다. 그래서 배열을 시계방향으로 순회하며 안쪽으로 파고드는 함수를 만들었다. 그리고 방향이 바뀌는 지점에서 수를 세도록 재귀 함수를 만들었다. 내가 기대한대로 재귀 함수가 동작하지 않았는데 재귀 함수에 대한 이해가 부족한 듯하다. 친구에게서 보다 쉽고 신박한 풀이를 듣게되어 복습겸 글로 남긴다. 애벌레가 배열을 시계방향으로 순회할 때 그려지는 경로에 규칙이 숨어있다. 배열의 크기가 주어질 때 C(열 길이)가 R(행 길이)보다 큰 경우를 생각해보자. R> C; if (R > C) { cout 공감수 0 댓글수 0 2019. 3. 15.
1373)2진수 8진수 https://www.acmicpc.net/problem/1373 2진수를 8진수로 변환하는 문제다. 학교에서 8진수를 2진수를 변환하는 방법에 대해 배웠는데 약간 응용해보고자 한다. 각 8진수와 이진수가 대응되는 모습을 표현했다. 0 : 000 , 4 : 1001 : 001 , 5 : 1012 : 010 , 6 : 1103 : 011 , 7 : 111 8진수로 13을 표현할 때 위 테이블을 사용하면 편하게 바꿀 수 있다. 각 자리 숫자를 떼어내 대응되는 이진수로 바꿔주기만 하면 된다. 따라서 8진수 13은 001011이다. 2진수를 8진수로 바꾸는 과정을 생각해보자. 110101을 8진수로 바꾸려면 우선 세 자리씩 끊어야 한다. 110 / 101 로 나뉘는데 굳이 대응되는 8진수를 찾을 필요는 없고 1.. 공감수 0 댓글수 0 2019. 3. 11.
1158)조세퍼스 문제 https://www.acmicpc.net/problem/1158 문제를 읽고 떠오르는 대로 풀어내는 습관을 고칠 필요가 있을 듯하다. 아니면 풀이를 생각한 후 더 빠른 방법은 없을까 고민해보거나 채점 현황을 보니 C언어 중에서 메모리가 꽤 크고 속도가 빠른 풀이는 자료 구조를 사용한 것 같고 메모리가 작고 속도가 느린 풀이는 나랑 비슷하게 푼 것같다. 메모리가 작고 속도도 빠른 풀이도 있었다. 처음 이 문제를 풀었을 때 %연산만 잘 사용하면 될 것이라 생각했다. 예를들어 수열 1~7에서 m = 3인 조세퍼스 수열을 만드는 경우를 생각해보자. 1 2 3 4 5 6 7에서 첫 항부터 count를 하나씩 증가시키며 각 항에 접근한다. count = 1일때 1에 접근하고, count = 2일때 2에 접근하고 .. 공감수 0 댓글수 0 2019. 3. 4.
10824)네 수 https://www.acmicpc.net/problem/10824 4개 수가 주어질텐데 앞의 두 개를 이어붙여 정수 하나를 만들고 뒤의 2개를 이어붙여 정수 하나를 만들어 더한 결과를 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334#include#include#define LENGTH 6 int main() { char strnum[4][LENGTH+1]; char A[2*LENGTH+1], B[2*LENGTH+1]; int t = 0; for (int i = 0; i 공감수 0 댓글수 0 2019. 3. 3.
1004)어린 왕자 https://www.acmicpc.net/problem/1004 시작점에서 도착점까지 행성계를 진입/이탈 하는 최소 횟수를 구해야 한다. 되게 어려워 보이지만 잘 관찰해보면 점이 원 내부에 있는가 외부에 있는가에 따라 진입/이탈 횟수가 결정됨을 알 수 있다. 위 그림에서 왼쪽 빨간 점은 아주 큰 행성계 하나에만 포함되어 있고 오른쪽 빨간 점은 두 개의 행성계에 포함되어 있다. 각 점이 행성계에 몇 번 포함됬냐에 따라 진입/이탈 횟수를 쉽게 알 수 있다. 어떤 점이 원 안에 포함됬는 지 여부를 확인 하려면 P(x0, y0)을 C : (x-a)^2 + (y-b)^2에 대입했을 때 C(x0,y0) > r^2이면 점이 원 바깥에 있고 C(x0,y0) < r^2이면 점은 원 안에 있다. 그림처럼 두 점이 같은 .. 공감수 0 댓글수 0 2019. 3. 1.
14910)오르막 https://www.acmicpc.net/problem/14910 수열의 각 항들이 입력으로 주어지면 수열이 비내림차순 수열인지 아닌지 판단해야 한다. 입력의 갯수가 주어지지 않기 때문에 몇 개의 수열을 입력받을 지 모른다. 질문 검색을 뒤져보니까 좋은 테크닉이 있더라. while( scanf("%d",&value) != EOF) 반복문 조건을 이렇게 해두면 입력이 끝나면 종료할 수 있다. 반복문 구조 때문에 입력받는 순간에 판단을 계속해야 한다. 이전 항과 현재 항을 비교해 내림차순인게 하나라도 있으면 그 수열은 비내림차순 수열이 아니다. 123456789101112131415161718192021#include typedef enum _BOOL { TRUE = 1, FALSE = 0}BOOL; in.. 공감수 0 댓글수 0 2019. 2. 26.
2991)사나운 개 https://www.acmicpc.net/problem/2991 개1은 시간 a동안 짖고 b동안 쉬며 개2는 시간 c동안 짖고 d동안 쉰다. 개들에게도 짖는 주기가 있다. 이 주기는 펑크없이 쭉 반복되기 때문에 배달원이 도착할 때 이 주기 안에 있을 수 밖에 없다. 배달원이 도착한 시간을 t라 할 때 주기 안에 배달원이 도착한 시점(h라 하자)은 h = t%(a+b)이다. 0 공감수 0 댓글수 0 2019. 2. 24.
2210)숫자판 점프 https://www.acmicpc.net/problem/2210 문제에서 제시된 규칙대로 숫자판에 접근해 만들어 질 수 있는 수는 아주 많다. 또한 중복되는 수들도 많기 때문에 중복되지 않게 규칙대로 만들어지는 수들을 저장해야 한다. 우선 규칙대로 수를 만드는 방법에 대해 생각해보자. 이를 위해 4방향으로 탐색하는 재귀함수를 응용했다. count를 이용해 6번 방향탐색을 한다. 숫자판의 각 숫자에 접근해 그 숫자들을 기록해야 한다. value 값을 10을 곱한 뒤(초기값 0) 기존 원소를 기준으로 동서남북 방향의 원소에 접근해 얻은 값을value에 합산한다. 그리고 이 value를 다음 호출할 함수로 넘긴다. 예를 들어 방향탐색에 의해 순서대로 1->2->3 순으로 접근한다고 하자. value = 0에.. 공감수 0 댓글수 0 2019. 2. 23.
6679)싱기한 네 자리 숫자 https://www.acmicpc.net/problem/6679 수의 본질에 대해 조금 생각하게 해준 문제였다. 일상 생활에서 쓰는 수 표현 방법은 십진법이다. 십진법은 수라는 물리량을 10개의 숫자로 표현하는 방법이다. 16진법은 수를 표현하기 위해 숫자 16개를 사용했을 뿐이다. 몇 개의 숫자로 수를 표현하든 수의 크기는 변하지 않는다. 예를들어 십진법으로 표현된 30을 생각해보자. 30은 16진법으로 표현했을 때 1E이다. 1E를 10으로 나눈 나머지의 크기는 10진법으로 표현하든 16진법으로 표현하든 크기는 다르지 않다. 10진법으로 표현된 수의 각 자릿수를 구하기 위해 몫을 10으로 반복적으로 나눈다. 12, 16진법도 각 자릿수를 구하기 위해 12,16을 반복적으로 나눈다. 그리고 10,12.. 공감수 0 댓글수 0 2019. 2. 23.
2740)행렬 곱셈 https://www.acmicpc.net/problem/2740 행렬 곱셈할 때 인덱스만 신경쓰면 쉽게 구현할 수 있다. 3x2인 행렬 A와 2x3인 행렬 B를 곱한다고 하자.A의 1행과 B의 1열을 곱할 때 i는 A의 행을 고정하고 k는 B의 열을 고정한 상태에서 j를 움직여 각각의 원소를 매칭시키고 그 결과를 C[i,j]에 저장하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include int main() { int N,M, K; int **A, **B, **C; int temp; scanf("%d %d",&N,&M); A = (int **)malloc(siz.. 공감수 0 댓글수 0 2019. 2. 21.
2312)수 복원하기 https://www.acmicpc.net/problem/2312 어떤 수를 소인수분해하려면 그 수 이하의 소수로 나눌 수 없을 때까지 나눠봐야 한다. 에라토스테네스의 체로 100000 이하의 소수를 미리 구해놓는다. 주어진 수를 2부터 그 수까지 소수로 나눌 수 없을 때까지 나누고 나누어지는 경우 그 소수를 하나 카운팅한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include#define MAX 100000 typedef enum _BOOL { TRUE = 1, FALSE = 0}BOOL; void initArray(int A[MAX + 1], int n).. 공감수 0 댓글수 0 2019. 2. 21.
2667)단지 번호 붙이기 https://www.acmicpc.net/problem/2667 자료구조나 알고리즘 공부를 똑바로 안해서 자료구조, 알고리즘 활용하는 문제는 피하면서 문제를 푸는데 선택할 수 있는 문제의 폭이 점점 좁아지는 것같다. 특히 3~4문제에 한 문제 꼴로 DP문제가 나오는데 DP 공부를 안해서 DP를 걸렀더니 풀 수 있는 문제가 많지 않다. 이 문제 유형은 세 번째 풀어봐서 어렵지 않게 풀었다. 맵을 입력 받으면 차례로 읽다가 1을 만나면 인접한 영역을 방문하면서 그 수를 세고 방문한 영역을 0으로 만든다. 인접한 영역의 방문이 끝나면 수를 반환한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849.. 공감수 0 댓글수 0 2019. 2. 20.
2965)캥거루 세 마리 https://www.acmicpc.net/problem/2965 수직선 위에 서로 다른 정수점 세 개가 주어진다. 가장 바깥쪽에 있는 정수점 하나는 다른 두 정수점 사이로 뛰어들 수 있지만 다른 정수점과 겹칠 수는 없다. 이 규칙으로 정수점 사이를 뛰어들 때 최대한 많이 뛰는 횟수를 찾는 문제다. 예를들어 정수점이 1,4,9라고 하자.정수점은 위 그림과 같다. 여기서 1이 4~9 사이로 뛰어들든가 9가 1~4 사이로 뛰어드는 방법이 있다. 딱보기에도 1이 4~9사이로 뛰어드는 방법이 4~9의 간격이 크기 때문에 많이 뛸 수 있어 보인다. 여기서 가능하면 정수점 사이의 간격을 크게만들어주는 방향으로 뛰어드는 것이 좋다는 것을 알 수 있다. 정수점 1이 4옆으로 뛰어들었다. 애매모호하게 6이나 7로 뛰어든.. 공감수 0 댓글수 0 2019. 2. 19.
10757)큰 수 A+B https://www.acmicpc.net/problem/10757 두 수를 더해 그 결과를 출력하는 쉬운 문제처럼 보이지만 더하는 두 수가 10^10000보다 작다. int나 long long 타입으로 위처럼 큰 수를 다룰 수 없기 때문에 문자열로 처리해야 한다. 두 수의 합을 구현하려면 sum과 carry를 고려해야 한다. 두 수의 길이가 어떻든 맨 마지막 자리수 끼리 맞추고 각 자리수들을 더한다. 예를 들어 1234 + 987을 더할 때 가장 마지막 자리끼리 더하면 sum = 11이다. sum>10이므로 carry가 발생했다. sum에서 10을 빼주고 carry에 1을 대입한다. sum을 result 배열에 넣어준다. 두 번째 자리를 더하면 sum = 3+8+carry 이므로 sum = 12이다. .. 공감수 0 댓글수 0 2019. 2. 19.
15501)부당한 퍼즐 https://www.acmicpc.net/problem/15501 처음에 1~n에서 한 번씩 숫자가 나오는 수열이 주어진다. 1 2 3 4 5처럼 주어질 수도 있고 3 2 5 1 4처럼 특별한 규칙없이 수열이 주어질 수 있다. 처음 주어진 수열을 A라고 하자. 게임 규칙에 따라 수열 A로 가능한 연산은 뒤집기와 왼쪽, 오른쪽 밀기이다. 수열 A가 1 2 3 4 5일때 이 수열을 뒤집으면 5 4 3 2 1이다. 수열 A를 왼쪽으로 밀어내면 2 3 4 5 1, 오른쪽으로 밀어내면 5 1 2 3 4이다. 이후 수열 B가 주어지는데 수열 A로 위 연산을 통해 수열 B로 만들 수 있는 지 알아내야 한다. 뒤집기, 왼쪽, 오른쪽 밀어내기 연산을 해도 바뀌지 않는 것이 있다. 바로 수열의 순서이다. 예를들어 수열 .. 공감수 0 댓글수 0 2019. 2. 18.
16396)선 그리기 https://www.acmicpc.net/problem/16396 선분의 시작점과 끝점을 입력으로 받는다. 요것을 그대로 일차원 배열에 넣으면 된다. 예를들어 1 10은 1부터10까지 선분을 말하는데 일차원 1~9까지 각 방을 TRUE로 바꿔주면 된다. 총 길이는 10000을 넘지 않으므로 미리 10000개의 방을 잡아놓고 입력에서 최소 시작점과 최대 끝점을 찾아서 최소 시작점부터 최대 끝점까지 TRUE인 것의 수를 세면 된다. 123456789101112131415161718192021222324252627282930313233#include#define MAX(A,B) (A>B)?A:B#define MIN(A,B) (A 공감수 0 댓글수 0 2019. 2. 17.
14891)톱니바퀴 https://www.acmicpc.net/problem/14891 똑바로 글을 읽어야 한다는 걸 깨닫게 해준 문제였다. 톱니가 어떻게 회전하는 지를 잘 파악해야 한다. 첫 번째로 문제를 풀 때 톱니가 회전한 후, 양쪽의 톱니가 맞물리는 지 검사했다. 두 번쨰로 문제를 풀 땐 선택한 톱니가 회전하기 전 양쪽의 톱니가 맞물리는 지 검사하고 첫 번째 사용했던 코드를 그대로 가져다 썼다. 세 번째로 문제를 풀었을 때 제대로 비로소 문제를 이해하게 됬는데 =_=... 톱니가 회전하기 전에 톱니들 끼리 맞물렸을 때 극이 같은 지, 다른 지 검사하고 다른 경우 회전방향을 토글시킨다. 회전시키기 전에 각 톱니의 회전 방향을 배열에다가 저장해야 한다. 그리고 저장해둔 회전 방향에 따라 톱니를 회전시켜야 한다. 문제를 .. 공감수 0 댓글수 0 2019. 2. 16.
2583)영역 구하기 https://www.acmicpc.net/problem/2583 흰 배추벌레 문제랑 비슷하다. 주어진 입력을 처리하는 방법부터 생각해보자. 직사각형의 영역을 입력할 때 왼쪽 아래가 시작점이고 오른쪽 위가 끝나는 점이다. 이 점들은 아래 그림처럼 x,y 좌표계의 좌표다. 전체 영역에서 어떤 영역의 면적을 표현하기 위해 2차원 배열을 사용할텐데 2차원 배열은 아래 그림처럼 i,j의 증가 방향이 x,y 좌표계와 일치하지 않는다는 점을 유의해야 한다.이 문제는 연속하는 흰색 영역의 갯수와 그 크기를 출력하는 문제다. 위 그림에서 흰색 영역의 갯수는 3개이고 각각의 크기는 1, 7, 13이다. 연속하는 영역의 크기를 구하기 위해 재귀적으로 4방향 탐색 방법을 사용할 것이다. 특정 영역의 면적은 TRUE로 표현했.. 공감수 0 댓글수 0 2019. 2. 16.
10158)개미 https://www.acmicpc.net/problem/10158 가로 길이가 w, 세로 길이가 h인 격자 공간에 (p,q)에 개미를 두면 1시간 후에 개미는 (p+1,q+1)으로 이동한다. 개미가 격자 공간의 경계에 부딪히면 운동방향이 바뀐다. 이것을 쉽게 표현하기 위해 개미는 한 시간 뒤에 (p+dx, q+dy)로 이동한다고 하자. (초기 dx = 1, dy = 1) 개미가 x = 0, x = w에 부딪힐 때 x축 이동 방향이 반대로 바뀐다. 예를들어 개미의 이동 방향이 dx = 1, dy = -1일 때 x = w에 부딪히면 dx = -1, dy = -1로 바뀐다. 개미가 y = 0, y = h에 부딪힐 때 y축 이동 방향이 반대로 바뀐다. 12345678910111213141516171819202.. 공감수 1 댓글수 0 2019. 2. 14.
10159)저울 https://www.acmicpc.net/problem/10159 물체의 무게는 구체적으로 알 수 없지만 물체 끼리 비교해서 얻은 대소 관계는 알 수 있다. 주어진 예제에서 각 물체의 대소 관계는 아래와 같다. 1>2, 2>3, 3>4, 5>4, 6>5 각각의 물체를 비교한 결과를 이어 붙이면 아래처럼 정리할 수 있다. 1>2>3>4 6>5>4 1번 물체는 1,2,3,4와 대소 관계를 확인할 수 있지만 5,6과 대소 관계는 확인할 수 없다. 이 관계를 조금 더 쉽게 표현할 수 없을까 고민하다가 방향성 그래프와 유사한 면이 있음을 알게됬다. 4번 물체는 1,2,3번 물체와 5,6번 물체와 대소 관계를 알 수 있는데, 1,2,3번 물체는 5,6번 물체와 대소 관계를 알 수 없다. 여기서 1,2,3번은 4번.. 공감수 0 댓글수 0 2019. 2. 13.
2578)빙고 https://www.acmicpc.net/problem/2578 빙고 게임을 하는 방법은 누구나 잘 알고 있다. 어떻게 빙고 게임을 하는지 생각해보면 쉽게 문제를 풀 수 있다. 1.우선 자신의 보드를 만들기 위해 5x5만큼의 수들을 입력 받는다. 2.사회자가 부른 수 하나를 입력 받고 내 빙고판에 해당 수가 있는 지 검사한다. 2-1.내 빙고판에 해당하는 수가 있다면 그 위치에 CHECK를 저장한다. 3.자신의 보드가 빙고인지 검사한다. 빙고인지 검사하기 위해 일렬로 CHECK가 나열되어 있는지 검사한다. CHECK는 0에 이름을 붙인 것인데, 보드의 어떤 수를 합하더라도 0보다 크다. 그래서 한 줄에 CHECK로 나열되어 있다면 그 라인의 합은 0이다. 라인 검사를 통해 라인 합이 0이 되는 경우를 .. 공감수 0 댓글수 0 2019. 2. 13.
2607)비슷한 단어 https://www.acmicpc.net/problem/2607 같은 구성을 지닌 단어란 알파벳의 종류가 같고, 각 알파벳 별로 갯수가 같은 두 단어를 말한다. 예를들어 기준이 되는 단어 ABC, 다른 단어 CAB는 서로 같은 구성을 가진다. 또 기준이 되는 단어에 알파벳을 하나 넣거나, 빼거나, 바꿀 때 두 단어가 같은 구성이 되면 비슷한 단어가 된다. 예를들어 기준 단어 ABC와 ABCD는 비슷한 단어다. ABC에 D를 넣으면 ABCD와 같은 구성이 되기 때문이다. ABC와 AB도 비슷한 단어다. ABC에서 C를 빼면 같은 구성이기 때문이다. ABC와 ABD는 어떨까. C를 D로 바꿔 주면 같은 구성이기 때문에 두 단어는 비슷한 단어다. 위 예를 가지고서 각 알파벳의 갯수를 배열로 표현해보자. 1... 공감수 1 댓글수 0 2019. 2. 12.
2606)바이러스 https://www.acmicpc.net/problem/2606 주어진 예제를 그래프로 표현하면 아래 그림과 같다.1번 컴퓨터에 어떻게든 연결된 컴퓨터는 감염된다. 우선 네트워크를 표현하기 위해 이차원 배열을 할당하고 두 노드 사이에 간선이 있으면 TRUE를 저장한다. 1번 노드에서 1~n번 노드 중 간선이 있는 경우 그 노드를 방문한다. 방문한 노드가 i번 노드일 때 해당 노드에 감염 여부를 TRUE로 바꿔준다. i번 노드에서 1~n번 노드 중 간선이 있을 때 그 노드를 방문한다. 이미 감염된 경우 빠져나온다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#define TRUE.. 공감수 0 댓글수 0 2019. 2. 12.
2605)줄 세우기 https://www.acmicpc.net/problem/2605 줄 세우는 방법이 특이하지만 어려운 문제는 아니다. 줄을 서는 사람은 숫자를 받게 되는데 그 수만큼 앞으로 가면 된다. 삽입 정렬을 약간 응용했다. 수를 입력받았을 때 입력받을 위치에서 그 수만큼 앞쪽에서 입력받아야 한다. 예를들어 순서대로 0 1 1 3 2를 받았다고 치자. 4번째 학생이 받은 번호는 3이기 때문에 4가 저장될 위치는 t에서 3칸 앞에 있다.. 삽입 위치부터 한 칸씩 밀어내면 된다. 12345678910111213141516171819202122232425262728293031#include int main() { int n; int *arr; int input; int j,t = 0; scanf("%d",&n); arr.. 공감수 0 댓글수 0 2019. 2. 11.
2309)일곱난쟁이 https://www.acmicpc.net/problem/2309 9명의 난쟁이 중 7명이 진짜이고 진짜 난쟁이의 키 합이 100이다. 일단 싹 다 더하고 임의로 난쟁이 2명의 키를 빼줘서 100이 되는 경우를 찾으면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#includetypedef enum _BOOL { FALSE = 0, TRUE =1} BOOL; void swap(int *A, int *B) { int temp; temp = *A; *A = *B; *B = temp;} int partition(int *A.. 공감수 0 댓글수 0 2019. 2. 11.
2217)로프 https://www.acmicpc.net/problem/2217 각 로프마다 견딜 수 있는 최대 무게가 다르다. n 개의 로프가 무게가 w인 물체를 견딜 때, 각 로프에는 w/n만큼의 무게가 가해진다. 이때 로프들이 견딜 수 있는 최대 무게는 얼마일까? 모든 로프들을 사용한다면, 견딜 수 있는 무게가 가장 적은 로프에 맞춰져야 한다. 예를들어 각 로프들이 견딜 수 있는 무게가 A:10, B:15, C:20, D:30, E:40 이라고 하자. 모든 로프를 사용한다면 w/5를 가장 작은 무게를 견디는 A가 견뎌낼 수 있어야 한다. 만약 w가 60이라면 A에 12만큼의 무게가 가해져 이를 견딜 수 없다. 즉 w의 최대값은 A가 견딜 수 있는 무게인 10에서 5를 곱한 값이다. 여기서 Wmin= Wmax / .. 공감수 0 댓글수 0 2019. 2. 11.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.