밤이 블로그

인접행렬과 인접행렬의 거듭제곱 → 잘 설명된 블로그가 있어서 공유합니다.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..

BOJ#2661 좋은수열 * 문제https://www.acmicpc.net/problem/2661 * 풀이 - 수열의 시작은 무조건 1이다. - 나쁜 수열인지 체크하는 알고리즘 세우기- Backtracking 구성 1) 나쁜 수열 체크2-1) 나쁜 수열인 경우 돌아가기2-2) 좋은 수열인 경우3-1) 길이를 다 채운 경우 -> 답을 return하고 모든 재귀함수를 종료한다.3-2) 길이를 다 못채운 경우4) 숫자 추가 (1~3 순서대로, 가장 작은 수를 만들어야 하기 때문에) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232661_GoodSequence/src import java.io.BufferedReader; import java.io.IO..

BOJ#1339 단어 수학 * 문제https://www.acmicpc.net/problem/1339 * 풀이 이 문제는 두가지 풀이법으로 풀어보겠습니다. 예)MCR ACDEB 1) 수학으로 풀기 위의 두 숫자를 풀어보면MCR = M * 100 + C * 10 + R * 1ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B * 1 두 숫자를 더해보면MCR + ACDEB = 10000A + 1001C + 100M + 100D + 10E + R + B 가 됩니다. 하나의 문자는 하나의 숫자(0~9)로 대응되고합의 최대값을 구하고 싶으므로 즉, 10000A + 1001C + 100M + 100D + 10E + R + B의 최대값을 구하면 되는 것입니다. A -> C ->..

[수학] 두 선분의 교차 여부 확인하기 아래와 같이 두 선분 AB, CD가 존재할 때A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4) fn(A, B, C) * fn(A, B, D) fn(A, B, C) = (x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3) -> fn(A, B, D) = (x1y2 - x2y1..

BOJ#12094, BOJ#12100, BOJ#12208, BOJ#12209 2048 * 문제https://www.acmicpc.net/problem/12094https://www.acmicpc.net/problem/12100https://www.acmicpc.net/problem/12208https://www.acmicpc.net/problem/12209 * 2048 게임 링크https://gabrielecirulli.github.io/2048/ * 문제 풀이 순서1. Move(Up, Down, Left, Right) 연산 구현하기BOJ#12208, BOJ#12209 2. N번 Move 이후 최대값 구하기BOJ#12100, BOJ#12094 * 나의 코드 https://github.com/stack07..

BOJ#1707 이분 그래프 * 문제https://www.acmicpc.net/problem/1707 * 풀이 그래프 관련 기본 문제입니다. 저는 BFS/DFS로 풀었는데, 주의할 점으로 연결 그래프와 비연결 그래프를 둘 다 고려해주어야 합니다, * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231707_BipartiteGraph/src/Main.java (BFS)import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** * BOJ#1707 이분 그래프 * https://www.acmicpc.net/p..