해나의 컴공생존기

https://www.acmicpc.net/problem/10989 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 출력 이는 원래 하던 merge sort로 하면 메모리 초과가 난다. 여기서 힌트로 봐야할 것은 숫자의 중복이 있다는 것과 입력되는 수는 10,000이하라는 것이다. 이 문제의 풀이는 10,000짜리 배열을 만들어서 각 숫자가 몇개 들어왔는지 세고 출력하는 것이다. #include using namespa..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력..

문제 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며..

https://www.acmicpc.net/problem/1874 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 ..

영역찾기는 전에도 해봤지만, 이번에는 각 색의 영역을 찾아야한다..ㅠ 그리고 두케이스를 봐야한다. 먼저 나는 color배열랑 Ncolor배열응 만들어 색약이 아닌 사람과 색약인 사람의 배열을 분리했다. Ncolor에는 G와 R이 있다면 1을 넣었다. 그리고 color배열에서 RGB로 세번 영역을 찾고 Ncolor배열에서 1로 영역을 찾아야겠다고 생각했다. 한참 코드를 짜다가 생각났는데 배열이 하나만 있어도 충분히 가능할 것 같았다. BFS조건만 좀 수정하면되니까... 근데 이미 코드를 너무 많이 짜서 킵고잉하자..! (뒤늦게 생각난건데 배열하나로 진행하려면 방문했는지 확인하는 배열이 필요하기때문이 메모리는 똑같을 것 같다 ㅎㅎ) 이야!! 성공했다! 짜잘짜잘한 오류가 있었지만 전에 비해 훨씬 빠르게 해결한..

흠..쉬울것같았는데 은근 고민스럽다..! 일단 미로문제니까 BFS로 풀자! 먼저 진호의 위치와 불의 위치를 파악하고, 진호의 위치로부터 가장자리로 가는 최단거리를 구한다. 최단거리를 구하는 방법은 check판에 이 자리까지 오는데 걸린거리를 기록하면서 나중에 최대값을 찾으면 될 것 같다. 불이랑 만나는지는 최단거리 루트를 구하고 생각할지, 아니면 BFS하면서 같이 구할지 고민하다가 fire배열을 만들어서 BFS업데이트할때 같이 업데이트해가면서 비교해봐야겠다고 생각했다. 계속 어떤 케이스는 되고 어떤케이스는 안되고 해서 오류를 하나하나 고쳐나갔다. 근데 이제 웬만하면 모든케이스가 다 되는데... 너무 억울한데..도대체 뭐때문에 안되는지 모르겠다ㅠㅠ 일단 내 코드는 차차 고민해보는걸로하고..! 다른 아이디어..

골드단계의 문제를 스스로 풀어보는건 처음이라! 꼭 스스로 풀겠다는 다짐을 하며 문제를 보았다. 음..1부터 시작해서 그냥 0인거 BFS하면 되겠다 싶었는데 요일를 세야하니까 한 타임에 몇개가 큐에 들어왔는지 세서 그 큐가 다 소진될때마다 하루씩 늘려야겠다고 생각했다. 풀 수 있을거같은데 시간초과가 날거같은...느낌? 일단 GO 다른 방법이 생각났다. 며칠째에 내가 익었는지 내 칸에 적어놓는다면 내 다음칸은 내 칸을 보고 +1을 하면 된다!! 다이나믹한 방법이다. 야호~! 맞았따~!~! 혼자힘으로 했다는게 너무 뿌듯하다~!~! #include #include #include using namespace std; int dx[4] = {0,1,0,-1}; int dy[4] = { 1,0,-1,0 }; que..

국어를 잘못하는지 집중력이 낮은지.. 문제 이해하는데에 좀 걸렸다. 결론적으로는 괄호문제와 비슷하다고 생각했다. A괄호와 B괄호가 있다고 생각하고 풀면 어렵지 않을 것 같다. 한 줄 읽고 한글자씩 보면서 읽은 글자가 스택의 맨 위와 같으면 pop해주고 그렇지 않다면 스택에 push 해준다. 스택이 비어있다면 무조건 push해준다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N,cnt=0; cin >> N; for(int i=0;i

1. 알고리즘 설명 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 맨 앞의 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 해당칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 2번을 반복 시간복잡도는 모든 칸이 큐에 한번씩 들어가므로 칸이 N개일 때 O(N)이된다. 2. 코드 BFS는 코딩테스트에서 굉장히 중요한 부분이므로 꼭 잘 숙지해야함! #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int bo..

큐를 이용하면 구현이 어렵지 않을 것 같다! #include #include using namespace std; int main() { queue p; int N,s=0; cin >> N; for (int i = 1; i