https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인 www.acmicpc.net 1. Logic 세그트리를 처음 공부하고 2번째로 푸는 문제이다. 기본 세그트리 문제랑 비슷하지만 pair을 활용하여 {value, index}를 같이 저장해서 풀이했다. 2. Code #include using namespace std; const int INF = 0x3f3f3f3f; int n, m; int ..
분류 전체보기
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. Logic 나를 이분그래프에 처음 입문시켜준 문제이다. 이분그래프란 서로 인접한 노드를 다른 그룹으로 묶을 때 서로 겹치지 않고 두개의 그룹으로 정확히 나눠지는 그래프의 형태를 말한다. 아래의 두번째 그림을 보면 좌측 노드 3개를 l1, l2, l3 / 우측 노드 3개를 r1, r2, r3라고 했을 때 우측에서 처음 시작하면 l1이 1번 그룹 서로 인접한 r1, r2, r3는 -1번 그룹 다..
https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. Logic 6,9는 뒤집어서 사용할 수 있는점을 조심해서 풀이하면 된다. 만약 6과 9의 갯수가 짝수가 나온다면 2로 나눈 갯수만큼 세트를 사용하면 되지만, 홀수가 나온다면 반올림을 한 갯수만큼 사용해야 한다. 2. Code #include using namespace std; int numCnt[9]; int main() { int n; cin >> n; while(n) { int temp = n % 10; if(temp == 6 || temp == 9) { numCnt[6]++; } e..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. Logic 처음에 문제를 무조건 k번 말처럼 이동한 후 기회를 다 쓰고 4방향으로 이동하는 줄 알고 냅다 2차원 방문배열을 만들어서 BFS돌렸더니 당연히 틀렸다. 문제의 의도는 목적지에 도달하기 전까지 k번 이하로 능력을 사용하여 도착하는것이기 때문에 4방향으로 먼저 돌고 능력을 사용해도 된다. 즉 처음위치에서 능력을 쓰고 x칸으로 이동한 것과 능력을 안쓴상태로 x칸으로 이동..
https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 1. Logic 문제에서 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 "인접하여 서로 연결"되어있다고 했기 때문에 그래프를 떠올릴 수 있다. 더해서 상, 하, 좌, 우, 대각선이기 때문에 8방향 BFS 또는 DFS로 풀이해줄 수 있다. 풀이 과정은 1. 입력받기 2. 1과 동시에 방문하지 않은 좌표 방문하기 3. bfs or dfs에서 8방향 확인해서 1, 미방문 좌표 들어가기 4. 함수 호출한 횟수 count C++은 BFS로 파이썬은 연습중이라 BFS, DFS 두가지 방법 모두 풀이해봤다...
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 1. Logic C++로 풀이할 때는 좌우로 큐를 회전시켜야 할 때 직접 빼고 넣어줘야 하기 때문에 움직여야 할 숫자가 음수인지 양수인지에 따라 경우를 나눠서 풀이했다. 하지만 파이썬으로 풀이할 때는 파이썬 queue에는 rotate라는 함수가 있기 때문에 훨씬 쉽게 구현할 수 있었다. rotate 함수는 안에 들어가는 인자가 양수이면 큐 안의 인자들을 오른쪽으로 절댓값만큼 이동..
https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 1. Logic 정렬한 후 투포인터를 사용해서 m과 같은 갯수를 카운트해주면 된다. 2. Code c++ #include using namespace std; int n, m; int ingredient[10000000]; int solve() { int left = 0; int right = n-1; int cnt = 0; while(left < right) { if(i..
https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 1. Logic 경우의 수를 나눠보게 되면 인사를 할때와 안할 때 두가지의 경우의 수로 분류할 수 있다. 각 인사를 할지 말지에 대한 고민을 풀이해야 하기 때문에 배낭 문제(KnapSack Problem)라고 볼 수 있다. 2. Code C++ #include using namespace std; int n; int dp[21][101]; int lose[20]; int delight[20]; ..
https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. Logic 기본적인 BFS문제이다. 처음 방문하는게 가장 최단거리기 때문에 vis배열을 통해 queue에 들어가는 갯수를 줄여주면서 BFS를 진행하면 된다. 2. Code c++ #include using namespace std; int n; int arr[1001]; bool vis[1001]; int bfs() { queue q; int ans = 0x3f3f3f3f; q.p..
https://www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n n; while(n--) { unordered_map land; long long cur; cin >> cur; long long landNum; long long maxNum = -1; for(int i = 0; i > num; land[num]++; if(land[num] > maxNum) { maxNum = land[num]; landNum = num; } } if(maxNum > cur/2) cout
