나만의 길

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net DFS를 통해 구현하는 문제. 해당문제와 유사한 문제가 많았기 때문에, 참고해서 푼다면 금방 풀 수 있었던 문제입니다. 단, 3 구역을 각각 처리하고, 이를 2 구역으로 나누는 부분처리만 할 수 있다면 어렵지 않게 풀 수 있었던 문제입니다. ※ 고려사항 1. 입출력 처리 2. DFS 처리 3. 정상, 색약 카운팅 1. 입출력 처리 해당 문제는 기존의 그래프문제와 살짝 입력구문이 다릅니다. ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 그래프 이론 중, 플로이드 - 워셜 방식으로 접근하는 문제입니다. 해당 경로까지 가는 방법이 1개라도 존재한다면, 1 그렇지 않다면 0을 출력하게 합니다. 본인은 단순히 BFS로만 접근했었고, 메모리초과로 인해 조금 더 단순하게 코드를 변형한 뒤, 구현했습니다. 그러나 플로이드 - 워셜 방식을 알고 난 뒤, 문제의 접근이 굉장히 쉬워졌습니다. 그래서 BFS, 플로이드 - 워셜 방식 2가지에 대해서 알아보려 합니다. ※ 고려사항 1. 입출력..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 분류 힌트가 없었다면, 접근법을 찾기 굉장히 어려웠었던 문제. BFS를 통해 접근해야 합니다. 각 위치에서의 +1, -1, x2 값을 노드로 계속해서 진행한 뒤, 해당 노드가 찾고자 하는 K값이라면, 종료시키면 됩니다. 또 해당 노드의 범위가 0에서 100,000 사이의 범위에서만 존재해야 하므로, 이 부분 역시 참고해줘서 문제를 해결하면 됩니다. ※ 고려사항 ..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 분할정복 문제. 2^N x 2^N 사각형을 계속해서 4등분을 해서 해당하는 좌표의 값을 불러오는 문제입니다.여기서 Key포인트는 '모든작업을 하면 안된다' 입니다. Divide & Conquer 방식으로 해당 좌표에 포함되는 부분만 나누어서 문제를 해결해야 메모리초과없이 문제를 해결할 수 있습니다. 분할정복에 대한 개념이 확실히 잡히지 않은상태에서 단순 재귀로 구현해서, 계속된 메모리초과..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 시간초과로 굉장히 고생을 많이 했던 문제입니다. 제가 시간초과가 발생한 이유를 확인해보면서 문제에 접근해보도록 하겠습니다. 해당문제는 최소힙, 최대힙 문제를 구현했으면, heap 자료구조를 이용하여 문제에 접근하면 됩니다. 그러나, 절댓값을 고려해야 하므로, 적절한 정렬방법이 요구됩니다. 해당문제는 절댓값과 입력값을 동시에 heap에 push하여 정렬하는 접근이 필요로 되는 ..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제에서 좌표압축은 임의의 좌표 x1이 있을 때, 이 좌표보다 작은 좌표의 개수를 출력하는 문제입니다. 그렇기 때문에 좌표끼리 서로 비교를 해야 합니다. 따라서 효율적인 비교를 하기 위해 정렬을 통해 문제에 접근하고자 했습니다. ex) (3, 8, 5) -> (3, 5, 8) (3, 3, 2) -> (2, 3, 3) 그러나 이러한 정렬에서 문제는 ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제를 보고 최대, 최소를 물어보는 점을 파악하여 그리디 알고리즘을 이용해야 겠다고 생각했다. 보통 그리디 알고리즘같은 경우 정렬을 통해 해당상황에서의 최선의 경우를 택함으로 해당 문제도 그렇게 접근하려고 했다. 회의를 최대한 많이 하기 위해서는 끝나는 시간을 우선적으로 고려해야 하는데, 그러한 이유로는 시작 시간으로 정렬하여 문제에 접근하면, 끝나는 시간이 제각각이라, (1, 10), (2, 4), (5, 6) 같은 경우 회의를 1번밖에 못하는 결과가 초례된다. 따라서 끝나는 시간을 우선적으로 고려해야한다. ※..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 전형적인 DFS, BFS로 구현하는 문제입니다. 여기서 요구하는 것은 1번 노드에서 연결된(문제에서는 감염시키는) 노드의 총 개수를 구하는 문제와 동일합니다. 단, 1번 노드 자신은 제외하고 출력해야 하므로 최종 출력 시 주의 해야합니다. ※ 고려사항 1. 입출력처리 및 노드와 간선 배열처리 2. DFS 또는 BFS 구현 3. 최종 출력시 1번 노드 제외 1. 입출력처리 및 노드와 간선 배열처리 먼저 ..