https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 두 학생 중 어느 학생의 등수가 더 높은지, 상대적인 정보만을 가지고 특정 학생이 가질 수 있는 등수의 범위를 찾아 최대, 최소를 구하는 문제이다. 구하고자 하는 학생을 기준으로, 등수가 높은 학생과 낮은 학생의 수를 각각 BFS를 활용하여 구한 후, 이를 바탕으로 가능한 가장 높은 등수, 낮은 등수를 구했다. ( 가능한 가장 높은 ..
Algorithm
https://www.acmicpc.net/problem/2539 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 문제 입력 조건에서 행과 열의 개수가 100만이라 2차원 배열을 사용하면 메모리초과가 난다. 또한 가장 작은 색종이의 크기를 구하는 문제인데 각 색종이의 크기마다 도화지에 대해 반복문을 돌리면 시간초과가 난다. 따라서 도화지 전체에 대해서가 아니라 잘못 칠해진 페인트에 대해서 반복문을 돌리고, 색종이의 크기에 대해서 이분탐색을 수행하여 색종이의 최소 크기를 구하였다. 잘못 칠해진 페인트의 좌표를 pair로..
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2차원 지도에서 특정조건을 만족하는 칸부터 상태가 변하며 모든 칸의 상태가 변할 때까지 걸리는 시간을 출력하는 문제이다. 전형적인 그래프 탐색에 구현이 붙은 문제이다. 1시간이 지날때마다 지도에서 몇 가지를 체크하는데, 외부 공기. - 치즈 내부에도 공기가 있는데 내부 공기 칸의 테두리의 치즈가 녹은 경우, 해당 공기 칸을 외부 공기로 바꿔줘야 한다. - airCheck()로 구현. ..
https://www.acmicpc.net/problem/2528 구현, 시뮬레이션 문제이다. 문제에서 제시하는 상황과 조건에 맞게 사다리를 오르는 동작을 구현하여 풀었다. Pair로 벡터를 만들어 각층마다 사다리의 왼쪽 끝점의 좌표, 오른쪽 끝점의 좌표를 저장했고, 사다리의 처음 위치는 사다리의 초기 이동 방향(d)에 따라 결정되기 때문에 d값에 따라 각층 사다리의 위치와 방향을 초기화시켜 줬다. 그리고 while(true) 문 안에서 사다리들이 1단위시간에 1칸씩 좌우로 움직이고 각 단위시간마다 철수가 다음 층으로 올라갈 수 있는지 체크하고 올라갈 수 있으면 y값을 증가시켜 줬다. 위 사진과 같이 두 층의 사다리 끝점에 맞물리는 경우에도 위 층으로 이동할 수 있다는 사실을 주의해야 한다. #inclu..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제에서 주어진 방향 순서대로 x, y 좌표 값을 x_dir[], y_dir[]에 각각 저장해두고 사용하였으며 로봇 청소기의 동작 순서대로 코드를 구현하였다. 현재 위치와 방향을 기준으로 왼쪽 방향으로 한 바퀴 탐색하면서 해당 좌표를 청소하지 않았다면 방향, 좌표를 바꾸고 새로운 방향과 좌표로 재귀호출해 준다. 네 방향 이미 방문했거나 벽이라면 로봇 청소기의 방향은 유지하고 좌표만 뒤로 한 칸 ..
https://www.acmicpc.net/problem/17611 17611번: 직각다각형 입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi, yi)가 차례대로 주어진다. 주어지 www.acmicpc.net 꼭짓점의 개수와 좌표가 입력으로 주어지고 해당 꼭짓점들을 순서대로 연결했을 때 만들어지는 직각다각형을 수직 또는 수평으로 지나는 선을 그었을 때 교점의 최대 개수를 출력하는 문제이다. 직각다각형이라는 조건이 있으므로 이웃하는 두 꼭짓점의 x좌표, y좌표 중 하나는 무조건 같다. 따라서, 이웃하는 두 꼭짓점의 x좌표가 같을 경우, 두 점의 y좌표 중 작은 값에서 큰 값까지 반복문을..
알고리즘 공부를 할 때 알아야 하는, 알면 좋은 개념들을 정리해보았다. 지속적으로 추가할 것이다. #include 과 #include "헤더파일" 의 차이점. #include 은 '컴파일러가 설치된 폴더'에서 해당 헤더 파일을 찾으라는 지시이다. #include "헤더파일"은 '현재 소스 파일이 존재하는 폴더에서 해당 헤더 파일을 먼저 찾고 없으면 '컴파일러가 설치된 폴더'에서도 찾는다. 사용자가 만든 헤더파일이나 추가 외부 라이브러리를 포함하고 싶은 경우 사용한다. 정규 표현식(Regular expression) : 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어. 특정한 조건이나 패턴이 있는 문자열을 간단하게 표현할 수 있다. c++ 의 경우 C++ 11부터 사용 가능하다. reg..
최근 백준 온라인 저지(boj.kr)를 활용하여 알고리즘 문제를 중점적으로 풀면서 겪었던 에러를 몇 가지 기록하고자 한다. 알고리즘 문제를 풀다 보면 정말 단순한 이유나 오타에서부터 생각지도 못한 에러까지 다양한 원인으로 인해 1시간 넘게 삽질하는 경우가 빈번하게 발생한다. 부딪혔던 문제들의 원인을 잘 기억하고 해결 방법을 숙지해서 같은 실수를 반복하지 말자!! 1. 런타임 에러(Runtime Error) : 프로그램이 비정상적으로 종료된 경우 발생한다. 런타임 에러에는 다양한 원인이 존재하지만, 나는 OutOfBounds, Segfault 두 가지의 런타임 에러를 경험해 보았다. 근데 사실 이 두 개가 가장 대표적이고 대중적인 런타임 에러인 것 같다. A. OutOfBounds : 배열, 벡터 등 컨테..
