밤이 블로그

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 <..

인접행렬과 인접행렬의 거듭제곱 → 잘 설명된 블로그가 있어서 공유합니다.http://blog.naver.com/gt7461/110151975370

BOJ#1062 가르침 * 문제https://www.acmicpc.net/problem/1062 * 풀이 꽤 어렵게 푼 문제입니다. 이 문제는 주어진 단어들을 어떤 자료구조에 담는지가 핵심인 것 같습니다. 1. 단어를 읽을 수 있다는 것은 그 단어를 이루고 있는 알파벳을 모두 알고 있다는 것입니다. -> 따라서 단어를 입력 받을 때, 불필요한 정보는 받지 말고 각 단어를 이루고 있는 알파벳의 모음으로 입력을 받습니다.-> 즉 antahellotica 단어는 [a, n, t, h, e, l, o, i, c] 으로 입력을 받으면 됩니다.-> 처음에는 중복되는 알파벳은 받지 않고 순서는 상관 없으므로 HashSet을 이용하려 했지만 재귀 형태에서 iteration을 사용하는 것에 불편함이 있어서 , 조금 더 ..

BOJ#2196 로봇 조종하기 * 문제https://www.acmicpc.net/problem/2169 Olympiad > 한국정보올림피아드 > KOI 2002 > 고등부 1번 * 풀이 꽤 어려운.. 문제인 것 같습니다.풀이는 다른 블로그에 자세히 나와 있으니, 저는 제가 어떻게 생각을 했는지 써보겠습니다. 1. 처음 한 생각은 Backtracking 입니다. 의외로 쉽게 풀릴 것 같습니다.2. 인풋값의 사이즈를 봅니다. 1000 * 1000 사이즈면 Backtracking 형식으로는 풀 수 없을 것 같습니다. (시간 초과)3. Dynamic Programming으로 방향을 잡습니다. 4. dp를 정의합니다. dp[i][j] : (1, 1)에서 (i, j)에 도달할 때 최대 비용5. 왼쪽, 오른쪽, 아래..

[공유] 알고리즘 공부를 입문할 때 읽으면 좋은 자료들 Algorithm Problem Solving 기초 http://slides.com/gangseoklee/aps-5#/

BOJ#1405 미친 로봇 * 문제https://www.acmicpc.net/problem/1405 * 풀이 - N의 범위가 작으므로 visited 배열을 이용하여 간단하게 단순 경로인지 아닌지 체크해줍니다.- 각 방향으로 움직일 확률을 입력 받을 때, double 타입의 확률로 바꿔서 입력받아줍니다.- 1번 이동해서 단순경로가 된다면 확률은 1.0, 그렇지 않으면 0.0 입니다.- 4방향으로 움직일 수 있으므로4방향 Sum(각 방향으로 움직일 확률 * 현재 위치에서 N-1번 움직일 때 단순경로가 될 확률) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231405_CrazyRobot/src import java.io.BufferedReader; i..