본문 바로가기

CPP

 (51)
[C++/PGS] Lv.3 : 네트워크 (DFS/BFS) 깊이/너비 우선 탐색(DFS/BFS) : 네트워크 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터..
[C++/PGS] Lv.2 : 타겟 넘버 (DFS) 깊이/너비 우선 탐색(DFS/BFS) : 타겟 넘버 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 ..
[C++/PGS] Lv.2 : 게임 맵 최단거리 (BFS) 깊이/너비 우선 탐색(DFS/BFS) : 게임 맵 최단거리 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 ..
[C++/BOJ] 2149 : 암호 해독 문제 어떤 문장을 키를 이용하여 다음과 같이 암호화하려 한다. 암호화하기 전의 문장을 평문이라 하며, 암호화 된 문장은 암호문이라고 한다. 키, 평문, 암호문은 모두 영어 대문자로 된 공백 없는 문장이다. 키의 길이를 N이라고 했을 때, 우선 평문을 N 글자씩 잘라서 다음과 같이 나열한다. 예를 들어 평문이 MEETMEBYTHEOLDOAKTREENTH 이고, 키가 BATBOY라고 해 보자. 제일 윗줄은 이해를 돕기 위해 키를 다시 한 번 쓴 것이다. 이제 이 행렬(배열)을 열(Column) 단위로 정렬을 하는데, 정렬을 하는 키준은 키의 문자로 한다. 즉 BATBOY를 정렬하여 ABBOTY와 같이 정렬하는 것이다. B와 같이 여러 번 나타나는 문자의 경우에는 원래의 행렬에서 더 왼쪽에 있었던 것을 먼저 ..
[C++/BOJ] 2293 : 동전 1 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 백준 골드 5 문제! 백트래킹이나 완탐 문제일 줄 알았는데 알고보니 dp였다.... 0원인 경우의 수는 1이다. dp[0] = 1; 1원이 가능한 경우의 수는 1원..
[코드트리] BFS 탐색 / 갈 수 있는 곳들 갈 수 있는 곳들 숫자 0, 1로만 이루어진 n * n 격자가 주어졌을 때, k개의 시작점으로부터 상하좌우 인접한 곳으로만 이동하여 도달 가능한 칸의 수를 구하는 프로그램을 작성해보세요. 숫자 0은 해당 칸이 이동할 수 있는 곳임을, 숫자 1은 해당 칸이 이동할 수 없는 곳임을 의미합니다. 입력 형식 첫 번째 줄에는 격자의 크기를 나타내는 n과 시작점의 수를 나타내는 k 값이 공백을 사이에 두고 주어집니다. 두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 순서대로 공백을 사이에 두고 주어집니다. 그 다음 줄 부터는 k개의 줄에 걸쳐 각 시작점의 위치 (r, c)가 공백을 사이에 두고 주어집니다. (r, c)는 r행 c열 위치가 시작점 중 하나임을 의미합니다. 모든 시작점의 위치에 적..
[코드트리] BFS 탐색 / 네 방향 탈출 가능 여부 판별하기 네 방향 탈출 가능 여부 판별하기 n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 상하좌우에 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 과 같이 뱀이 배치 되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이 때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요. 입력 형식 첫번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두번째 줄부터 (n+1)번째 줄까지는 각 행에 뱀이 없는 경우 1, 뱀이 있는 경우 0이 입력으로 공백을 사이에 두고 주어집니다. 시작 칸과 끝 칸에는 뱀이 주어지지 않는다고 가정해도 좋습니다. 2 ≤ n..
[코드트리] 완전탐색 / 자리 수 단위로 완탐 연습문제 5개의 숫자 [1, 5, 2, 6, 8]이 주어졌을 때 이 중 단 하나의 숫자만 두 배로 해서, 인접한 숫자간의 차이의 합이 최대가 되도록 해보세요. 위 문제는 단순하게, 모든 위치의 숫자를 2배씩 해보는 완전탐색을 진행해 볼 수 있습니다. 1. 첫 번째 숫자 1에 2배를 하는 경우 [2, 5, 2, 6, 8]이 되므로, 인접한 숫자간의 차이의 합은 3 + 3 + 4 + 2 = 12가 됩니다. 2. 두 번째 숫자 5에 2배를 하는 경우 [1, 10, 2, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 9 + 8 + 4 + 2 = 23이 됩니다. 3. 세 번째 숫자 2에 2배를 하는 경우 [1, 5, 4, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 4 + 1 + 2 + 2 = 9가 됩..
728x90

티스토리툴바