오구의코딩모험

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. 주어진 두 정수 사이의 제곱ㄴㄴ수가 몇 개 있는지 출력! 문제 이름이 제곱ㄴㄴ수 이기 때문에 제곱이 중요한 문제처럼 보이지만 저번에 풀었던 환상의 짝꿍과 마찬가지로 소수와 관련된 문제이다. 왜 소수랑 관련이 있을까? 차근차근 알아보자! 제곱수에는 다..

https://www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 문제 3줄 요약 1. 두 사람은 각각 인연의 증표로 끈을 갖고 있다. 2. 두 끈을 이어붙이고 다시 길이가 소수인 끈 두개로 정확히 나눈다. 3. 나누는 것이 가능하다면, 환상의 짝꿍! 오늘도 저번 골드바흐의 추측에 이어 소수와 관련된 문제를 풀고자한다. 2023.03.07 - [프로그래밍 공부/백준 알고리즘] - [Python] 6588번 : 골드바흐의 추측 [Python] 6588번 : 골드바흐의..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 문제 3줄 요약 1. 수백년 전, 골드바흐는 추측했다. 2. "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 3. 백만 이하의 모든 짝수에 대해 검증해봐라 8은 3 + 5 로 나타낼 수 있다. 42는 나타낼 수 있는 경우가 많은데, 만들 수 있는 방법이 여러 가지인 경우는 두 수의 차가 가장 큰 것을 출력한다. 또한 소수의 합으로 나타낼 수 없다면, 문자..