알고리즘/팁 (9) 썸네일형 리스트형 그래프에서 사이클 찾는 법 해시 테이블 이용 노드를 해시 테이블에 넣고 그 노드가 다시 방문하면 사이클 존재 투 포인터 slow = head fast = head.next slow는 한칸씩 전진, fast는 두칸씩 전진한다 fast가 slow와 만나면 사이클 존재 만나지 않고 fast가 null 혹은 fast.next가 null이라면 사이클 존재 x https://leetcode.com/problems/linked-list-cycle/ Linked List Cycle - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next intervi.. [Python] 위상정렬 위상 정렬은 기본적으로 N번 만큼만 수행한다. N개의 원소의 순서를 알아내는 것이기 때문이다. 이를 이용해 알아낼 수 있는 정보들이 있다. 첫번째: 사이클 발생 첫번째로 N번 만큼 수행할 동안 큐안에 0개의 원소가 들어있다면 사이클이 발생했다는 것이다. 그 이유는 위상 정렬을 할 때 indegree를 감소시키는데 이 값이 0일때만 큐 안에 들어간다. 하지만 사이클이 있어 한번 더 진입을 하게되면 큐 안에 값이 들어갈 수 없기 때문이다. 두번째: 순서 불분명 두번째로 큐 안에 2개 이상의 원소가 들어가있다면 순서가 확실하지 않아 여러 순서가 발생할 수 있는 것이다. indegree 값이 0인 값이 여러개가 존재하게 되면 큐 안에 2개 이상의 원소가 들어가게 되는데 이는 동시에 들어간 노드의 순서가 불분명하.. [Python] 시간초과가 난다면 1. 입출력 속도를 높여본다. import sys input = sys.stdin.readline 2. 파이썬이라서 시간 초과가 나는 것이 아닌지 고민해본다. 자바 혹은 c++로 풀면 통과가 되는 경우가 있다. 예시> https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접� www.acmicpc.net 위의 경우가 아니라면 대부분 로직이 잘못됐다는 이야기 일 것이다. 새로운 알고리즘을 짜 보자 [Python] set 소소한 팁 set안에 값을 넣고 특정 값이 있는지 찾고 싶다면 x in set 이렇게 사용하면 된다. 예시로 set안에 좌표값을 넣고 그 좌표에 도착했는지 여부를 알고싶다면 (x,y) in set 이렇게 쓰면 유용하다. JAVA EOF 판단 Scanner while(sc.hasNextInt()) { sc.nextInt(); } while(sc.hasNextLine()) { sc.nextLine(); } BufferedReader BufferedReader br = new BufferedReader(new InputStreamReader(System.in); String input = ""; while((input = br.readLine()) != null) { } 만약 입력의 끝이 주어지지 않고 계속 받는다는 문제가 나오면 이렇게 쓰면 된다. 문제 예시 http://boj.kr/3745 3745번: 오름세 문제 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다. 정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보.. 특정 구간에 0~9의 숫자 갯수 찾기 start%10 가 0이 될때까지 start++를 한다. 이 과정에서 start에 나오는 숫자의 갯수를 세준다. end%10가 9가 될때까지 end--를 한다. 이 과정에서 end에 나오는 숫자의 갯수를 세준다. 0~9 모두에 (end-start+1)*t를 더해준다. 이때 t의 값은 어떤 자리수를 세는지에 따라 다르다. 예를 들어 일의 자리를 센다면 t=1이고 십의 자리를 센다면 t=10이다. 십의 자리를 셀때는 일의 자리를 셀 동안 계속해서 반복적으로 나오기 때문이다. start > end 혹은 start == 0, end == 0일때 반복을 종료한다. ans = 0; long mul = 1; while(A next permutation 다음 순열에 해당하는 배열을 찾는 방법. 처음부터 순서대로 배열을 보면서 arr[i] = arr[i] 인 마지막 i를 찾는다. 만약 그러한 i가 없다면 이미 마지막 순열이다. 다음은 끝에서 시작하면서 arr[j] > arr[i] 인 첫번째 j를 찾는다. 이후에 swap(i,j)한다. 그 이후에 i+1부터 끝까지 정렬을 해준다. 정렬을 할 때는 앞뒤만 바꾸는 작업을 해주면 된다. 그 이유는 i+1부터 끝까지는 이미 내림차순이기 때문이다. 이 배열을 예로 들면 1번을 만족하는 i는 숫자 1을 가지고 있는 arr[2]이다. 또한 3번을 만족하는 j는 숫자 7을 가지고 있는 arr[4]이다. 따라서 i .. 바이너리 카운팅을 통해 부분집합 생성 public class subset { public static void main(String[] args) { char[] arr = {'a','b','c'}; for(int i = 0; i < (1 이전 1 2 다음
