Problem 💻이 문제는 L ≤ 10^8 이므로 2차원 배열을 만들어 하나하나 뱀을 이동시켜가며 풀 수 있는 문제는 아니다. 그러므로 머리의 회전 횟수 N을 이용해 문제를 해결해야 한다.  Approach 1 ⭕구현해당 문제는 뱀이 머리를 1초마다 하나씩 늘려가며 어떤 시간에는 회전도 하고 하면서 최종 죽는 시간을 구하는 문제이다. 문제의 주체를 뱀이 아니라 사람이라고 생각하면 자신이 가던 경로와 겹치는 순간 혹은 범위의 밖으로 가는 순간 죽는 것으로 해석할 수 있다. 뱀은 오로지 수직, 수평으로만 머리가 늘어난다. 그래서 방향을 바꾸는 시간 차이와 바꾸는 방향이 주어지면 바꾸는 시간 전까지는 같은 방향으로만 이동한다. 그래서 해당 방향 전까지 하나하나 이동하지 않고 단번에 ‘x + time’ 또는 ..

Problem 💻결정 문제로 이분탐색 + 다익스트라 or BFS, DFS로 풀 수 있는 문제이다.컴퓨터 N개를 연결하는 최소 비용을 구하는데, 어떤 비용 X에 대하여 해당 비용 X보다 작으면 돈을 내고, 크면 무료로 연결하여 최소 비용을 구하도록 문제의 요구 조건을 바꾸면 된다.  Approach 1 ⭕이분탐색 + 다익스트라이분탐색을 통하여 최소한으로 내야할 금액을 결정하고, 다익스트라를 통해 무료로 연결한 횟수를 가중치로 하여 1 → N 컴퓨터로의 최소 무료 연결 횟수를 구한 다음 해당 횟수가 k를 넘는지 확인하면 된다.k를 넘는다면 연결할 수 없는 경우이므로 다시 비용을 더 증가시켜보고, k를 넘지 않거나 같다면 비용을 더 줄일 수 있는지를 확인한다. 그렇게해서 예제를 보면 최소 4의 비용은 되어야..

Problem 💻단순한 브루트포스 문제지만 어떻게 풀어야할지 좀 고민해봐야 하는 문제이다. Approach 1 ❌좌표 완전 탐색별 기준으로 완전 탐색처음 풀이는 2가지였다. 좌표 완전 탐색과 별 기준 완전 탐색. 좌표 완전 탐색은 (1, 1)부터 (M-L, N-L)까지 x ~ x+L, y ~ y+L 사이의 겹치는 좌표가 있는지 하나하나씩 찾아서 최고값을 갱신해주는 방법이다. 하지만, 문제의 조건에 N, M은 최대 500,000으로 되어있기 때문에 이렇게 할 경우 L = 1인 최악의 경우 500,000 * 500,000으로 2500억 가까이 되는 연산이 일어난다. 당연히 시간초과이다. 그래서 생각한 방법이 별 기준으로 완전 탐색이다. 처음엔 별 좌표 기준으로 x ~ x+L, y ~ y+L 까지 겹치는 별..

순환 참조는 의존 관계에 사이클이 생기는 상황으로 대표적으로 객체가 서로 양방향 참조를 하는 상황이 있다. @Dataclass Team { private long id; private String name; private List members;}@Dataclass Member { private long id; private String name; private Team myTeam;}@Data@NoArgsConstructor@Entity(name = "team")class TeamJpaEntity { @Id private String id; @Column private String name; @OneToMany(mappedBy = "myTeam") private List members;}@Data@No..

Problem 💻1863. 스카이라인 쉬운거 입력은 다음과 같은 스카이라인을 나타낸다................................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....XXXXXXXXXXXX 다음과 같이 여섯 개의 빌딩이 있을 때가 최소 개수의 빌딩이 있는 상황이다................................22.........333........111.22.......XX333XX.....X111X22XXX....XX333XXXXXXX...............................XX.........XXX........XXX.XX.......5555555.....4444444444....555555..

단일 책임 원칙(SRP; Single Responsibility Principle)개방 폐쇄 원칙(OCP; Open-Closed Principle)리스코프 치환 원칙(LSP; Liskov Substitution Principle)인터페이스 분리 원칙(ISP; Interface Segregation Principle)의존성 역전 원칙(DIP; Dependency Inversion Principle)각 원칙은 객체지향 언어에서 좋은 설계를 얻기 위해 지켜야 할 규범이다. 소프트웨어의 유지보수성, 확장성을 높이는 것이 목적이다.코드 유지보수성을 판단할 때 사용할 수 있는 실무적인 세 가지 맥락이 있다.영향 범위: 코드 변경으로 인한 영향 범위가 어떤지의존성: 소프트웨어의 의존성 관리가 제대로 이뤄지는지확장성:..

Problem 💻4485. 녹색 옷 입은 애가 젤다지? 링크가 ‘도둑루피’로 가득찬 동굴에서 (0, 0) → (n-1, n-1)까지 최소한의 루피를 잃으면서 도착해야 하는 문제이다. 동굴의 각 칸마다 도둑루피의 가치가 주어지고 해당 가치가 클수록 잃는 돈이 많아지는 것이다. Approach 1 ⭕다익스트라 (00:13:12) 이 문제의 해결방법은 ‘도둑루피’를 조금 다르게 생각해 해당 노드로 가는 ‘가중치’라고 생각하는 것이다. 해당 노드로 가는 모든 간선의 가중치가 도둑루피의 가치로 고정되는 것이다. 그럼, 가중치 그래프의 최단 거리를 구하기 위해서 사용할 수 있는 알고리즘인 ‘다익스트라’를 생각할 수 있다. Approach 2 ⭕BFS (00:10:27) 두 번째로는 BFS를 이용한 방법이 있다. ..

문제https://www.acmicpc.net/problem/1238 접근 1 ⭕플로이드 워셜 (00:21:37)각각의 1~N번 마을에 살고 있는 학생들이 X번 마을을 왕복할 때 가장 시간이 많이 걸리는 학생이 누군지 찾는 문제이다. 즉, 1~N번 마을에서 X번 마을까지의 최단 거리를 구하고, X번 마을에서 1~N번 마을까지의 최단 거리를 구한 다음에 1↔X, 2↔X, …, N↔X 중 최대값을 구하면 되는 문제이다. 두 가지의 최단 거리를 한번에 구하는 가장 쉬운 방법이 바로 ‘플로이드 워셜’이다. 플로이드 워셜은 모든 정점에서 시작해 모든 정점까지의 최단 거리를 구하는 알고리즘이다! 접근 2 🔺다익스트라 (00:30:12)두 번째 해결 방법으로는 다익스트라가 있다.💡 1~N번 마을에서 X번 마을까지..