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.. 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에 접근한 .. 1012)유기농 배추2(DFS) https://www.acmicpc.net/problem/1012 삼성 역테 준비할 겸 DFS 배우고 관련 문제 조지려 한다. 이 문제를 처음 풀었을 때 내가 문제를 푼 방식이 DFS인 줄도 모르고 풀었다. FM DFS와는 차이가 있긴 했지만 DFS의 변형인 것은 분명했다. 원래 DFS는 연결 그래프를 빠짐 없이 방문하는 순회 알고리즘이다. 그러나 DFS는 그래프만 다룰 수 있는 것이 아니라 배열도 순회할 수 있다. 그래프의 관점에서 배열을 바라보는 것이다. 2차원 배열의 격자 공간 하나하나가 노드이고 인접한 방끼리 연결되어있다 생각하면 편하다. 그렇다고 해서 배열의 방 갯수만큼 인접리스트나 인접행렬을 만드는 것은 좋은 방법이 아니다. 예를들어 4x4 배열을 DFS로 순회할 때 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번 컴퓨터로 보내.. 3208)배고픈 애벌레 https://www.acmicpc.net/problem/3208 처음 이 문제를 접했을 때 시계 방향으로 배열을 순회해야 한다고 생각했다. 그래서 배열을 시계방향으로 순회하며 안쪽으로 파고드는 함수를 만들었다. 그리고 방향이 바뀌는 지점에서 수를 세도록 재귀 함수를 만들었다. 내가 기대한대로 재귀 함수가 동작하지 않았는데 재귀 함수에 대한 이해가 부족한 듯하다. 친구에게서 보다 쉽고 신박한 풀이를 듣게되어 복습겸 글로 남긴다. 애벌레가 배열을 시계방향으로 순회할 때 그려지는 경로에 규칙이 숨어있다. 배열의 크기가 주어질 때 C(열 길이)가 R(행 길이)보다 큰 경우를 생각해보자. R> C; if (R > C) { cout 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.. 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에 접근하고 .. 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 이전 1 2 3 4 ··· 11 다음
