LeetCode의 141번을 풀다가 발견한 알고리즘. Linked List Cycle - LeetCode Linked List Cycle - Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internall leetcode.com 설명과 사진은 geeksforgeeks를 참고. Floyd’s Cycle Finding Algorithm - GeeksforGe..

322. Coin Change 동전의 목록인 coins가 주어진다. coins로 만들어야하는 amount가 주어진다. coins로 amount를 만들때 가장 적은수를 사용하는 케이스를 출력해야한다. class Solution { public int coinChange(int[] coins, int amount) { // amount가 0이면 만들수 없다 if(amount == 0) return 0; int[] dp = new int[amount+1]; // dp 구현을 위한 공간 할당 Arrays.fill(dp, Integer.MAX_VALUE); // 각 dp 원소에는 Integer의 최대값으로 초기화 Arrays.sort(coins); // coins를 오름차순으로 sorting List coinLi..

LeetCode를 풀면서 고생했던(?) 문제와 재밌게 풀었던 문제들을 돌아보는 시간. 886. Possible Bipartition 서로 함께할 수 없는 번호들이 주어지고 return으로 2개의 그룹을 만들 수 있는지를 넘겨줘야하는 문제다. 탐색으로 풀어야겠다고 생각하고 접근까지는 했으나 상태를 3개로 구분하지 못해서 헤맸다. (돌아보면 진짜 아무것도 아닌데) 방문, 미방문이 아니라 미방문, 그룹1, 그룹2 이런식으로 3가지의 상태를 통해 문제를 풀었어야했다. class Solution { public static boolean possibleBipartition(int N, int[][] dislikes) { int[] peopleGroup = new int[N+1]; Map graph = new Ha..

오랜만에 알고리즘 한문제 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net MxN 사이즈의 행렬속에서 꼭지점의 숫자가 같은 (사이즈가 가장 큰)정방행렬을 찾는 문제다. 아래와 같은 행렬이 있다고 할때 꼭지점 숫자가 같은 경우는 2가지 Case가 있으며, 그중 사이즈가 가장큰 정방행렬 (붉은색 박스)의 행과 열의 길이의 곱이 정답이 된다. 해결법은 아래 그림처럼 행렬값을 기준으로 우측,아래쪽, 우측하단의 숫자들을 확인하면된다. 아래는 구현 소스코드 mport java.io.BufferedReader; import..

1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 입력된 문자에 존재하는 알파벳이 연속되는지 확인하는 문제이다. 아이디어 1. 입력된 문자에 존재하는 알파벳을 구한다. 2. 알파벳이 연속되는지 확인한다. 3. 현재의 index가 이전의 index보다 +1인 경우는 연속이며 그렇지 않은 경우는 불연속이다. 4. 문자내에 알파벳이 하나만 있는 경우는 연속으로 처리한다. 구현 getAlphabet 함수를 만들어 입력된 문자내에 존재하는 알파벳을 ArrayList로 반환하도록 한다. s..

2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 입력된 문자의 갯수를 세는 프로그램을 만드는 문제다. 입력된 문자중에는 크로아티아 알파벳이라고 해서 2개이상의 문자가 조합되어 1개의 문자를 의미하는 케이스가 존재한다. 아이디어 입력받은 문자에서 크로아티아 알파벳의 갯수를 센다. 또한 크로아티아 알파벳이 있다면 "_" 문자 형태로 치환한다. 치환된 문자에서 "_"가 아닌 문자의 갯수를 센다. 구현 구현 하면서 주의할 점은 크로아티아 알파벳이 있는지 검사할때 긴문자부터 수행해..