개발조아

문제 링크 : https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net MST와 DFS로 풀이 했다. 첫번째 답은 모든 마을을 연결하는 최소 비용을 출력해야하므로 MST 로 구한다. 두번째 답은 마을과 마을 사이의 최단 경로 중 비용이 가장큰 경로 이므로 BFS나 다익스트라로 구하면 된다. MST는 크루스칼로 구현했다. MST를 구성하면서 BFS에서 사용할 그래프를 인접리스트로 저장했다. 인접리스트 중 길이가 1인 점에서만 BFS를 수행했다. 끝에서 ..

문제 링크 : https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net BFS로 풀이 했다. 문제를 정리하면 한붓 그리기를 위해선 붓을 맵에 놓아야하는데 이때 붓을 몇번 놓는지 구하면 된다. 내 풀이의 핵심은 도형의 크기를 두배 확장하는 것이다. 나는 BFS를 통해서 한붓그리기가 가능한지 판별한다. 근데 테두리가 겹치는 것만 한붓그리기가 가능하지만 BFS를 수행하면 동서남북으로 인접한 곳을 확인하게 된다. 그러면 사각형안에 사각형이 있는 경우고 가능하다고 판별하게 ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42894 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr 빡구현 문제였다. 구현한 기능이 많다보니 100줄이 넘어갔다. 처음부터 봐보자. 일단 사용가능한 블록이 12가지가 있다. 하지만 게임..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17676 = (다음 지점 시작시각) 이라면 현재지점의 종료시각에 다음 지점의 응답은 동시에 처리되는 것이다. 즉 아래처럼 되어 있는 것이다. ㅣ-------------ㅣ ㅣ----------------ㅣ 또한 다음 지점의 시작시각이 현재지점 종료시각 보다 크더라도 그 차이가 1초가 안된다면 1초 동안 함께 처리될 수 있는 요청이다. ㅣ----------ㅣ (간격 0.5초)ㅣ----------ㅣ 따라서 한 로그의 종료시각을 기준으로 그 다음 모든 로그에 대해서 위의 경우를 세주면 된다. 종료시각부터 1초 구간으로 잡아서 이전 로그는 볼필요가 없다. 주의 할점으 위의 두 경우가 아니라고 해서 반복문을 ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 조합으로 풀이했다. 후보키의 길이는 1,2,3,4,..최대 8까지다. 그러므로 속성중에서 1개,2개,3개 뽑는 경우의 모든 조합을 다 구해도 충분하다. 우선 후보키가 될 컬럼들을 뽑아 조합을 순서 조합을 만들자. 다음 뽑은 조..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr 백준에 비슷한 문제를 풀었던 적이 있어서 아이디어는 금방 떠올랐다. 백준 문제 링크 : https://www.acmicpc.net..

문제 링크 : https://www.acmicpc.net/problem/1553 1553번: 도미노 찾기 도미노의 크기는 1×2이고, 크기가 1×1인 칸으로 나누어져 있다. 칸은 수를 나타내며, 위와 같이 총 28가지가 있다. 크기가 8×7인 격자가 있고, 격자의 각 칸에는 정수가 하나씩 들어있다. 위의 도 www.acmicpc.net 도미노를 놓는 방향은 ㅡ ㅣ 두가지 모양밖에 없다. (0,0)부터 두 방향으로 묶어서 백트래킹으로 완탐해보자. 도미노를 (0,0)에서 (7,6)까지 순차적으로 확인하면 되므로 왼쪽이나 오른쪽을 향하도록 놓지 않아도 된다. 그래서 나는 처음에 오른쪽방향으로 도미노를 만들어 보고 다음 아래쪽 방향으로 도미노를 만들어 봤다. 이때 이미 사용한 도미노인지, 해당방향의 칸에 번호를..

문제 링크 : https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net MST와 BFS로 풀었다. 처음에는 단순하게 MST 구성해서 가중치 합 구하고 x,y의 간선 정보만을 보고 빼주면 될줄 알고 제출했더니 틀렸다. 당연하다. 문제는 두개의 점을 기준으로 두개의 MST를 만드는 것이다. 그래서 모든점을 포함하는 MST를 구성하고, 두 점을 기준으로 두개의 MST로 나누어야한다. 따라서 두 점 사이의 간선 중 가중치가 가장 큰 것을 빼주면 두개..