감자는 아직 꿈을 꾼다.

https://www.acmicpc.net/problem/3860  🤔 풀기 전의 문제에 대한 생각☑️ 문제를 읽으며문제를 읽고 생각한 것은 좌표를 간선을 이용해서 연결하여 그래프로 만들자 였다.BFS에서 4방향으로 이동하는 것을 간선을 통해서 표현하고벨만 포드 알고리즘을 통해서최단거리를 구하려 했다.문제 자체도 계속해서 과거를 돌아가는 것을 출력하라고 하기에대놓고 벨만 포드 문제라고 생각했다. 물론 해당 문제를 가지고 플로이드는 실행하지 못한다. N 이 900가 되기에 3제곱이 되면 시간복잡도가 무조건 터진다.핵심결국 이 문제의 핵심은 개인적으로 바라볼때 구현력이다.좌표를 간선으로 연결해서 그래프로 만드냐이 부분에서 나는 처음에 가로 → 이 방향과 세로 위 방향을 순회하면서연결시켰지만 끝내 오류가 계..

알고리즘 : 유니온 파인드 유니온 파인드는 말그대로 합치기와 탐색입니다.여기서 상호 배타적인 집합 관계가 나옵니다. 말 그대로 둘이 어떠한 교집합도 없는 집합입니다.그래프로 생각하면 둘이 완전히 분리된 그래프 인거죠. 파인드는 자기 자신의 부모로 계속 올라가서 루트 노드까지 가는 과정이고 여기에서 만약 서로 다른 두 점을 파인드 했는데 루트 노드가 같을 경우는 이미 같은 집합 인것이고다를 경우는 다른 집합인 것이겠죠 유니온은 말 그대로 두 집합을 합치는 과정인데 여기서 중요한 게 깊이 차이를 신경써야됩니다.그냥 막무가내로 붙여버리면 깊이가 깊어져서 비효율적이게 됩니다.그래서 두 루트노드의 랭크를 확인해서 더 큰 랭크인 루트노드를 부모 루트 향하게 작은 랭크의 루트노드를 바꿔주면 트리의 깊이 차가 안생기므..

알고리즘 : BFS토마토 시리즈로서 2차원인 7576번과 3차원인 7569번을 설명하도록 하겠다.문제설명 : 7576번 토마토https://www.acmicpc.net/problem/7576링크 참조 내 풀이 이 문제는 시작점이 여러개 일경우의 BFS 문제이다.문제에서도 주어진 것처럼 토마토의 위치가 여러군데에서 시작하고BFS를 따로따로 진행하면 dist배열 초기화가 먼저 이루어져서 겹치는 부분에 대해 처리가 정확히 되지 않는다.간단하게 이 문제를 풀이하면 시작점들을 큐에 집어넣고 BFS를 시작하면 된다.왜냐하면 큐의 특성상 FIFO 이므로 시작점들을 넣고 BFS를 돌리면 순차적으로 각 시작점 위치에서 BFS가 돌아가면서 실행이 되기 때문이다. 큐의 특성으로 거리순으로 저장되는 것 만약에 스택이였으면 하..

String 문제예외상황만 잘 처리하면 되는 문제다. https://www.acmicpc.net/problem/3613  내 풀이 StringBuilder의 사용법을 익힐수 있는 좋은 문제다.deleteCharAt() -> 해당 인덱스 문자 삭제insert() -> 해당 인덱스 앞에 문자 삽입indexOf() -> 포함 되있으면 해당 시작 인덱스 반환 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Solution { public static void main(String[] args) throws IOException { ..

String 문제자바의 String 메소드를 활용해서 풀 수 있는 문제3가지 방식으로 풀이를 설명한다문제 설명https://www.acmicpc.net/problem/9996 내 풀이 주어진 패턴을 * 를 기준으로 split하여 앞부분과 뒷부분을 나누고substring을 활용해서 주어진 문자열과 같은지 확인한다.주의할 점은 주어진 문자열이 first와 second의 합보다 작은 것에 예외처리또한 split할 때 그냥 * 로 하면 아래와 같은 에러가 뜨게된다.**Dangling meta character ' * ' near index 0+, * , ^ 로 나누고자 할 때도 발생하는 오류로**앞에 \ 기호 두개를 붙여야 된다. import java.io.BufferedReader;import java.io...

알고리즘 : 시뮬레이션문제 설명https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  🪟내 풀이 삼성식 시뮬레이션 문제이다.물론 실제 삼성전자 코테를 이번 하반기에 가서 본 입장으로선 그것보다는 귀여운 수준의 문제지만생각지도 못한 실수를 해서 고생했다.내가 한 실수는 set에 자표를 저장하고 사용할 때split으로 나눠서 쓰는게 아니라 단순하게 charAt한다음 - '0'해서 사용한 것이다.이렇게 사용하면 당연히 안되는 게, 좌표 크기가 2자리 수가 되면 사고가 나는 것이다.어이없는 실수를 했..

알고리즘 : 벨만 포드 알고리즘다익스트라 알고리즘과 달리 음의 가중치인 경우에 최단경로 구하기가 가능하다.하지만 다익스트라 알고리즘에 비해서 모든 간선을 다 확인하므로 O(V * E)로 시간복잡도가 느리다.또한 음의 순환의 확인이 가능하다.음의 순환이 존재하면 최단경로는 구할 수 없다.문제https://www.acmicpc.net/problem/11657내 풀이기본적인 벨만포드 알고리즘으로 풀었다.풀다보면 38프로에서 출력초과가 뜨는 경우가 있는데이 조건에서 n= 500,m = 6000인 경우 모든 간선이 -10000 일 경우 최단경로 값이 -30억이 나올 수 있기에 Int오버플로우가 발생하는 경우 일 것이다. 이는 dist 배열을 Long 타입으로 선언하여 해결 할 수있다.package com.exam..

알고리즘 설명 : 다익스트라 알고리즘최단 경로 알고리즘을 사용한다.다익스트라 알고리즘은 한 정점에서 다른 모든 정점에 대한 최단 경로를 정하는 알고리즘이다.여기서 최단 경로란 상황에 따라서 달라진다.가중치가 있을 경우 가중치의 합이 가장 작은 길이 최단 경로이고,가중치가 없을 경우 간선의 갯수가 가장 작은 길이 최단 경로다.문제 설명https://www.acmicpc.net/problem/1753시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초 256 MB 224898 69029 35315 25.902%문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선..

알고리즘 : 큐 or 연결리스트https://www.acmicpc.net/problem/1158     문제 설명문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.두 가지의 풀이 방법이 있다.1. 큐큐를 사용해서 푸는 것이 제일 연상하기 쉬운 풀이 방법이다.하지만 메모..