큐

난이도 : Level 2유형 : 큐 / 구현 / 시뮬레이션구현 시간 : 30분링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   문제 풀이우선 해당 문제는 문제에 대한 설명이 부족하다.예제를 보면 추측이 가능한데 아래 2가지 조건을 추가해야 한다.트럭은 1초에 1씩 전진한다.트럭은 1초에 1대씩 다리에 올라갈 수 있다. 1. Queue 자료구조를 사용해서 다리 위 트럭 객체를 관리2. currentWeight, idx, time 변수를 통해 현재 다리 위 무게, 시간, 대기 트럭의 ..

난이도 : 골드 3유형 : 위상 정렬 / 동적 계획법링크 : https://www.acmicpc.net/problem/1005구현 시간 : 1시간 (못품)        문제풀이위상 정렬 알고리즘을 공부하고 나서 처음으로 풀어본 문제이다. 노드의 방문 순서를 구현하는건 쉬웠지만, 특정 건물마다 필요한 최대 시간을 구하는 방법을 생각해내지 못했다 ㅜ indegree[] 배열을 이용해 노드의 진입 차수를 저장하고, 방문마다 해당 노드의 진입 차수를 차감하여 위상 정렬을 구현했다. BFS에서 탐색 레벨마다 날짜를 계산했었던 토마토 문제가 기억이 나서 위상 정렬에도 반복마다 최대 시간을 누적하는 방식으로 최대 시간을 저장했다. 하지만 이 방법은 이전 단계에서 소요된 시간을 다음 단계에 반영하지 못하므로, 특정 노..

너비 우선 탐색(BFS, Breadth-First Search)BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. BFS는 최단 경로를 찾는 알고리즘으로도 많이 쓰이곤 하는데, 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다. 쉽게 말해 문제에 대한 답이 많은 경우 너비 우선 탐색은 이 답 중에서도 가장 가까운 답을 찾을 때 유용하다. BFS는 주로 FIFO(선입선출) 방식인 큐 자료구조를 사용하여 구현한다.인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.(DFS는 이와 반대로 스택을 통해 구현한다.) BFS 작동 원..

난이도 : 골드 5유형 : BFS / 큐링크 : https://www.acmicpc.net/problem/7569구현 시간 : 1시간       문제풀이토마토 박스를 3차원 배열에 저장한다.1번 과정에서 빈칸의 개수, 익은 토마토의 개수를 저장한다.(총 배열의 크기 - 빈칸의 개수) 가 익은 토마토의 개수와 같다면 0 을 출력하고 종료한다.익은 토마토가 있는 좌표를 Queue에 저장한다.Queue 가 비어있지 않을때까지 반복문 시작Queue의 현재 size 를 저장하고, size 만큼 for문을 돌린다. (BFS 탐색의 Depth를 기준으로 하루가 지남을 판별하기 위함)Queue에서 poll한 익은 토마토의 위치 기준 상하좌우아래위 6방향으로 탐색한다.만약 탐색 위치가 박스 위치를 벗어나면, 다음 방향으..

난이도 : Level 3유형 : BFS / 큐구현 시간 : 1시간 (못품)링크: https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr      문제풀이위 문제는 2020 카카오 인턴십 코딩 테스트에 출제된 문제로 현재까지 풀어본 BFS 문제와는 다르게 생각이 많이 필요했다.최단 경로를 구한다고 하더라도 그 경로가 가장 저렴한 비용이 들지 않기 때문에 최소 비용을 저장해서 문제를 구현했다.  x, y 좌표 및 방향 정보를 저장하는 cost 배열을 사용해서 시작점을 제외한 모든 데이터를 최대값으로 저..

난이도 : Level 2유형 : BFS / 큐구현 시간 : 30분링크 :https://school.programmers.co.kr/learn/courses/30/lessons/159993  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr      문제풀이위 문제는 BFS 탐색 알고리즘을 사용하여 최단 경로를 찾는 문제이다. 앞서 백준을 통해 BFS / DFS 문제를 많이 연습해두었기에 알고리즘을 구현하는 것은 오래 걸리지 않았지만 BFS 를 총 2번 실행하는 과정에서 데이터 초기화에 문제를 겪었다. 시작점, 레버, 도착지의 위치 정보 저장시작점 -> 레버까지 최단 경로를 BFS 를 통해 구함만약 레버까지..

난이도 : 골드 4유형 : 구현 / 시뮬레이션 / 큐링크 : https://www.acmicpc.net/problem/3190구현 시간 : 1시간   문제풀이앞서 풀었던 시뮬레이션 / 구현 문제인 로봇 청소기보다 구현하는데 오랜 시간이 걸린 것 같다. 뱀의 길이는 조건에 따라 늘어나고, 늘어나는 뱀의 몸을 저장할 자료구조를 생각하는게 특히 고민할 부분이였던 것 같다. [BOJ] 14503번 로봇 청소기 - JAVA[자바]난이도 : 골드 5유형 : 구현 / 시뮬레이션링크 : https://www.acmicpc.net/problem/14503      문제풀이로봇 청소기의 규칙대로 알고리즘을 차례대로 구현했다.구현에  대한 고민은 크게 어렵지 않았다tenaciously.tistory.com 보드(룸)의 크기..