[백준 / C언어] 14888번: 연산자 끼워넣기 (삼성 SW 기출)

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 브루트포스 알고리즘, 백트래킹 접근 방법 N개의 수 사이 N - 1개의 자리에 모두 들어갈 수 있는 N - 1개의 연산자가 주어지고, 연산은 연산자 우선순위를 무시하고 앞에서부터 진행되므로, 직접 다 하나씩 집어넣어보는 브루트포스 알고리즘을 사용한다. 구현 N개의 수를 저장할 배열 A와 각..

• format_list_bulleted PS/백준
• · 2023. 7. 9.
• textsms

[백준 / C언어] 11723번: 집합

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 난이도: solved.ac 실버 5 알고리즘 분류 구현, 비트마스킹 접근 방법 찾고자 하는 숫자의 번호를 index로 갖는 배열의 값을 1 또는 0으로 두어 집합 내 숫자의 유무를 확인할 수 있다. set[5] = 1은 숫자 5가 집합 S에 있다는 것을 의미하고 set[5] = 0은 숫자 5가 집합 S에 없다는 것을 의미한다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include int se..

• format_list_bulleted PS/백준
• · 2023. 7. 8.
• textsms

[백준 / C언어] 2617번: 구슬 찾기 (DFS 풀이)

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (DFS) 접근 방법 및 구현 무게가 중간이 될 수 없는 구슬은 해당 구슬보다 더 가볍거나 무거운 구슬의 개수가 N / 2개보다 많아야 한다. 더 가볍거나 무거운 구슬의 개수는 DFS를 이용해 구할 수 있다. 입력으로 들어오는 구슬의 관계는 2차원 배열을 이용해 방향그래프로 나타내었다. 아래와 같은 입력이 주어진다고 ..

• format_list_bulleted PS/백준
• · 2023. 7. 8.
• textsms

[백준 / C언어] 18870번: 좌표 압축 (구조체 이용)

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 정렬, 값 / 좌표 압축 접근 방법 및 구현 Coord라고 하는 구조체(struct)를 만들어 배열로 만들어주었다. 이 구조체의 원소는 x, loc, compress가 있는데, 각각 입력받은 숫자, 입력받은 순서, 압축된 숫자를 의미한다. 좌표 압축을 하기 위한 순서는 다음과 같다. 1. 값(x)..

• format_list_bulleted PS/백준
• · 2023. 7. 7.
• textsms

[백준 / C언어] 11659번: 구간 합 구하기 4 (Prefix Sum 알고리즘)

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 누적 합 접근 방법 위의 성질을 이용한다. 위의 성질을 이용하면, i번째 수부터 j번째 수의 합을 S로 나타낼 수 있다. 따라서 아래와 같은 식이 도출된다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include int main() { int N, M, i, j, temp; scanf(..

• format_list_bulleted PS
• · 2023. 7. 7.
• textsms

[백준 / C언어] 14891번: 톱니바퀴 (삼성 SW 기출)

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 시뮬레이션 접근 방법 한 톱니바퀴의 양 옆 톱니바퀴는 반대 방향으로 돈다. 예를 들어 3번 톱니바퀴가 시계 방향으로 돈다면, 2번 톱니바퀴와 4번 톱니바퀴는 반시계 방향으로 돈다. 그리고 톱니바퀴의 톱니는 8개로 이루어져 있으며, 앞 톱니바퀴의 3번째 톱니(3시 방향)와 현재 톱니바퀴의 7번째 톱니(9시 방향)가 서로 맞닿아있다. 맞닿아..

• format_list_bulleted PS/백준
• · 2023. 7. 7.
• textsms