본문 바로가기

백준84

[1074] Z https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 분할 정복, 재귀 문제이다. 구간을 4개의 작은 정사각형으로 쪼갠다음 Z순서(왼쪽 위 1, 오른쪽 위 2, 왼쪽 아래 3, 오른쪽 아래 4)로 탐색한다. Z순서로 탐색하는 모습이다. 해당 구간에 원하는 좌표가 있다면 그 안에서의 분할 탐색을 진행한다. 코드로 보는게 빠를 것 같아 설명을 줄인다..! #include #include using namespace std; int N; int .. 2022. 11. 12.
[2630] 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할 정복, 재귀 문제이다. 만든 정사각형 안이 모두 같은 색이 될 때까지 쪼개야한다. 0이면 흰색, 1이면 파란색을 뜻한다. 그래서 정해진 구간에서 모두 같은 색을 갖고있는지 판별한 후, 다른 색이 있다면 더 쪼개고(분할), 같은 색이라면 흰색인지 파란색인지 판별하여 count해준다. 작은 정사각형으로 쪼갤 때 총 4개의 정사각형이 새로 생긴다. 그래서 그림을 참고하여.. 2022. 11. 8.
[1406] 에디터 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 스택을 이용하여 문제를 풀었다. 커서를 기준으로 왼쪽 / 오른쪽 문자들을 나누어 stack을 2개 생성하였다. 처음에는 모든 문자를 left에 담는다.(커서가 맨 뒤에 있으므로) 그 다음 명령어에 따라서 left(커서 왼쪽)에 담을지, right(커서 오른쪽)에 담을지 결정한다. 첫번째 예제의 과정을 그려보았다. 각 명령어에 따라 push, pop을 적절히 사용하였다. 그림에 있는 것만 설명하자면 .. 2022. 11. 7.
[1158] 요세푸스 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 순열을 queue를 활용하여 푸는 문제이다. queue는 선입선출, 처음 넣었던 값이 제일 처음에 나온다는 뜻! 나 혼자 2시간 삽질하다가 다른 사람의 풀이를 참고하여 문제를 풀었다. ㅠㅠ 초반에는 queue가 아닌 deque를 사용하여 접근했다. deque는 중간에서 데이터 삽입, 삭제가 가능했기 때문이다. (그래서 K번째 데이터를 삭제하려고 했음..) queue에서 index로 데이터 삭제가 가능하다고 생각하고 문제를 풀었다. 그래서 (cur + K - 1 + myqueue... 2022. 11. 6.
[10866] 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net deque를 실제로 구현해보는 문제이다. Deque는 앞/뒤에서 모두 push, pop이 가능하다는 것이다.(Queue는 앞에서는 pop, 뒤에서는 push 가능) deque의 앞과 뒤를 나타내는 front, rear를 어떻게 나타냈냐면 front는 실제 있는 곳보다 앞에, rear는 실제 값이 있는 곳을 가리키도록 설정하였다. size를 출력하고자 한다면 (rear-front+M.. 2022. 11. 4.
[10845] 큐 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 큐를 직접 구현해보는 문제이다. Queue : FIFO(First in First out), 먼저 들어간 데이터가 먼저 나와야함. 한방향 통행 가능! 구현해야 하는 함수 6가지만 선언해주었다. template class MyQueue { public : int front; int rear; int size; T* values; MyQueue() { size = MAX; values.. 2022. 11. 3.
[17413] 단어 뒤집기 2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 태그 : 으로 둘러싸여 있음. 그 안에는 알파벳 소문자와 공백이 들어갈 수 있다. 단어 : 알파벳 소문자와 숫자로 이루어져있다. 연속된 단어는 공백으로 구분한다. 태그인 경우에는 그대로 출력, 단어인 경우에만 거꾸로 출력한다. 그래서 tag 안에 있는 경우를 bool 자료형으로 구분하였고, 단어를 stack에 담아 일정 조건이 되면(공백이 나타난다거나, '') { .. 2022. 11. 2.
[2156] 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이 문제는 2579번 계단 오르기 문제와 굉장히 흡사하다. https://kmyobin.tistory.com/81 [2579] 계단 오르기 https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https:.. 2022. 10. 31.
[2579] 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP 문제인데 어려워서 검색함 ㅎㅎ 내 무궁한 발전을 위해 어쩔 수 없는 선택이었당~! 여기서 조건 3가지가 쓰여있다. 1. 계단은 한 번에 1, 2칸씩 2. 시작점 제외하고 연속해서 3계단 밟지 마라 3. 마지막 도착 계단은 밟아라 마지막 계단에 도착한다고 했을 때 2가지 경우가 존재한다. 1. 바로 전 계단을 밟고 마지막 계단 도착 -> 이 경우에는 전전계단을 밟으면 안된다(2번 조건 때문). 그러므로 전.. 2022. 10. 31.
[9461] 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 지독하게 실버만 패는 사람,, 이 문제는 DP + 수학이 섞여 있는 문제이다. 나선형으로 돌아가는 형식이라 규칙이 있을 것이라 생각하고 직접 그려보며 문제를 풀었다. P(9)부터 규칙이 존재함을 발견했다. A[i] = A[i - 1] + A[i - 5]; 바로 그 전 값(i-1)과, 5번째 전에 있던 값(i-5)의 합이 현재 i의 값임을 알아냈다. 근데 그냥 했더니 틀렸다. 알고보니 int형이라 ove.. 2022. 10. 30.

티스토리툴바