algorithm (135) 썸네일형 리스트형 백준 1926_그림(JAVA) www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net [문제 풀이] 깊이 우선 탐색을 이용하여 문제를 풀었습니다. 이 문제는 2차원 배열에 대한 정보가 주어지고 2차원 배열에서 1로 연결된 그림의 갯수가 최대 그림의 크기를 찾는 문제였습니다. 문제를 푼 방법은 배열을 순회하며 1이 시작되는 좌표를 찾고 깊이 우선으로 탐색하며 확인한 좌표들은 마킹을 해주는 식으로 풀었습니다. 코드 설명 입력으로 주어진 값을 받아 배열에 저장해주고 방문을 확인할 배열을 똑같이 선언해 줍니.. 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(Minimum Spanning Tree) Spnning Tree란? 사진 첨부 정의 그래프 내의 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 말합니다. 특징 Spanning Tree = 신장 트리 n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필역적으로 트리형태가 됩니다. 이를 Spanning Tree라 고 합니다. 즉 Spaaning Tree는 그래프에 있는 n개의 정점을 (n-1)개의 간선으로 연결한 트리입니다. 신장 트리를 구하는 방법은 여러가지 입니다. (Kruskal, Prim 등..) DFS, BFS를 이용하여 그래프에서 Spanning Tree를 찾을 수도 있습니다. Minimum Spa.. 백준 2583_영역 구하기(JAVA) www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net [문제 풀이] 너비 우선 탐색을 이용하여 문제를 풀었습니다. 이 문제는 사각형의 좌표가 주어 졌을 때 사각형 공간을 제외한 나머지 공간이 몇개로 나누어질 수 있는지에 대해 찾는 문제였습니다. 문제를 풀기 위해 2차원 배열에 사각형이 차지하고 있는 부분을 먼저 적은 후 2차원 배열을 순회하면서 체크 되지 않은 부분이 있다면 BFS를 통해 영역을 구해 주었습니다. 코드 설명 입력으로 주어진 값을.. 프로그래머스_기능개발(C++, JAVA) programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr [문제 풀이] queue을 이용하여 문제를 풀었습니다. 이 문제는 함께 배포될 수 있는 작업의 수를 각각 구하는 문제입니다. 작업이 배포되기 위해서는 아래의 조건을 만족하여야 합니다. 진행 중인 작업 + 작업 속도 * 작업일 >= 100을 만족해야 합니다. 완료되지 않은 작업이 앞에 존재하지 않아야 합니다. 완료된 작업 중 배포되지 않은 작업이 뒤이어 존재한다면(연속적.. 프로그래머스_베스트앨범(C++, JAVA) programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr [문제 풀이] map을 이용하여 문제를 풀었습니다. 이 문제는 아래의 조건을 만족하는 값을 찾는 것입니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 주의할 점은 같은 장르 안에서는 최대 2개까지만 선택할 수 있다는 것입니다. 예를.. 프로그래머스_전화번호 목록(C++, JAVA) programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr [문제 풀이] set을 이용하여 문제를 풀었습니다. 이 문제는 전화번호 목록 중에 접두어로써 존재하는 번호가 있는지를 찾는 문제입니다. 짧은 시간 안에 번호의 존재를 찾기 위해 set을 이용하여 전화번호 목록을 저장하였고 전화번호 리스트를 순회하며 길이가 N인 번호에 대해 0 ~N까지의 번호 중 set에 존재하는 번호가 있는지 찾아주었습니다. [C++] #include #.. 프로그래머스_완주하지 못한 선수(C++, java) programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr [문제 풀이] map을 이용하여 문제를 풀었습니다. 이 문제는 마라톤에 참여한 선수 중에 완주를 하지 못한 지원자를 찾는 문제입니다. 지원자 중에 동명이인이 존재 할 수도 있습니다. 문제를 푸는 방식은 입력으로 주어진 competition 벡터를 map에 넣어 이름들을 세어줍니다. 그 후 participant 백터를 순회하며 존재하면 빼주고 map에 존재하.. 프로그래머스_주식가격(C++, JAVA) programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr [C++] #include #include using namespace std; vector solution(vector prices) { vector answer; for(int i = 0; i < prices.size(); i++){ int cnt = 0; for(int j = i + 1; j < prices.size(); j++).. 이전 1 2 3 4 5 6 7 8 ··· 17 다음
