밤이 블로그

BOJ#10942 팰린드롬? * 문제https://www.acmicpc.net/problem/10942 * 풀이 문자열 중에서 팰린드롬에 대하여 지금 공부할지 아니면 나중에 공부할지 고민했습니다만..(알고리즘 대회가 아니면 별로 쓸 일이 없기 때문에) 간단히 O(N^2) 풀이와 O(N)풀이에 대해 공부해 보았습니다. 완벽히 이해한 상태가 아니기 때문에 설명은 나중에 추가하도록 하겠습니다.팰린드롬은 너무 어렵습니다.. 팰린드롬 공부 링크 : http://stack07142.tistory.com/128 * 나의 코드 O(N), Manacher's Algorithm - 어느 한 원소를 기준으로 좌/우로 넓혀가면서 검사 -> N이 홀수인 경우에는 문제없지만, N이 짝수인 경우에는 문제가 생김 -> 일괄적으로 2..

n명을 k개의 그룹으로 분할하는 경우의 수 (제 2종 스털링 수) 출처 : http://terms.naver.com/entry.nhn?docId=3405190&cid=47324&categoryId=47324

Manacher's Algorithm #1 : https://algospot.com/wiki/read/Manacher's_algorithm#2 : http://www.ideserve.co.in/learn/longest-palindromic-substring-manachers-algorithm 알고리즘 설명은 위 출처에 잘 되어 있습니다.- Time Complexity : O(n)- Space Complexity : O(n) * 관련 문제BOJ#10942 팰린드롬? https://www.acmicpc.net/problem/10942 * 코드 public class Manacher { public Manacher(String s) { char[] T = new char[s.length()*2 + 3]; T[..

BOJ#12851 숨바꼭질 2 * 문제https://www.acmicpc.net/problem/12851 * 풀이 쉬운 문제인데 푸는데 고생을 좀 했습니다. 일단은 1697 숨바꼭질 문제와 동일한데..동생을 찾는 가장 빠른 시간을 출력하는 것과가장 빠른 시간으로 찾는 방법의 개수까지 출력해야 합니다. 헷갈리지 말아야 할 것은 가장 빠른 시간으로 찾는 '경로'가 아니라 '방법'의 개수 입니다. 즉, 입력 데이터가 1 10일 때가장 빠른 경로는 1 -> 2 -> 4 -> 5 -> 10 이지만방법으로 따지면 아래와 같이 2가지가 있습니다.1 -> 2(+1) -> 4(*2) -> 5(+1) -> 10(*2)1 -> 2(*2) -> 4(*2) -> 5(+1) -> 10(*2) 따라서 방법의 개수를 구하려면 큐에 ..

BOJ#1670 정상 회담2 * 문제https://www.acmicpc.net/problem/1670 * 풀이 Dynamic Programming 문제입니다. 동적계획법은 복잡한 문제를 하위 문제로 나누어 푸는 것을 말합니다. 이 문제에서는 그림을 그려보면 이해하기 쉽습니다. 예를 들어 N = 6일 때, 아래 3가지 경우의 합을 구하면 되겠습니다. 1) 0번째 사람과 1번째 사람이 악수하는 경우dp[6] += dp[0] + dp[4](한쪽 구역은 0명, 다른 구역은 4명) 2) 0번째 사람과 3번째 사람이 악수하는 경우dp[6] += dp[2] + dp[2](한쪽 구역은 2명, 다른 구역은 2명) 3) 0번째 사람과 5번째 사람이 악수하는 경우dp[6] += dp[4] + dp[0](한쪽 구역은 4명, ..

BOJ#2580 스도쿠 * 문제https://www.acmicpc.net/problem/2580 * 풀이스도쿠는 어떻게 푸는 것일까요?사람이 스도쿠를 푸는 과정을 생각해보면 아래와 같습니다.(Backtracking) 숫자를 하나 검증해서 넣어보고 -> 다른 칸으로 진행 -> 실패하면 되돌아와서 다른 숫자를 넣어보고 -> 반복.. 계산량을 줄이기 위해 최초 map 정보를 입력 받을 때 필요한 정보들을 미리 저장해두면 됩니다.1. 빈칸의 정보를 저장한다.2. 각 행의 정보를 저장한다.3. 각 열의 정보를 저장한다.4. 각 사각형의 정보를 저장한다. 자료구조는 boolean 배열로 해도 되고, bit mask를 이용해도 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blo..

BOJ#11650 좌표 정렬하기 * 문제https://www.acmicpc.net/problem/11650 * 풀이쉬운 문제이지만 실수했던 점 -> x에 대해 확실히 기준을 세워줄 것 틀림@Override public int compareTo(Coordinate o) { return this.x o.x ? 1 : this.y < o.y ? -1 : 1; } * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%2311650_Aligning..

BOJ#1162 도로포장 * 문제https://www.acmicpc.net/problem/1162 * 풀이그래프 최단거리를 찾는 문제로써, 다익스트라 알고리즘으로 문제를 풀 수 있습니다.그러나 K개 이하로 도로 포장하여 가중치를 제거할 수 있기 때문에 추가적인 문제 풀이 방법이 요구됩니다. 따라서 기존의 dist 배열을 아래와 같이 바꿔봅시다.-기존의 dist[i] : 시작점에서 i까지의 최단 경로 cost라고 한다면-이 문제에서 dist[i][k] : 시작점에서 i까지 k개 도로를 포장하여 가는 최단 경로 cost 기존과 동일하게 dijkstra 알고리즘을 쓰되 각 경로에서 포장하는 경우, 포장하지 않는 경우를 구분하여 진행하면 되겠습니다. * 나의 코드https://github.com/stack071..

BOJ#1946 신입 사원 * 문제https://www.acmicpc.net/problem/1946 * 풀이서류 성적으로 오름차순 정렬 후 면접 성적을 순차적으로 검사한다. 정렬 이후 첫번째 줄은 무조건 합격이므로2번째 줄부터 N번째 줄까지 순차적으로 진행한다. 서류 성적으로 한번 정렬 되었으므로 이미 누군가에게는 한번 졌다는 뜻이다.따라서 면접 성적에서 누구에게라도 한번만 더 지게 되면 탈락이다. 따라서, 2번째 줄부터 N번째 줄까지 순차적으로 진행하면서면접 성적의 최고 순위를 계속 갱신 + 최고 순위와 현재 라인을 검사 * 나의 코드 https://github.com/stack07142/BOJ/tree/master/BOJ%231946_Freshman/src import java.io.IOExcepti..

BOJ#1753 최단경로 * 문제https://www.acmicpc.net/problem/1753 * 풀이 다익스트라 최단 경로 문제입니다.주의할 점으로는 V와 E의 범위입니다. (1 dist[here] + W[here][i]) { dist[i] = dist[here] + W[here][i]; pq.add(new Element(i, dist[i])); } } } } } } class Element implements Comparable { int node; int dist; Element(int node, int dist) { this.node = node; this.dist = dist; } @Override public int compareTo(Element o) { return this.dist <..