코딩 공부하는 코딩류

지도에 표시되어 있는 섬의 개수를 세는 문제 문제의 조건 1. h의 높이 x w의 너비 크기를 가진 지도가 주어진다. 2. 2차원 지도 배열에는 0과 1로 표시가 되어 있다. 0은 바다, 1은 땅이라는 뜻 3. 2차원 배열의 각 땅들은 상하좌우 대각선으로 연결되면 하나의 섬이라고 할 수 있다. 4. 여러 테스트 케이스가 주어질 때 각 테스트 케이스의 섬의 갯수를 구해서 출력하기 5. 입력의 마지막 줄에는 0 0 이 주어진다. 입력받은 w와 h가 둘 다 0이라면 테스트 케이스 입력받기 종료하고 프로그램도 종료 풀이 과정 BFS로 상하좌우에 연속되어 있는 같은 숫자 갯수 세던 문제에서 대각선 방향만 추가해서 풀면 될 거 같아서 기존 BFS 코드에 대각선 방향만 추가해서 풀었습니다. 1. 방향 확인용 배열에 ..

가장 마지막 마을까지 가는데 필요한 최소 주유 금액을 구하는 문제 문제의 조건 1. 도시의 개수 N이 주어진다. 도시들은 일직선상에 있기 때문에 무조건 맨 앞 도시부터 차례대로 가야 한다. 2. 처음엔 차에 기름이 없기 때문에 맨 처음 도시에서 기름을 넣고 출발해야 한다. 기름통의 크기에는 제한이 없다. 도시 간 도로를 이용하여 이동할 때 1km당 1리터를 사용한다. 3. 각 도시에는 주유소가 하나씩 있으며 각 도시마다 기름 가격이 다를 수 있다. 그렇기 때문에 다른 도시보다 기름 가격이 싼 도시에서 최대한 넣고 가는 것이 이득이다. 4. 각 도시에 있는 주유소의 리터당 기름 가격과 각 도시 간 거리가 주어질 때 마지막 도시까지 가는데 필요한 최소 주유 금액을 구해서 출력하기 풀이 과정 처음엔 기름이 없..

방향이 없는 연결 그래프에서 서로서로 연결된 덩어리가 몇 개인지 구하는 문제 문제의 조건 1. 첫째 줄에 N개의 정점을 가진 양방향 연결 그래프와 M개의 간선이 주어진다. 2. 둘째 줄부터 간선의 양 끝점이 주어진다. 3. 서로 연결된 요소가 몇 개인지 출력 풀이 과정 앞전에 풀었던 컴퓨터 바이러스 문제처럼 몇 개의 정점이 간선을 통해 서로 연결되어 있는지 확인하면 될 거라고 생각했습니다. 연결 요소라는 말이 헷갈렸는데 질문 게시판 보니까 컴퓨터 바이러스 문제처럼 간선으로 서로서로 연결된 것들을 한 덩어리로 치는 것이 맞더라고요. 풀이 1. 양방향 그래프를 만든 뒤 BFS로 현재 정점에서 방문할 수 있는 곳들을 모두 방문한다. 2. 1번 과정이 끝나고 나면 한 연결 요소(덩어리) 탐색이 끝난 것이기 때문..

자연수 N개의 수들의 합 S를 만들 수 있는 수들 중 N의 최댓값을 구하는 문제 문제의 조건 1. 수들의 합 S가 주어진다. 2. 자연수 N의 최댓값을 출력한다. 풀이 과정 첨 봤을 땐 뭐 이런 문제가 있나... 했는데 누적합계를 구하면서 나오는 최댓값을 구하면 되나 싶어서 누적합계를 구해 봤습니다. 근데 애매하게 틀린 숫자가 나오고 문제 자체도 이해가 잘 안 가서 힌트를 찾아봤습니다. 문제 이해 후 정리된 풀이 1. 누적합계를 구하는 방식으로 접근하는 것은 맞다. 2. 하지만 모든 수가 연속된 숫자일 필요는 없다. S = 5 라면 [1,1,1,1,1] 로도 5를 만들 수 있다. 이 경우엔 N개의 자연수 중 최댓값은 1이라고 할 수 있지만 유일하게 1만 있는 것이 아니다. 5를 만들기 위해서 1을 다섯번..

배추밭에 필요한 배추흰지렁이의 최소 갯수를 구하는 문제 문제의 조건 1. 배추를 해충으로부터 보호하기 위해 배추밭에 배추흰지렁이를 놓을 것이다. 2. 지렁이는 상하좌우에 인접한 배추에게 이동할 수 있다. 3. 배추는 한 번에 많이 몰려있지 않고 밭 전체에 퍼져서 심어져 있다. 아파트 단지처럼 배추도 단지별로 심어져 있음 4. 필요한 지렁이의 최소 갯수 구해서 출력하기 5. 테스트 케이스가 여러 개 주어질 수 있다. 풀이 과정 1. BFS로 배추밭을 탐색하는데 전체 밭을 탐색해야 하기 때문에 2중 for문으로 [0, 0]번째부터 탐색한다. 2. 배추 한 칸을 대상으로 상하좌우에 또 배추가 있는지 검사해서 연결된 배추가 있으면 다음에 방문할 큐에 추가 3. 하나의 배추 단지 검사가 끝나고 나면 정답 카운트를..

진영 주식회사의 신입 사원 선발을 도와주는 문제 문제의 조건 1. 진영 주식회사는 신입 사원 지원자들의 서류 점수와 면접 점수를 매겼다. 2. 진영 주식회사에서 신입 사원을 선발하는 기준은 어떤 지원자가 다른 지원자보다 적어도 한 가지는 더 높은 순위를 받아야 한다는 것이다. 서류 점수라도 더 높던가 면접 점수라도 더 높던가 그렇지 않고 둘 다 다른 지원자보다 낮으면 탈락 3. 테스트 케이스가 여러 개 주어질 때 각 케이스별로 최대한 많이 선발할 수 있는 신입 사원의 수를 구해서 출력하기 풀이 과정 처음엔 서류 점수를 기준으로 오름차순 정렬을 하면 되겠다 까지는 생각을 했는데 그 뒤로 비교 조건을 어떻게 해야할 지 감이 잘 안 와서 힌트를 봤습니다. 과정 1. 지원자들의 점수를 pair 구조체를 이용해서..

전자레인지 버튼을 몇 번 누르면 가장 적은 횟수로 T초를 정확하게 맞출 수 있는지 구하는 문제 문제의 조건 1. 전자레인지에 데울 냉동식품의 조리시간 T가 주어진다. 2. 전자레인지에는 A, B, C 버튼 세 개가 있다. 각 버튼을 누르면 5분, 1분, 10초 타이머가 설정된다. 3. 세 버튼만 이용해서 정확하게 T초를 맞춰야 한다. 4. 세 버튼을 이용한 횟수를 모두 출력하는데 누른 적 없는 버튼은 0 출력하면 된다. 만약 정확하게 T초를 만들 수 없으면 -1만 출력한다. 풀이 과정 전형적인 그리디 문제입니다. 출처에 초등부라고 되 있길래 초딩들도 푸는데 혹시 못 푸면 어쩌지..^^;; 했는데 다행히 통과했습니다. 과정 1. 전자레인지 버튼들에 지정된 시간을 저장할 배열과 각 버튼을 누른 횟수를 저장할..

서로 연결되어 있는 컴퓨터 중에서 바이러스에 감염된 컴퓨터가 몇 개인지 구하는 문제 문제의 조건 1. 컴퓨터의 갯수 N, 서로 연결된 쌍 M개가 주어진다. 2. 1번 컴퓨터는 바이러스에 걸렸는데 이 바이러스는 네트워크를 통해서 전파된다. 3. 1번 컴퓨터부터 시작해서 서로서로 연결되어 있는 컴퓨터들은 연결된 컴퓨터에게서 바이러스가 옮았다. 4. N개의 컴퓨터 중에서 1번 컴퓨터를 빼고 몇 개의 컴퓨터가 바이러스에 걸렸는지 출력 풀이 과정 쉽게 생각하고 시작했는데 생각보다 오래 걸린 문제 ㅠ.ㅠ 아직 dfs/bfs가 완벽하지 않아서 그런가 봅니다. 단순하게 모든 정점을 탐색하는 코드는 쉽게 짤 수 있지만 조금만 응용되어 나오면 방문할 필요가 없는 정점을 어떻게 거르나 고민하면서 시간을 많이 썼습니다. 풀이..