복습용 블로그

알고리즘 복기용 메모 binary search : 정렬되어 있는 상태에서 특정 값의 위치를 찾는 검색 알고리즘 절반 위치씩 쪼개면서 검색을 하기 때문에 복잡도는 O(log N) 구현하고자 하는 것 : 중복 가능한 배열이 오름차순 정렬 가정 1. 찾고자 하는 값이 없을 때는 해당 값이 있다면 있어야 할 위치를 리턴 2. 찾고자 하는 값이 있고, 중복된 값이라면 가장 첫 번째 인덱스를 리턴 3. 찾고자 하는 값이 단일 값이라면 해당 인덱스를 리턴 중복이 없다 + 타겟이 존재한다는 기본적인 binary search의 경우, 단순히 left, right +-1 을 해주면서 target을 만나면 끝내는 식으로 진행하면 된다. ( while(left target) { res = 0; return res; } if(..

https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 자동완성 기능이 있는 사전을 이용해 주어진 문자열들을 만들기 위해서는 몇 개의 알파벳을 입력하여야 하는가의 문제입니다. ex) hello, hell -> h 입력 시 hell 까지 자동 완성, hello, hell, he -> h 입력 시 he 까지 자동완성, l 입력 시 hell 까지 자동완성 트라이를 이용하여 다음과 같이 풀 수 있습니다. 1) 입력으로 주어진 문자열의 마지막에 . 을 추가한다. (..

회사에서 치는 시험에 구글링이 안 되서 짬짬이 알고리즘들 개념을 다시 정리하고자 한다. 1. permutation (순열) 간단히 {0,1,2,3,4} 배열에서 5P3 을 구한다고 하면 {0,1,2} ~ {4,3,2} 까지가 계산된다. 이를 계산하기 위한 방법은 다음과 같다. - 전체 배열에서 현재 체킹하고 있는 인덱스가 방문했었다면 다음 인덱스로 넘어간다. - 방문 안 했었다면, 해당 값을 추가하고, 처음 루프부터 다시 이를 진행한다. (재귀) - 재귀적으로 진행하면서 추가된 값이 총 r 개를 만족하면 결과에 추가한다. - 재귀가 끝나면 체킹했던 인덱스 방문을 해제한다. {0,1,2,3,4} 로 되어 있는 배열에 대해 살펴 보면, - 0번째 값인 0이 현재 체크가 되어 있지 않으므로 0을 추가 ... ..

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net (회사에서 프로그래밍 시험을 보는데 C/C++, Java 만 있어서 C++로 다시 연습 중이다.) (처음에는 자식 노드한테 번호를 순차 부여해서 - ex. (1, 2), (1, 3), 연결 시, 1 -> "1", 2 -> "10" , 3 -> "11", (2, 4), (2,5) 연결 시, 4 -> "100", 5 -> "101", .... prefix 일치 여부로 풀려고 했으나 끝없는 메..

https://www.acmicpc.net/problem/3665 주어진 입력이 작년의 순위이고, 순위가 바뀐 팀들이 다음 입력으로 주어질 때, 올해의 최종 순위를 구하는 문제입니다. 알고리즘은 다음과 같습니다. 1. 등수가 n m 로 edge 있는 그래프 생성 (n=1, m=2 : n < m) 이 때 모든 등수에 대해 연결, 그리고 위상정렬에 사용할 진입 차수 계산 2. 새로 받은 입력으로 기존 edge를 제거하고, 새 edge를 연결, 그리고 진입 차수 새로 계산 3. 2번까지 진행 후 만든 그래프에서 사이클 발생 시, IMPOSSIBLE 4. 그렇지 않은 경우, 위상정렬으로 순차적으로 출력 1번에서 모든 n, m에 대해 edge를 만들었으므로, 사이클이 없는 그래프라면, ..