본문 바로가기

<알고리즘 문제풀이&연습>/[C++] 백준68

[백준 2501] 약수 구하기 안녕하세요. BlockDMask 입니다.오늘도 간단하게 전체 탐색법을 이용하여 약수를 구하는 문제를 풀어보았습니다.0. 제목백준 2501 약수 구하기BOJ 2501 약수 구하기1. 문제 설명 약수란어떤 자연수 a, b 가 있을때a를 b로 나누었을때 나머지가 0 이면 b는 a의 약수라 한다. 12 를 예로 들자면 12 / 1 = 12 ---> 012 / 2 = 6 ---> 012 / 3 = 4 ---> 012 / 4 = 3 ---> 012 / 5 = 2 ---> 212 / 6 = 2 ---> 012 / 7 = 1 ---> 512 / 8 = 1 ---> 412 / 9 = 1 ---> 312 / 10 = 1 ---> 212 / 11 = 1 ---> 112 / 12 = 1 ---> 0 12 의 약수는 1, 2,.. 2017. 10. 17.
[백준 9506] 약수들의 합 안녕하세요. BlockDMask 입니다.조금 간단한 문제를 풀어보았습니다.약수들의 합을 구하는 문제 입니다. 170907 문제 빼먹음 -> 171016 완료0. 제목백준 9506 약수들의 합BOJ 9506 약수들의 합1. 문제 설명 n의 범위가 (2 < n < 100,000)인 어떤 수 n에 대해 숫자 n이 자신을 제외한 약수들의 합으로 나타내어 지면, 그 수를 '완벽한 수'라고 한다. 예를 들으 6은 6 = 1 + 2+ 3 이므로 완벽한 수이다. n이 완벽한 수 인지 아닌지 판단해주는 프로그램을 작성하면 됩니다. -- 입력 --테스트 케이스마다 한 줄 간격으로 n 이 주어집니다. 입력이 마지막엔 -1 이 주어집니다. -- 출력 --테스트케이스 마다 한줄에 하나씩 출력해야합니다.n이 완벽한 수라면, n .. 2017. 10. 16.
[백준 2178] 미로탐색 (BFS-너비우선탐색) 안녕하세요. BlockDMask 입니다.오늘은 BFS algorithm 기반으로 미로탐색 문제를 풀어보았습니다.0. 제목백준 2178 미로탐색(BFS-너비우선탐색)BOJ 2178 MAZE(BFS-너비우선탐색)1. 문제 설명 N x M 크기의 배열로 표현되는 미로가 있습니다. 4x6 예시.[101111][101010][101011][111011] 미로에서 1은 이동할 수 있는 칸을 나타내고 0은 이동할 수 없는 칸을 나타냅니다. 이러한 미로가 주어졌을 때 [0,0] 에서 출발하여 배열기준 [N-1, M-1] 의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 구현하면 됩니다. 입력 : 첫째 줄에 두 정수 N, M (2 지나간 길을 알릴 뿐만 아니라 몇번째에 왔는지 숫자를 기록하면서 이동해야.. 2017. 10. 16.
[백준 9663] N-Queen(DFS 깊이우선탐색) 안녕하세요 BlockDMask 입니다.오늘은 다들 학교에서 한번쯤 들어본 N-Queen 체스 문제를 풀어보았습니다.은근 신경써야 하는 부분이 많더군요;;;;0. 제목백준 9663 N-Queen (DFS)BOJ 9663 N-Queen (DFS)1. 문제 설명N-Queen 문제는 체스판 크기가 N x N 인 체스판 위에 퀸 N개를 서로 공격하지 못하도록 배치하는 총 방법의 수를 구하는 프로그램을 작성하는 문제입니다.정수 n이 입력으로 들어옵니다. (1 그 다음 행에서 위의 행의 퀸과 일치 하지 않는 맨 왼쪽 열에 퀸을 놓습니다. -> n 번째 열까지 도달한다면 전체 count 를 하나 더합니다. -> 그렇지 않다면 다시 백트랙킹합니다. 배열 arr은 열의 개수 를 뜻합니다.같은 열(세로)라인에 Queen이 .. 2017. 10. 15.
[백준 2667] 단지번호붙이기(BFS-너비우선탐색) 안녕하세요 BlockDMask 입니다. 171011 일자 문제 입니다.포스팅을 늦게 했네요;;이번시간엔 단지번호 붙이기를 BFS 방식으로 풀어보았습니다.단지 번호 붙이기 DFS 방식으로 푼 포스트는 [여기] 있습니다.0. 제목백준 2667 단지 번호 붙이기BOJ 2667 단지 번호 붙이기1. 문제 설명 과 같이 정사각형(5 2017. 10. 15.
[백준 2667] 단지번호붙이기(DFS-깊이우선탐색) 안녕하세요. BlockDMask 입니다.날이 갑자기 추워졌네요;; 다들 ;; 옷 따숩게 입으시길;;오늘자 문제 시작하겠습니다.이번 포스트는 단지번호 붙이기를 DFS 방식으로 풀었습니다.단지번호 붙이기 BFS 방식으로 푼 글은 [여기] 있습니다.0. 제목백준 2667 단지 번호 붙이기BOJ 2667 단지 번호 붙이기1. 문제 설명 과 같이 정사각형(5 2017. 10. 12.
[백준 1764] 듣보잡 안녕하세요. BlockDMask 입니다.연휴도 끝났고;; 많이 쉬었네요;; ㅠㅠ오늘의 문제 풀어보겠습니다.0. 제목백준 1764 듣보잡BOJ 1764 듣보잡문제 이름이 참.. 듣보잡이라니 ㅎㅎ 1. 문제 설명 듣지도 못한 사람의 명단과, 보지도 못한 사람의 명단이 주어질 때, 듣지도 보지도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 -- 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄 부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터는 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M 은 500,000 이하의 자연수이다. 출력 -- 듣보잡의 수와 그 명단.. 2017. 10. 10.
[백준 1920] 수 찾기 (이진탐색) 안녕하세요. BlockDMask 입니다. 오늘은 '수 찾기' 라는 문제를 풀어보았습니다.음..은근히 생각을 하게 하는 문제였습니다. '시간초과' 때문에;; ㅎㅎ 170906 문제 빼먹음 -> 171008 완료0. 제목백준 1920 수 찾기 (이진탐색)BOJ 1920 수 찾기 (Binary Search)1. 문제설명 N개의 정수 A[1], A[2], A[3], A[4], ..., A[N-2], A[N-1], A[N] 이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 구현하면 됩니다. 입력 -- 첫째 줄에 자연수 N(1 2017. 10. 8.
[백준 2562] 최대값 안녕하세요. BlockDMask 입니다.오늘의 문제 풀어보겠습니다. 170905 문제 빼먹음 -> 171008 완료0. 제목백준 2562 최대값BOJ 2562 최대값1. 문제 설명 9개의 서로 다른 자연수가 주어질 때, 이들 중 최대값을 찾고 그 최대값이 몇 번째 수인지 구하는 프로그램을 만들면 됩니다. 예를들어, 서로 다른 9개의 자연수 3, 29, 30, 12, 55, 80, 9, 92, 60 이 주어지면, 이들 중 최대값은 92 이고 이 값은 8번째 수 입니다. 주어지는 자연수의 크기는 100보다 작습니다. 2. 풀이 과정 배열에 각 수를 저장한 후 선형탐색을 이용하여 배열 전체를 탐색하는 방법으로, 최대값을 구하는 방식으로 풀면 됩니다. 3. 코드 123456789101112131415161718.. 2017. 10. 8.
[백준 2309] 일곱 난쟁이 (브루트 포스) 안녕하세요. BlockDMask 입니다.오늘은 백준 온라인 저지에 단계별로 풀어보기 중 브루트 포스 카테고리에 있는 문제를 풀어보았습니다.170904 문제 빼먹음 -> 171006 완료 0. 문제백준 2309 일곱 난쟁이 (브루트 포스)BOJ 2309 일곱 난쟁이 (brute force)**Brute Force(브루트 포스)란 : 무식하게 푼다, 가능한 방법을 전부 만들어 보는 알고리즘, 완전탐색(exhaustive search)라고도 합니다. 1. 문제설명 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. (백설공.. 2017. 10. 6.