백준

[11725] 트리의 부모 찾기(C++)

문제 [11725] 트리의 부모 찾기 해결 방법 이 문제도 전형적인 dfs, bfs 문제이다. 한 가지, 현재 노드의 부모 노드가 몇번인지 저장할 배열만 추가하면 된다. 나는 인접리스를 활용한 dfs로 구현하였는데, 인접한 노드를 모두 입력받은 후 리스트의 형태는 아래와 같다. 노드 1 6 4 2 4 3 6 5 4 1 2 7 5 3 6 1 3 7 4 1번 노드부터 탐색을 시작하는데, 1번 노드와 연결된 노드는 무조건 1번 노드의 자식임을 알아두자. 또한, 나와 연결된 노드는 나의 부모이거나 자식이거나 둘중 하나임을 기억하자. 탐색을 하면서 나와 연결되어있지만 이미 방문한 노드는 부모노드이고, 그렇지 않은 노드는 부모 노드가 아니기에 자식노드로 판단하고 부모로 저장해주면 된다! 내 코드(C++) // [1..

[1049] 기타줄

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 🔎 해결 방법 정렬을 한 후 제일 첫번째 원소를 취하던지, 아니면 입력받을 때마다 비교를 하던지 해서 패키지 가격의 최솟값과 낱개 가격의 최솟값을 찾아야 한다. 그리고 이 두 개의 값만 사용하면 문제를 풀 수 있다! 1. 모두 낱개로 사는게 제일 싼 경우 예를 들어 가장 싼 패키지 가격이 24, 가장 싼 낱개의 가격이 3이라면 항상 낱개로 사는 것이 더 이득이다. 따라서 (가장 싼 낱개 가격)..

[2437] 저울(C++)

🎅🏻 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 🧣 해결 방법 예를 들어 추의 무게가 (3, 1, 6, 2, 7, 30, 1) 이렇게 주어졌다면 오름차순 정렬을 하고 처음부터 각 인덱스까지의 추의 무게를 합한 sum 은 아래의 표와 같다. sum = 처음부터 각 인덱스까지의 추의 무게의 합 즉, sum에 저장된 값에 해당하는 무게까지는 우리가 만들 수 있다는 뜻이 된다. ex) sum = 7이면 무게가 1인 것부터 7인 것까지 모두 만들 수 있다는 뜻 i가 4일때부터 한번 차근차근 봐보자. 1) i = 4,..

[1309] 동물원

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 💧 해결 방법 N이 1일 때, 2일 때, 3일 때, 4일 때.... 를 차근차근 계산해보면 규칙성을 바로 발견할 수 있다. dp[i] = 2(가로) * i(세로) 크기의 동물원에 사자를 배치하는 방법의 수 라고 한다면 dp[0] = 1 dp[1] = 3 dp[2] = 7 dp[3] = 20 dp[4] = 41 . . . 즉, 아래와 같은 점화식이 성립하는 것을 알 수 있다. dp[i] = dp[i - 1]*2 + dp[i - 2] ☂️ 내 코드 // [1309] 동물원 // https://www.acmicpc.net/problem/1309 // dp #include int main(void) {..

[1157] 단어 공부

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net alpha 배열을 초기화해줘야 한다는 것은 생각도 못하고 엄한 것만 고치다가 오답률만 더 늘어버렸다. ㅎㅎ 항상 변수 선언하면 초기화부터 하고 사용하자... 한 가지 주의해야 할 점❗️ 문자를 알파벳으로 출력하고 싶은 경우 printf 함수를 쓰면 "%c"로 출력만 해주면 되지만 cout으로 출력하는 경우에는 출력문에서 타입 변환을 할 수 없기 때문에 사전에 원하는 타입으로 선언한 변수에 값을 저장해서 형 변환을 해준 뒤에 출력해..

[11720] 숫자의 합(C / C++)

https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 🧩 내 코드 Ver.1(C) // [11720] 숫자의 합 // https://www.acmicpc.net/problem/11720 #include int main(void) { int n, sum = 0; char arr[101]; scanf("%d", &n); scanf("%s", arr); for (int i = 0; i < n; i++) { sum += arr[i] - '0'; } printf("%d", sum); } Ver.2(C++) // [11720] 숫자의 합 //..

[11724] 연결 요소의 개수

문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 내 코드(C / C++) Ver.1(C++) // [11724] 연결 요소의 개수 // https://www.acmicpc.net/problem/1260 #include #include #include #include #define MAX 1001 using namespace std; bool visit[MAX]; vectorlist[MAX]; void dfs(int start); int cc..

[4344] 평균은 넘겠지

https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 문제 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 입력 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 � www.acmicpc.net 🏖 내 코드(C) // [4344] 평균은 넘겠지 // https://www.acmicpc.net/problem/4344 #include int main(void) { int c, n; scanf("%d", &c); while(c) { // 학생 N명 점수, 점수 총합, 평균, 평균 이상인 학생들의 수 int score[1001], sum = 0, mean, cnt = 0; scanf("%d",..