본문 바로가기
반응형

백준499

백준 5052 전화번호 목록 c++ (트라이) 문제 출처 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 .. 2021. 8. 3.
백준 12103 짝합 수열 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/12103 12103번: 짝합 수열 정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다. 당신은 수열에 있는 몇 개의 원소를 원 www.acmicpc.net 문제 정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다. 당신은 수열에 있는 몇 개의 원소를 원하는 정수로 바꿀 수 있다. 최소 몇 개의 원소를 바꿔야지 수열을 k.. 2021. 8. 2.
백준 7976 수열 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/7976 7976번: 수열 정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다. 당신은 수열에 있는 몇 개의 원소를 원하 www.acmicpc.net 문제 정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다. 당신은 수열에 있는 몇 개의 원소를 원하는 정수로 바꿀 수 있다. 최소 몇 개의 원소를 바꿔야지 수열을 k-짝합 .. 2021. 8. 1.
백준 18513 샘터 c++ (bfs) 문제 출처 : https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 문제 일직선 상의 공간에 N개의 샘터가 존재하며, K채의 집을 짓고자 한다. 모든 샘터 및 집이 존재하는 위치는 항상 정수 형태이다. 이때 일직선 상의 공간에서 N개의 샘터 및 K채의 집들은 모두 서로 다른 위치에 존재한다. 다시 말해 하나의 위치에는 샘터가 있거나, 집이 있거나, 혹은 아무것도 없다. K채의 집을 지을 때, 가능하면 샘터의 주변에 집들.. 2021. 7. 31.
백준 11725 트리의 부모 찾기 c++ (dfs) 문제 출처 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 알고리즘 분류 그래프 이론 그래프 탐색 트리 너비 우선 탐색 깊이 우선 탐색 풀이.. 2021. 7. 29.
백준 1325 효율적인 해킹 c++ (dfs) 문제 출처 : https://www.acmicpc.net/problem/1325 3이다. 따라서 graph[1].push_back(3)을 해준다. 단방향 그래프이기 때문에 반대로 연결은 하지 않는다. ※인접 행렬 그래프보다 인접 리스트 그래프가 메모리 부분에서 효율적이기 때문에 웬만하면 인접 리스트 그래프를 사용 하는 습관을 들이자. 해당 문제에서도 인접 행렬 그래프를 사용하면 메모리 초과가 뜬다고 한다. 그래프를 연결해 주고, 모든 노드를 탐색하여 카운트와 노드 번호를 배열에 저장한다. vector에 저장하고 algorithm헤더의 sort를 커스텀하는 방법도 있지만, 본인은 우선순위큐에 저장하고, 우선순위큐의 sort 방식을 커스텀했다. 이후 가장 높은 카운트(큐의 맨 앞)와 같은 노드 번호들을 오름.. 2021. 7. 29.
백준 7569 토마토 c++ (bfs) 문제 출처 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토.. 2021. 7. 29.
백준 2636 치즈 c++ (bfs) 문제 출처 : https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구.. 2021. 7. 28.
백준 16234 인구 이동 c++ (bfs) 문제 출처 : https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이.. 2021. 7. 28.
반응형

티스토리툴바