오구의코딩모험

https://www.acmicpc.net/problem/15724 문제 3줄 요약1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.2. 4개의 숫자로 직사각형 범위를 알려준다.3. 해당 직사각형 범위의 내에 살고 있는 사람 수를 구해보자.  DP가 아닌 완전 탐색으로 처음 접근했더니시간 초과로 통과가 되지 않았다..! 직사각형의 시작 좌표와 (1,1)가고정이 아니기에 DP 테이블을 사용할 수 있나? 에 대한의문이 생겼다. 결국 코딩도사인 GPT에게DP를 어느 부분에 적용하면 좋을지 도움을 받았다.  DP 테이블에 (1, 1)부터 해당 좌표까지의직사각형 합을 저장(메모이제이션) 해두는 것이었다. 그 후(1, 1) 부터 (x1, y1) 의 인원 수와(1, 1) 부터 (x2, y2) 의 인원 수..

https://www.acmicpc.net/problem/22942  문제 3줄 요약 1. 원의 중심이 x축 위에 존재하는 원들이 존재 한다.2. N개의 원들의 중심 x좌표와 반지름이 주어진다.3. 각 원들이 서로 교점이 생기는지 않는지 확인해봐라.  문제에서 N의 최대 값이 200,000 으로원을 하나 받을 때마다 그려진 원들을 전부 비교하기엔N(N-1)/2 정도의 연산이 필요하니대충 계산해봐도 200억 번의 연산이 필요하다.  따라서원이 그려질 때마다 겹치는지 겹치지 않는지범위 값을 담아두고 비교하는 형식이 필요할 것이다. 일단원의 중심 좌표, 반지름을 통해각 원의 최소 좌표와 최대 좌표를 vector에 담아 비교 연산에 필요한 값들을 세팅해주었다. int n;cin >> n;vector> circl..

https://www.acmicpc.net/problem/1991 문제 3줄 요약 1. 이진 트리의 순회 결과를 출력한다.2. 전위 / 중위 / 후위 순으로 순회할 것이다.3. 순회 방법은 순회 결과가 힌트!  학부 수업 때,트리 순회를 외우려고 친구들과 고민하던 중친구 한 명이 알려줬던 방법이 기억에 잘 남아서 아직도 잊혀지지 않는다..! 그 방법은트리에 막대기를 붙여서 경로를 이어주는 방법이었다. 전위 순회는 막대를 각 노드의 왼쪽,중위 순회는 막대를 각 노드의 아래쪽,후위 순회는 막대를 각 노드의 오른쪽에 붙여주고 경로를 이어주면막대기의 순서가 순회 결과 순으로 된다는 것이었다. 예를 들어,위의 이진 트리의 중위 순회를 해본다면  막대기는 순회 방식에 따라 다르게 설정해준다.하지만 경로는 항상 왼쪽..

https://www.acmicpc.net/problem/5567 문제 3줄 요약 1. 상근이는 결혼식에 자신의 친구 + 친구의 친구까지만 초대한다.2. 친구의 친구의 친구는? 안된다.3. 친구 관계 리스트를 보고 몇 명을 초대해야할 지 구해보자!  C++를 공부를 시작한지 얼마 되지 않아아직 알고리즘 문제푸는게 익숙하지 않다고 느껴다시 차근차근 푼 문제들을 블로그에 작성해야겠다.  처음에는 재귀 DFS를 사용하여 문제에 접근했는데,Depth 처리가 생각보다 쉽지 않다고 느껴서BFS로 바꿔서 풀었다. 제출한 코드가 길지 않으니일단 필자의 데이터 입출력 부분부터 확인해보자! int main(void){ ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ ..

https://www.acmicpc.net/problem/1926  문제 3줄 요약1. 도화지에 그림이 그려진 부분은 1, 그려지지 않은 부분은 0으로 표시되어 있다.2. 1로 연결된 것은 한 그림이라 정의한다. 대각선 연결은 예외, 가로/세로 연결만 해당3. 그림의 개수와 가장 큰 그림의 넓이(포함된 1의 개수)를 출력하라. BFS와 DFS를 사용한다면큰 어려움 없이 풀 수 있는 문제라고 느껴졌다. BFS와 DFS의 차이를 잘 모르고 계시다면,아래 글을 참고하면 좋을 것 같다! https://59travel.tistory.com/76 [Python] 1260번 : DFS와 BFShttps://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 3줄 요약 1. 1은 길, 0은 벽 2. 좌측 상단에서 시작해서 우측 하단으로 이동한다. 3. 미로를 탈출하는 최소의 이동 칸 수를 구해라 문제가 매우 익숙하다! 전에 풀었던 델타 탐색을 사용하면 될 것 같은데, 델타 탐색이 뭔지 궁금하다면? https://59travel.tistory.com/77 [Python] 2667번 : 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 3줄 요약 1. 0 부터 10만까지의 좌표에 수빈이와 동생이 숨바꼭질을 한다. 2. 수빈이는 1초에 한번, 뒤로 걷기(-1), 앞으로 걷기(+1), 순간이동(*2) 중 하나를 하여 동생을 찾는다. 3. 동생이 있는 좌표에 수빈이가 도달하는 가장 빠른 시간을 출력한다. 예시를 통해 문제를 접근해보자. EX) 수빈 : 5, 동생 : 17 일 때, 왼쪽 걷기, 오른쪽 걷..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 3줄 요약 1. 정사각형 모양의 지도가 있다. 2. 집이 있는 곳은 1, 없는 곳은 0을 표시한다. 3. 집의 모임을 단지라고 정의하는데, 단지수를 출력하고 속하는 집의 수를 오름차수으로 정렬하라! 예시를 보면 이해하기 수월하다. 1의 모임을 단지라고 부르고, 단지수를 먼저 출력한다. 위의 에서는 3 단지가 있는 것을 볼 수 있다. 다음은 단지에 속하는 집의 수를 출력하는데, 단지 1은 7 가..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 3줄 요약 1. 그래프를 DFS와 BFS로 탐색한 결과를 출력한다. 2. 여러 정점을 방문할 수 있는 경우, 작은 번호부터 방문 3. 정점 번호는 1번부터 N번까지이다. 알고리즘하면 빠질 수 없는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 구현문제다! 간단하게 DFS와 BFS의 차이를 본다면, DFS의 경우, 부모 노드 이후에 (2) 자식 노드의..

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 문제 3줄 요약 1. 1보다 큰 제곱수(2, 4, ..)로 나누어 떨어지지 않는 수가 있다. 2. 그 수를 제곱ㄴㄴ수라고 한다. 3. 주어진 두 정수 사이의 제곱ㄴㄴ수가 몇 개 있는지 출력! 문제 이름이 제곱ㄴㄴ수 이기 때문에 제곱이 중요한 문제처럼 보이지만 저번에 풀었던 환상의 짝꿍과 마찬가지로 소수와 관련된 문제이다. 왜 소수랑 관련이 있을까? 차근차근 알아보자! 제곱수에는 다..