링크: https://programmers.co.kr/learn/courses/18/lessons/1878문제코딩 테스트의 데모 문제, 연습 문제로 많이 등장하는 문제입니다.직사각형을 나타내는 네 개의 꼭짓점 중 세 개의 좌표가 주어졌을 때, 나머지 한 좌표를 구하는 문제죠.좌표의 범위에 따라 해결 방식이 다를 수 있습니다. 여기서는 좌표의 범위가 10억까지인 프로그래머스 문제의 풀이를 다룹니다. (백준에서는 1000 이하의 정수)네 점의 x좌표들은 모두 2번씩 등장합니다. 마찬가지로 y좌표들도 2번씩 등장해야하죠. 그럼 x, y 좌표들 중 1번만 등장한 녀석들이 문제의 정답입니다.이것을 카운팅하는 것이 곧 문제를 해결하는 것인데, 좌표가 10억까지 주어지는 경우라면 해시(Hash)와 같은 적당한 자료구..

링크: https://www.acmicpc.net/problem/1405문제동서남북 각 방향으로 이동할 확률이 주어지고, 로봇이 동선을 겹치지 않게 n번 움직일 확률을 구하는 문제이다.(0, 0)부터 출발한다고 생각하면 동서남북 경계의 끝은 (14, 0), (-14, 0), (0, 14), (0, -14) 일텐데 음수를 없애기위해 출발점을 (15, 15)로 설정하면 편하다.좌표값을 들고 다니는 이유는 동선이 겹쳐서는 안되기 때문에, 다시 말해 이미 방문한 위치는 다시 방문하지 않도록 하기 위해서이다.어떤 한 위치에서 생각했을 때, 동쪽으로 이동한다면 동쪽에서 나오는 모든 확률은 (그 위치에서 발생하는 확률 * 동쪽으로 이동할 확률)이 된다. 이걸 동서남북 모든 방향과 모든 위치마다 반복한다면 정답을 구할..

링크: https://www.acmicpc.net/problem/2096문제어떤 칸을 선택하면 선택 가능한 다음 칸이 정해지는 점에서 9465번 - 스티커와 굉장히 유사합니다. 사실 동일한 풀이로 해결되지만 다른 점이 있습니다.이 문제는 메모리의 제한이 4MB로 엄청 작다는 겁니다.적은 메모리 제한때문에 스티커 문제처럼 dp[3][N] 과 같은 배열을 선언할 수도 없고 재귀 함수까지도 염려해야하는 상황입니다. 그럼 어떻게 해결해야할까요?풀이어떤 r번째 줄에서 어떤 칸을 선택한다면, 이는 다음 줄인 r+1번째 줄에 영향이 갑니다. 어떤 칸을 선택할 때, 항상 2개의 줄만 확인하면 된다는 점으로 메모리를 줄일 수 있습니다. 왜냐하면 1번째 줄은 2번째 줄에 영향을 주고 2번째 줄은 3번째 줄에 영향을 주지만..

링크: https://www.acmicpc.net/problem/16964풀이문제의 가장 큰 힌트는 입력된 그래프의 모양이 트리라는 점이다. 즉, 사이클이 없다. 올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다.이 특징을 살리면, 어떤 순서 \(i\)번째에 등장하는 노드 \(x\)의 깊이는 어떤 순서 \(i\)+\(x\)의 서브트리의 크기까지는 전부 그 노드의 자식이라는 점이다. 위 그림처럼 입력이 주어졌다고 해보자.여러 DFS 방문 순서가 가능하겠지만, 그 중 하나인 [1, 3, 5, 8, 6, 4, 7, 9, 2]의 순서를 예로 들자면 어떤 \(i\)번째 순서에 있는 노드 \(x\)는 자신의 서브트리의 크기만큼 다음 순서가 자신의 형제 노드이다.2번째 순서..

링크: https://www.acmicpc.net/problem/11447문제문제에서 정의되는 x, y, z 방향으로 1000을 넘지 않는 길이만큼 C번 움직인 후에, 마지막에 완성된 그림 속에 채워지는 삼각형의 수는 몇 개인지 맞추는 문제이다.삼각형들은 빈 공간이 없이 빽빽하게 채워져있고, 다시 시작점으로 돌아오지 않는 잘못된 입력은 주어지지 않는다. 처음에는 x,y,z 방향을 2차원 x,y 평면으로 적당히 전사시켜서 그 넓이를 구하는 방식으로 해야하나? 라는 생각을 했다. 그 외에도 문제를 변형시키는 별 생각을 다 했는데 결국 풀이는 다각형의 면적을 구하는 문제였다.풀이다각형을 이루는 꼭짓점들이 주어지면, 그 다각형의 면적을 구하는 문제이다. 이건 신발끈 공식으로 해결할 수 있다. 다각형의 각 꼭짓점..

링크: https://www.acmicpc.net/problem/1976문제\(n\)개의 도시 사이의 연결 상태가 인접 행렬로 주어지고 여행 계획에 있는 \(m\)개의 도시가 주어질 때, \(m\)개의 도시를 모두 방문할 수 있는가를 묻는 문제이다. 다시말하면, \(m\)개의 도시가 모두 연결되어있는가를 확인하면 된다. 이 문제는 서로소 집합(Disjoint-Set)으로 간단하게 해결할 수 있다. 각 도시들의 연결 상태만 확인하면 되므로, 연결된 도시들을 집합으로 묶어서 표현한 후 마지막에 주어지는 \(m\)개의 도시들이 모두 같은 집합에 속하는 지 확인하면 정답이기 때문이다.코드

링크: https://www.acmicpc.net/problem/1613이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html문제알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다. 방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다. a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다. 문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. n이 400으로 작으므로 플로이..

링크: https://www.acmicpc.net/problem/9465예전 풀이: http://joonas-yoon.blogspot.com/2014/08/9465.html풀이한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다. A B C DE F G H 만약 위와 같이 있다고 생각해보자. A를 고른다면 C, D, F, G, H 중에 골라야한다. E를 고른다면 B, C, D, G, H 중에 골라야한다.바로 다음 칸(열)에만 영향이 있고, 그 이후의 C, D, G, H를 고민하는 것은 변함이 없다. 즉 어떤 i번째 열을 볼때, i+2번째 이후의 열은 영향이 없다는 뜻이다. i번째 열에서 고민할 점은 3가지이다. 1. 고르지 않는..