어흥

문제 링크: https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 1. 주의할 점 - 스택을 사용해서 해결한다 → O(N)에 해결 2. 구현 - 스택에 문자와 문자가 위치했던 인덱스 번호를 구조체 형태로 저장하여 쌓는다 - 이때, 스택의 Top에 위치한 원소와 현재 검색하려는 원소가 쌍이라면 스택의 원소를 뺀다 - 이외의 경우에는 스택에 원소를 추가한다 - 위의 방법을 통해 스택에는 쌍을 못이룬 문자들에 대한 정보만 담고 있다 ..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 1. 주의할 점 - 구현해야 하는 조건이 많다 - 2개의 좌표를 어떤 방식으로 저장할 것인지 정한다 2. 구현 - BFS를 통해 문제를 해결한다 - Info 객체를 통해 로봇의 정보를 저장한다. 로봇의 한 좌표와 어떤 방향에 다른 좌표가 위치해 있는지 저장한다. - 우선순위큐 pq에 로봇의 정보를 담으며, 소요 시간의 오름차순으로 정렬한다 - Board의 정보를 static 변수..

문제 링크: https://www.hackerrank.com/challenges/matrix-rotation-algo/problem?isFullScreen=true Matrix Layer Rotation | HackerRank Rotate the matrix R times and print the resultant matrix. www.hackerrank.com 1. 주의할 점 - R만큼 회전시키지 않는다(적절히 패턴에 맞게 나눈다) 2. 구현 - Row와 Col을 구한다 - 해당 직사각형이 몇 개의 껍질로 이루어져있는지 구하여 Times에 저장한다 - Rotate() 함수를 통해 각 껍질에 대해 작업을 수행한다 - 회전되는 수는 각 껍질의 2*(열+행-2)만큼 돌 때, 원래 상태로 돌아오므로 돌려야하는..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/77886 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr 1. 주의할 점 - 브루트포스로 풀지 않는다 - 선형시간(O(N))내로 푼다 2. 구현 - 입력 받은 문자열에 대해 110의 개수를 확인한다 - 110을 제외한 문자열을 Deque에 담도록 한다 - 110의 개수가 1개 이상일 때, 문자열 어디에 삽입하면 사전 순서로 가장 빠를지 예상한다 Deque에는 다음과 같은 형태만 들어..

문제 링크: https://www.acmicpc.net/problem/24513 24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net 1. 주의할 점 - BFS 종료시점을 잘 정하여 TLE가 나지 않도록 한다 - 동시에 도달할 경우, 어떻게 처리할 것인가 2. 구현 - Y, X, 바이러스 번호, 해당 칸에 도달하기까지 걸린 시간의 형태를 저장하는 Info를 이용하여 BFS를 수행한다 - Check[y][x][flag] 배열을 통해 flag 바이러스가 [y][x]에 도달하기까지 걸린 시간을 저장한다 - Ar..

문제 링크: https://leetcode.com/problems/zigzag-conversion/ Zigzag Conversion - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 주의할 점 - 큰 2차원 배열을 사용하지 않는다(Ex. 1시 방향으로 올라갈때 우측 1칸, 위로 1칸) → 메모리 절약 - numRows의 값에 따라 패턴 길이를 구한다 2. 구현 - String[] 배열에 문자들을 추가하는 방식으로 구현한다 - 몇 개를 기준으로 각 문자열이 ..

문제 링크: https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 1. 주의할 점 - 자식이 많은 부모의 경우, Leaf를 찍고 돌아왔을 때 다음 Node가 자신의 자식인지 어떻게 판별할 것인가? - 브루트포스는 절대로 하지 않는다 (하면 안되는거 알잖아요..) - TLE를 어떤 방식으로 해결할 것인가? 2. 구현 - 제목 그대로 DFS로 접근한다 - 모든 간선에 대한 정보는 Li[] 리스트 배열에 담는다 - Ar..

문제 링크: https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 1. 주의할 점 - 정렬기준을 잡는다 - 2개의 우선순위큐를 이용한다 2. 구현 - 각 입력에 대한 정보들을 시작시간에 대한 오름차순, 종료시간에 대한 내림차순으로 정렬하는 우선순위큐 PQ에 담는다 - 현재 진행중인 회의에 대한 종료시간을 담는 우선순위 큐 haveRight에 PQ의 첫 원소의 종료시간을 담고 시작한다 - haveRight 우선순위큐는 오름차순으로 정렬한다 - 우선..