본문 바로가기
300x250

Algorithm13

[BOJ 1240][c++] 노드사이의 거리 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net dfs,bfs문제이다. 루트로부터 각 노드까지의 거리를 구하고, 공통 부분을 빼주면 된다. 코드는 아래에 있다. 더보기 #include using namespace std; vector g[1001]; bool c(pair a,pair b){return a.first> n >> m; for(int i=1;i> f >> t >> c; g[f].push_back(make_pair(.. 2023. 8. 3.
[C++][BOJ 11725] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net BFS로 풀 수도 있고, DFS로도 풀 수 있는 문제다. 아직 방문하지 않은 정점인 경우 현재 방문 노드를 아직 방문하지 않은 노드의 부모로 check하고 방문 여부를 true로 바꿔주면 되는 문제다. 주의 사항으로는 c++에서 endl을 사용하는 경우에는 cout과정에서 시간을 오래 잡아먹어 시간초과가 나오므로 \n을 사용해야 한다. 코드는 아래에 있다. dfs 코드 더보기 #include using namespace std; vector graph[1000.. 2023. 5. 23.
[Python][BOJ 6951] Packet Routing https://www.acmicpc.net/problem/6951 6951번: Packet Routing The date is October 29th, 1969. Today, scientists at UCLA made history by exchanging data between two computers over a network. The transmission wasn't very spectacular: only the first two letters of the word login were received before the system crashed. www.acmicpc.net 엄청 쉬운 Floyd-warshall 문제이다. n개의 정점에 w개의 간선정보을 받고 계산 후 p개의 질문에 대답하면 되.. 2023. 3. 13.
[Python][BOJ 2862] 수학 게임 https://www.acmicpc.net/problem/2862 2862번: 수학 게임 동전의 개수가 4개일 때, 상덕이가 첫 번째 턴에서 가져갈 수 있는 동전의 경우의 수는 1, 2, 3, 4개이다. 만약 4개를 가져가게 된다면 상덕이는 항상 이기게 된다. 하지만, 이것은 최솟값이 아니다. www.acmicpc.net 저번에 풀었던 fibonacci game과 같은 유형의 문제이다. 증명을 하면 이도 똑같이 돌의 수보다 작은 피보나치 수 중에서 가장 큰 수만큼 돌을 가져가야 이기는 문제다. https://ujoon.tistory.com/4 [python][BOJ2373] Fibonacci Game https://www.acmicpc.net/problem/2373 2373번: Fibonacci Game.. 2023. 3. 11.
[Python][BOJ 14938] 서강그라운드 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 플로이드 워셜, 데이크스트라, 브루트포스의 응용문제다. 나는 플로이드 워셜을 사용했는데, 각 정점에서 다른 정점으로 가는 길이를 모두 구해놓고 탐색 범위 m보다 길이가 작은 수들의 아이템 개수를 저장하고, 각 정점에서 모을 수 있는 아이템 개수들 중에서 최대값을 출력하면 되는 문제다. 코드는 아래에 있다. 더보기 n,m,r=map(int,input().split()) t=[0]+list(map(int,.. 2023. 3. 11.
[python][BOJ15973] 두 박스 https://www.acmicpc.net/problem/15973 15973번: 두 박스 표준 입력으로 두 박스의 정보가 한 줄에 하나씩 주어진다. 각 박스의 정보는 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)로 구성되는데 이들 좌푯값 x1, y1, x2, y2 (x1 < x2, y1 < y2) www.acmicpc.net 2018년 정올 중등부 1번 문제지만, 단순 구현문제다. 물론 구현할 때 조건문이 조금 길어 귀찮다. NULL인 경우, POINT인 경우, LINE인 경우를 판단하고 나머지는 FACE로 처리해주면 풀린다. 코드는 아래에 있다. 더보기 a=list(map(int,input().split())) b=list(map(int,input().split()).. 2023. 2. 18.
300x250

티스토리툴바