본문 바로가기
728x90

ALGORITHM/C++ - 백준28

[백준 7576] 토마토 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 분석 토마토가 들어 있는 상자가 하나 있고, 한칸의 하나의 토마토 혹은 비어 있는 칸도 존재한다. 익은 토마토는 위, 아래, 오른쪽, 왼쪽의 토마토를 익게할 수 있고, 비어있다면 익지 않는다. 모든 토마토를 익게 하려면 얼마의 시간이 필요한지 구하는 문제이다. 알고리즘 설계 우선 입력을 받아 토마토를 담아둘 상자를 입력 받는다. 1로 되어 익어있는 토마토는 queue에 .. 2023. 10. 19.
[백준 24446] 알고리즘 수업 - 너비 우선 탐색 3 문제 https://www.acmicpc.net/problem/24446 24446번: 알고리즘 수업 - 너비 우선 탐색 3 너비 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2, 4번 노드이다. 3번 노드는 2번 또는 4번 노드의 자식이다. 5번 노드는 1번 노드에서 방문 될 수 없다. www.acmicpc.net 문제 분석 무방향 그래프를 만들고 시작 정점부터 BFS를 돌려준다. 시작 정점을 0으로 다음으로 방문하는 노드는 1, 그다음은 2이렇게 1식 올라간 것을 출력한다. 여기서 방문하지 않은 노드는 -1로 표시한다. 알고리즘 설계 정점의 수, 간선의 수, 시작 정점을 입력 받는다. 어떤 노드끼리 연결되어 있는지 확인하기 위하여 이중vector.. 2023. 10. 19.
[백준 5635] 생일 문제 https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 학생의 수를 입력 받고 학생의 수에 맞춰 이름과 생일을 입력 받는다. 가장 나이가 어린 사람의 이름과 가장 나이가 적은 사람의 이름을 출력한다. 알고리즘 설계 priority_queue를 2개 만들어 오름차순으로 정렬되는 것과, 내림차순으로 정렬되는 것을 만든다. 학생의 수를 입력 받아 반복문을 돌려주고 학생의 이름과 생일을 입력 받는다. 19990101이 생일인 사람보다 20000101인 사람이 더 나이가 어린 것에서 착안하여 년도, 월, 일 순으로 배치하여.. 2023. 10. 19.
[백준 11047] 동전 0 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 분석 동전의 개수와 총 만들어야하는 돈을 입력 받는다. 이후 동전의 가치가 정해진다. 이 동전의 가치로 총 만들어야하는 돈을 만들어야하고, 동전을 가장 적게 써야한다. 알고리즘 설계 동전의 개수와 만들어야하는 돈을 입력 받는다. 이후 vector에 동전들의 가치를 입력 받는다. 만들어야하는 돈이 0이 아니라면 계속 반복문을.. 2023. 10. 19.
[백준 1991] 트리 순회 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 분석 입력 받아 트리를 만들고 그 트리를 전위, 중위, 후위 순서대로 순회하여 값을 출력하는 간단한 문제이다. 알고리즘 설계 몇 가지의 노드가 있는지 입력 받고, 노드와 연결된 노드를 입력받아 이중 vector에 넣어준다. 이후 전위, 중위, 후위 순회를 하여 출력해준다. 유의점 전위, 중위, 후위 순회에 간단한 이해가 필요한 문제이다. 코드 #include #include .. 2023. 10. 19.
[백준 5639] 이진 검색 트리 문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 분석 수를 입력 받아 트리 안에 넣어주고, 그 트리를 후위순회한 결과값을 출력하는 문제이다. 알고리즘 설계 Node라는 구조체를 만들어 그 데이터 값, 왼쪽 노드, 오른쪽 노드를 만들어준다. 가장 기본이 되는 rootNode변수를 만든다. 이후 입력을 받으며 처음엔 rootNode에 넣어주고, 처음이 아니라면 Insert함수에 입력 받은 data값과 루트 노드를 넣어준다. .. 2023. 10. 18.
[백준 11725] 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 루트 없는 트리가 주어지고 각각 노드의 부모노드가 무엇인지 출력하는 문제이다. 알고리즘 설계 이중 vector을 사용하여 간단한 트리를 만들어준다. queue에 1을 넣어 큐가 비어있지 않을떄 실행되는 while을 돌려준다. 큐에 있는 노드와 연결된 노드들의 부모 노드를 queue의 처음으로 정해주고, 연결된 노드들을 queue에 넣어준다. 이후 2번째 노드부터 부모노드가 무엇인지 출력한다. 코드 #include #include #include.. 2023. 10. 18.
[백준 1068] 트리 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 분석 노드의 개수가 입력 되고 그 개수에 맞춰 부모 노드가 누구인지 정해준다. 이후 없앨 노드가 입력되고 없앤 상태의 트리에서 리프노드가 몇개인지 세는 문제이다. 알고리즘 설계 이중 vector을 사용하여 간단한 트리를 만들어준다. 루트 노드에서 DFS를 돌린다. DFS에 매개변수로 들어간 수가 지운 노드라면 return해준다. 만약 자식 노드가 없거나, 자식이 하나인데 그 자식이.. 2023. 10. 18.
[백준 1463] 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 분석 수가 입력 되고 그 수가 3으로 나눠지면 3으로 나누고, 2로 나눠지면 2로 나누고, 안 나눠진다면 1을 뺴는 간단한 문제다. 알고리즘 설계 수가 2로 나눠지면 2를 나눈 값을 넣고, 3으로 나눠진다면 3으로 나누고, 다 아니라면 1을 뺸다. 코드 #include #include using namespace std; int main() { int index; queue q; cin >> index; q.push(make_pair(index, 0)); while (!q.empty()) { if (.. 2023. 10. 18.
[백준 5525] IOIOI 문제 https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 분석 우선 n과 m을 입력 받는다. n은 IOI문자열의 크기이다. n이 1이라면 IOI, 3이라면 IOIOIOI이다. m은 확인할 문자열의 크기이다. 받은 문자열에 n에서 입력 받은 크기의 문자가 몇개 있는지 세는 문제이다. 알고리즘 설계 입력 받을 수 있는 것을 모두 입력 받는다. 이후 for문을 돌려 0부터 m, 즉.. 2023. 10. 18.
[백준 14940] 쉬운 최단거리 문제 https://www.acmicpc.net/problem/14940 문제 분석 지도의 크기가 우선 정해진다. 갈 수 없는 곳은 0, 갈 수 있는 곳은 1, 시작 위치는 2로 표시 된다. 2에서 시작하여 좌우양옆으로 방문한 순서를 출력해주는 문제이다. 여기서 갈 수 있는 곳 1인 곳인데 갈 수 없는 곳이라면 -1로 출력한다. 알고리즘 설계 우선 지도의 크기를 정해서 지도를 그린다. 시작 위치는 따로 관리하며 지도엔 0으로 표시한다. 갈 수 있는 곳은 -1로 표시하여 나중에 1번쨰로 도착한 곳과 헷갈리지 않도록 해준다. 이후 BFS를 사용하여 몇번쨰에 도착하였는지 map에 적어준 후 출력한다. 유의점 x축과 y을 착각하지 않고 적는 것이 중요하다. 코드 #include #include using nam.. 2023. 10. 18.
[백준 16928] 뱀과 사다리 게임 문제 https://www.acmicpc.net/problem/16928 문제 분석 1이라는 위치에서 100이라는 위치로 이동하는 문제이다. 다만 주사위로 1~6칸을 갈 수 있으며, 사다리와 뱀이라는 변수가 존재한다. 사다리는 작은 수에서 큰 수로 올라가며, 뱀은 큰 수에서 작은 수로 내려오는 형태이다. 이 문제는 BFS로 풀 수 있다. 알고리즘 설계 방문을 확인할 vector 또는 배열, 사다리 및 뱀을 체크할 vector 또는 배열을 만든다. 이후 사다리와 뱀을 입력받아 연결 시켜준다. 1에서 시작하며 추가로 1 ~ 6을 더하여 계속 방문 확인할 배열과 queue에 넣어준다. 주사위 수에 사다리 또는 뱀이 있다면 움직여준다. 100에 도착하면 while에서 벗어나 몇번쨰에 방문하였는지 확인한다. 유의.. 2023. 10. 18.
728x90

티스토리툴바