Algorithm
-
백준 2667 단지번호붙히기Algorithm/BOJ(백준) 2018. 9. 30. 20:30
문제 링크 : https://www.acmicpc.net/problem/2667※선행해야 할 알고리즘 : BFS/DFS Algorithm : BFS/DFS 를 활용하여 군집을 찾아 군집의 개수와 군집의 원소 개수를 오름차순으로 출력해라 1. 지도를 입력 후, 지도에서 1이 입력된 인덱스를 찾아 반환한다. 2. 반환된 인덱스를 기준으로 아래, 왼쪽, 오른쪽을 BFS하며 count 한다. 이 때, 1을 찾아 방문을 했기에 count의 초기값은 1이다. 또한 방문한 곳들은 지도를 0으로 설정하여 다시 들리지 못하게 한다. 3. 해당 count를 vector에 삽입하고, 1~3을 지도에 1이 더 이상 없을 때까지 반복한다. 예를 들어, 입력 예제 본다면701101000110101111010100001110100..
-
백준 7576 토마토Algorithm/BOJ(백준) 2018. 9. 30. 19:26
문제 링크 : https://www.acmicpc.net/problem/7576※선행해야 할 알고리즘 : BFS/DFS Algorithm : BFS/DFS 를 활용하여 행렬에서 -1을 제외한 모든 0을 1로 만들 때 걸리는 최단 횟수를 구하여라. (단, 모든 0을 1로 만들지 못할 시엔 -1 출력) 1. 토마토가 익은 index를 입력 시, 1일 때 바로 queue에 삽입한다.BFS를 실행할 시, 토마토가 익은 구간을 queue에 삽입하여야 한다. 이 때, 모든 index를 입력 후에 1을 찾게 된다면 n*m만큼의 시간복잡도가 추가되기에 복잡도 단축을 위해 입력하면서 바로 queue에 삽입할 수 있도록 한다. 2. 또한, visit 배열을 초기화 할 때 모두 false로 처리하는 것이 아니고 queue에..
-
백준 1697 숨바꼭질Algorithm/BOJ(백준) 2018. 9. 28. 23:49
문제 링크 : https://www.acmicpc.net/problem/4354※선행해야 할 알고리즘 : BFS, DFS Algorithm : N에서 K까지 갈 때 count를 센다. 1. 미로찾기로 따지면 N이 시작점, K가 출구가 된다. 즉, 현재 위치값을 순간이동(*2), 오른쪽(+1), 왼쪽(-1)을 통해 바꿔가며 찾는다. 즉, 입력 예제를 통해 본다면 1 2 3 4 5 6 7 8 9 1011 12 13 14 1516 17 18 19 20 빨간색은 시작점 -> 노란색은 이동거리 -> 파란색은 도착점 이 되는 것이다. 2. queue를 활용하여 BFS를 진행하면 다음과 같다. //kuklife.tistory.com #include#include#include#includeusing namespace..
-
[2018 상반기 카카오 블라인드 채용 1차] 프로그래머스 카카오 뉴스 클러스터링(난이도 중)Algorithm/대회 및 기타 2018. 9. 20. 22:38
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17677※ 추천 선행 알고리즘 : string 기본 함수들 문제 설명뉴스 클러스터링여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 카카오 신입 개발자 공채 관련 기사를 검색해보았다.카카오 첫 공채..'블라인드' 방식 채용카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용카카오, 블라인드 전형으로 신입 개발자 공채카카..
-
[2018 상반기 카카오 블라인드 채용 1차] 프로그래머스 카카오 프렌즈4블록(난이도 상)Algorithm/대회 및 기타 2018. 9. 19. 19:04
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17679※ 추천 선행 알고리즘 : 우선 탐색, DP 문제 설명프렌즈4블록블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. 만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 ..