목록알고리즘 문제 풀이/BOJ 문제 풀이 (32)
굥뷰를 햡시댜
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이전에 풀었던 N과 M(1)과 같은 문제입니다. 입력만 늘어났지 예시를 보시면 순열 문제라는 것을 금방 파악할 수 있습니다. (잘 모르시겠다면 이전 게시물(N과 M(1)문제)을 참고해주세요) 풀이 과정은 다음과 같습니다. 1. 입력을 받고 vec이라는 벡터에도 입력값을 넣어줍니다. 2. vec을 정렬합니다. 3. dfs와 백트래킹으로 모든 순열을 구해줍니다. #define _CRT_SEC..
https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 중복 조합 문제 입니다. 중복 조합이란? -> 서로 다른 n개에서 r개를 순서에 상관 없이 뽑는데 중복을 허용해서 뽑는 경우의 수를 말합니다. 쉽게 예로 들어보겠습니다. n = 4, r = 2이고 모집합이 {1,2,3,4}일 때 순서에 상관 없이 중복을 허용해서 뽑는 경우의 수를 찾아본다면 (1,1), (1,2), (1,3), (1,4) (2,2), (2,3), (2,4) (3,3), ..
https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 중복순열 문제입니다. 중복순열이란? 순열인데 중복의 경우도 고려하는 순열입니다. 다시 말하자면, 서로 다른 n개에서 r개를 중복을 허용하여 순서에 상관있게 나열하는 것을 말합니다! 바로 예로 들어보겠습니다. n = 4, r = 2이고 모집합이 {1,2,3,4}인 경우를 고려해봅시다. 원래 순열이라면 (1,2), (1,3), (1,4) (2,1), (2,3), (2,4) (3,1), (3..
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 조합 문제입니다. 이전 게시물에서 말했다시피, 순열이란 서로 다른 n개에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 말합니다. 하지만 조합의 경우에는 어떨까요? 이미 중학교, 고등학교 과정에서 배웠던 것과 같습니다! 조합은, 서로 다른 n개에서 순서에 상관 없이 r개를 뽑는 경우의 수를 말합니다. 여기서 순서에 상관 없다는 것은 뽑힌 순서가 다르더라도 내용물(원소)만 같다면 ..
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 순열 문제입니다. 먼저, 순열은 서로 다른 n개에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 말합니다. 여기서 순서에 상관있게 나열한다(?) 라는 것은 순서만 다르면 다른 녀석들로 구분한다는 것입니다. 예를 들어, {1,2,3,4} 4개의 원소가 있는 집합에서 2개를 중복없이 고른다고 가정합시다. (1,2), (1,3), (1,4) (2,1), (2,3), (2,4) (3,1..
https://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩 www.acmicpc.net 빡구현 bfs, dfs 문제를 찾던 도중 난이도가 가장 낮아 보여서 선택한 문제 생각보다 어려웠고 시간이 오래걸렸다 ㅠㅠ 결국 질문검색 게시판..
https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 www.acmicpc.net 구현이 빡센 BFS 문제를 풀어보고 싶어 문제집을 찾던 도중 제일 난이도가 쉬워보이는 문제를 찾았다. 그냥 BFS로 빡구현했고 내가 문제를 푸..
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이번 9월 삼성 A형 역량테스트 복기된 문제로 난이도는 이제껏 풀었던 A형 문제중 어려운 문제에 속한것 같다. 지난번 게리맨더링 문제도 난이도가 꽤 높았고 이번 문제도 꽤 높은걸 보니 이제는 출제자 측에서도 지원자들이 상향평준화 되었다는걸 알아서 올해 하반기 지원자들의 수준을 테스트해보기 위해 삼성 역량테스트 전에 문제의 난이도를 조금 올린듯 하다. 이번 문제를 풀 때는 BF..