목차 문제 해석 핵심 조건 코드 구현 풀고 난 후 오답노트 https://www.acmicpc.net/problem/15683 문제 해석 N x M 직사각형, 총 K개 CCTV 5종류 1: 한 방향 2: 반대 두 방향 3: 직각 두 방향 4: 세 방향 5: 네 방향 모두 CCTV는 벽 통과 못함, CCTV 감시 X -> 사각지대 CCTV끼리는 통과 가능 CCTV 회전 가능, 항상 90도, 감시 방향 가로 or 세로 6: 벽, CCTV가 못 뚫어 회전 가능한 경우는 1,2,3,4 5는 회전 필요 X 최대한 많은 곳을 check 해야함 ( 중복 없이 ) Check 유무 판단: 7 입력 1
알고리즘
목차 사고 과정 코드 구현 문제 해석 톱니바퀴 총 K번 회전, 시계 or 반시계 회전시킬 톱니바퀴, 방향 정하기 맞닿은 극이 같으면 움직이지 않는다. 극이 서로 다르다면 움직이는 톱니바퀴의 반대방향으로 움직인다. 첫 입력, N극 : 0 S극 : 1 12시부터 시계방향순 회전 횟수 이후 회전시킨 방법, 톱니바퀴 번호, 방향 출력, 12시 극의 값에 따라 점수 배분 💥 사고 과정 왼쪽과 오른쪽 각각을 따로 메서드로 만들어서 재귀형식 구현, 과오1 시계방향, 반시계 방향 회전을 단순히 arr[i+1] = arr[i]로 해버린.. 그러면 계속 갱신돼서 결국 같은 숫자만 나올텐데.. -> copy 배열을 활용해서 시계와 반시계 변화 구현 과오2 톱니의 회전여부를 돌아가면서 실시간 업데이트..XXXX ->톱니를 돌..
목차 문제 파악하기 해법 설계 코드 구현 디버깅 문제 파악하기 주어진 10 X 10 크기의 종이에 대한 정보가 주어진다. 종이에는 길이가 1부터 5까지의 정사각형 색종이를 이용하여 붙이려고 한다. 각 종이는 5개씩 존재하며, 가장 적은 개수의 색종이로 종이를 모두 채워라. 해법 설계 과정 색종이의 길이가 큰 거부터 작은 순으로 돌아가며 덮을 수 있는 거 찾으면서 전부 돌기 1까지 다 돌았는데 paper내의 1이 하나라도 남아있으면 바로 -1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 -> 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 --> 반례 발생, 풀이 설계 방법 전환 알고리즘을 사용해서 누가 뭐래도 최소값이라고 말할..
프림 알고리즘과 다익스트라 알고리즘의 공통점 그래프 최소 비용의 관점에서, 최소 비용을 탐색한다는 것이 가장 큰 공통점 구현 방법에서 반복문과 우선순위 큐 모두 사용 가능 프림 알고리즘과 다익스트라 알고리즘의 차이점 프림 알고리즘 다익스트라 알고리즘 간선 선택 기준 선택한 정점과 인접한 정점들 중 최소비용의 간선이 존재하는 정점 선택 해당 노드로 향하는 경로의 최소값, 간선의 가중치의 합이 최소인 경로 시작 노드의 차이에 따른 결과값 변화 없음 (모든 정점에 대해 동일한 결과) 있음 (정점마다 결과값이 달라짐) 저장 핵심 데이터 간선의 가중치 해당 정점에 도달하기 위한 최소 cost 저장 (경로를 포함) 🖥️코드 구현 import java.util.*; public class 다익스트라_우선순위큐 { s..
https://softeer.ai/practice/7726 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai ✍문제 해결 핵심 전략탈출 여부의 요인 정확히 분석하기 남우가 탈출하기 위해서는 유령에게 잡히지 않고 탈출구를 찾아가야 합니다. 남우와 유령 사이의 관계 명확히 파악하기 (벽 넘기의 유무) 🔍'유령에게 잡히지 않는다' ▶ 유령보다 탈출구에 더 빨리 도착해야한다. 🔍'탈출구를 찾아간다.' ▶ 탐색을 통해 탈출구에 도달할 수 있는가?. 🔍'벽을 넘을 수 있다.'를 위의 내용과 연관시키면 ▶ 벽의 유무를 고려한 뒤 남우가 최단거리로 출구에 가야 한다. 한 줄 요약 유령과 탈출구 사이 거리, 남우와 탈출구 사이 거리 (남우는 벽을 고려) 비교를 통해 탈출의 유무를 확인할 수 있다. 👨..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 분석 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수는 결국 1번과 연결 1번과 연결된 노드들을 모두 검사하여 count 하면 되겠구나?! 📝풀이방법 BFS 활용 ( Linkedlist, 2차원 배열) 사실 문제 자체는 간단해서 BFS 구현 연습 문제로 제격인 거 같습니다. BFS의 경우 선입선출을 기본적인 구조로 가지고 있으며, 완전탐색에서 너비 우선 탐색의 의미로 DFS와 대비해 같..
