컴공과고씨

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 간단 정리 지민이가 여러 개의 파티에 감. 파티마다 참석하는 사람이 주어짐. 지민이가 거짓말을 할 건데 진실을 아는 사람이 주어짐. 진실을 아는 사람에게 거짓말을 하면 안됨. 또한 어느 파티에서는 거짓을 듣고 다른 파티에서 진실을 듣는 것도 안됨. 즉, 거짓말이라는 것을 아무도 알아채지 못하게 거짓말을 많이 할 수 있는 파티의 개수를 구하라. 문제 해결 방법 이 문제 같은 경우 유니온 파인드를 쓰면 쉽..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 간단 정리 정말 간단하다 a,b,c가 주어짐. a^b을 구하는 문제임. 단 a^b값이 너무 클 수 있으니 c로 나눈 나머지를 구하면됨. 문제 해결 방법 일단 나머지 정리를 알아야함. 나머지 정리는 그냥 간단하게 그냥 ((a%c) * (b%c) %c) 하고 (a*b)%c 같다. 즉, 이런 문제가 나오면 그냥 나머지 구하고 곱해주고 나머지 구해주면 된다. 제한 시간이 2초이기 때문에 1초에 3~5억번 연산을 한다고 했을 때 문제의 주어진 수가 최대 21억이기 ..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 정리 1. 행렬이 주어짐. 2. 시작 좌표 (x1,y1)이 주어지고 도착 좌표 (x2,y2)가 주어짐 3. 좌표 사이에 있는 값의 합들을 구해야함. 예를 들어 초록색이 시작 좌표, 파란색이 끝 좌표라고 하면 저런식으로 보라색 빗금의 부분의 합들을 구해주면됨. 문제 해결 방법 그 전 구간 합 구하기를 해보면 알듯이 일일이 for문을 돌리면서 구해주면 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 정리 n개의 숫자가 주어짐 구간이 주어지면 그 구간안에 있는 숫자의 합을 구하라. 문제 해결 방법 무작정 구간이 주어질때마다 더하게 되면 시간 초과가 남. 숫자가 주어질때마다 거기까지의 합을 구해놈. 그 후 구간이 주어지면 마지막 구간까지의 합에서 시작 구간 전까지의 합을 빼주면 됨. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 간단 정리. 상어가 물고기를 먹으러 다님. 상어는 물고기의 크기보다 크면 물고기를 먹을 수 있음. 크기가 같다면 지나갈 수만 있음. -> 작으면 못지나 감. 물고기를 먹으면 그 칸은 빈칸이 됨. 상어가 한 크기에서 물고기를 먹은 횟수와 상어의 크기가 같게 되면 상어 크기가 1 증가함. 물고기를 먹을 때는 가장 작은 것을 우선으로 먹고 같은 크기가 많다면 가장 위쪽 우선 그 다음은 왼쪽..

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 문제 정리 I와 O가 반복된 배열이 주어짐. 1: IOI 2: IOIOI 3: IOIOIOI 이런 식으로 반복되는 수열의 길이 N이 주어짐. 배열안에 N으로 이루어진 IOI가 얼마나 있는지 구함. 예를 들어 N이 4라는 것은 IOIOIOIOI 이 부분이 배열에 얼마나 있냐는 것이다. 주어진 배열이 OOOIOIOIOIOIOIOOO라..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 정리 배열이 주어짐. 명령어가 주어짐. 명령어는 문자열 형태로 R은 배열 뒤집기 D는 배열의 맨 앞 원소 빼기 두 가지로 구성됨. 명령어를 수행후 남은 배열 원소를 구해라. 단, 원소가 없을 때 D가 수행되면 error를 출력하라. 문제 해결 방법 이 문제 같은 경우는 deque를 이용해서 풀 수 있습니다. 저 같은 경우는 인덱스를 조작을 이용해서 deque를 사용하지 않고 풀었습니다. deque는 queue와 비슷하지만 다른 점은 양쪽에서 pop..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 정리 바둑판이 주어지고 각 칸에는 숫자가 써있음. 여기에 4칸으로 이루어진 도형 5개 주어짐. 바둑판에 도형 한 개를 놓아서 놓아진 칸의 숫자 합이 최대가 되도록 만들어라. 문제 해결 방법 이 문제를 해결하는 방법은 대표적으로 DFS를 사용하는 방법이 있습니다. 제가 처음 푼 방법은 DFS를 쓰지 않고 풀었습니다. 하지만 DFS를 쓰는 방법에 대해 설명하고 제가 푼 방법을 설명하도록 하겠습니..

https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 이 문제 같은 경우 제약 조건이 많아 차근차근 조건을 생각해 나가야 풀 수 있는 문제 였습니다. 문제 정리 바둑판 있음. 바둑판 가장자리는 벽으로 막혀있고 중간 중간에 벽이 있을 수 있음. 바둑판에 빨강, 파랑 1개씩 구슬 주어지고 구슬이 빠지는 구멍이 주어짐. 바둑판을 상하좌우로 기울일 수 있음. 바둑판을 기울이면 그 방향 끝까지 감. (구슬은 곂쳐..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 정리 바둑판 모양이 있음. 각 방 마다 지나갈 수 있는 방과 없는 방으로 나뉨. 갈수 없는 방은 뚫 수 있음. (0,0) 에서 (n-1,n-1)까지 가는데 방을 최소한으로 뚫어서 갈 때 몇 개를 뚫어야 하는가? 문제 해결 방법 BFS를 사용해서 탐색을 하는데 각 방 마다 뚫고 온 방의 개수를 적어서 BFS 탐색을 해주면 됩니다. 방의 초기 값은 크게 잡아 줍니다. 그 후 시작점은 0으로 해줍..