컴공과고씨

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 정리 1. 유저가 번호로 주어짐 2. 관계가 주어짐. 관계라는 것은 예를 들어 1 2 이렇게 주어지면 1과 2는 연결되어 있다는 것을 말함. 3. 관계가 1 2 주어지고 2 4 로 주어진다고 치면 1에서 4로 갈때의 단계는 1 2(1단계) 2 4(2단계) 그래서 총 2단계를 걸처 1에서 4가 연결되어 있다고 함. 이 때 다른 사람과의 관계의 총..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 정리 0이 아니면 원소 추가. 0이면 추가된 원소 중 절대값이 가장 작은 원소를 출력 후 제거. 원소의 개수가 0일 경우 0이 입력되면 0을 출력. 문제 해결 방법 우선순위 큐를 떠올리면 간단하게 풀 수 있는 문제이다. 우선 순위 큐를 간단하게 보려면 https://hagisilecoding.tistory.com/60?category=1050177 위 링크에서 간단하게 ..

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/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 이 문제는 굉장히 간단합니다. map 컨테이너를 사용하면 간단히 풀 수 있습니다. 이러한 문제류는 pair같은 것으로 저장 후 탐색을 for문으로 돌리게 되면 시간초과가 나기 때문에 map 컨테이너를 이용해 key값을 찾아주는 것이 시간 복잡도 측면에서 유리합니다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

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/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 정리 몇번 째 해인지 나타내는 방법을 라고 정의 여기서 x와 y의 최대값이 문제에서 주어짐. 예를 들어 m = 10, n = 12 라는 것은 x의 최대값은 10 y의 최대값은 12 1번째 해 = 1,1 2번째 해 = 2,2 이런식으로 해가 최대값을 넘지 않으면 +1 씩 증가 그러다가 최대값을 넘어가면 1로 다시 시작 10번째 해 = 10, 10 11번째 해 = 1, 10 이렇게 넘어감. 이 때 ..

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개씩 구슬 주어지고 구슬이 빠지는 구멍이 주어짐. 바둑판을 상하좌우로 기울일 수 있음. 바둑판을 기울이면 그 방향 끝까지 감. (구슬은 곂쳐..