본문 바로가기
728x90
[백준/C++] 10026번: 적록색약(G5) 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 사용한 알고리즘 2022.02.05 - [PS/Algorithm] - [알고리즘 개념정리] 8. 그래프/그래프 탐색 -> 2차원 상에서의 그래프 탐색 풀이 이차원 상에서의 그래프 탐색이다. 모든 정점에 대해, 그 정점과 입접한 정점은 상, 하, 좌, 우 방향에만 있다. 따라서 각 정점의 좌표 (x,y)에 대해 (x+1, y), (x-1, y), (x, y+1), (x, y-1) 중 특.. 2022. 2. 6.
[알고리즘 개념정리] 8. 그래프/그래프 탐색 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 그래프 정점(vertice)의 집합 V와 간선(edge)의 집합 E로 이루어지며 보통 (V,E)로 표기한다. 각각의 간선은 두 정점의 쌍으로 나타낸다. 간선에 방향이나 가중치가 부여되는 경우도 있다. 관련 용어 무방향/방향 그래프, 인접, 사이클, 가중치 그래프, 연결 그래프(정점들이 모두 이어져있는 그래프) 간선 표현 방법 인접 리스트 vector adj[100005]; : 간선 개수에 비례하는 메모리만 차지 but 연결성 여부 판단 O(V) 대부분의 경우 정점 개수가 꽤 많기 때문에 인접 리스트가 유리하다. 인접 행렬 int adj[1005][1005]; : 연결성 여부 판단 O(1)에 가능 but .. 2022. 2. 5.
[백준/C++] 16564번: 히오스 프로게이머(S1) 문제 https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 사용한 알고리즘 2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복 -> 매개변수 탐색 풀이 팀 목표 레벨의 '최댓값'을 구하는 문제이므로 최적화 문제라고 할 수 있다. 결정 문제로 바꾸어 푸는 매개변수 탐색 기법을 사용해보자. 목표레벨 T는 최초 레벨들 중 최소값보다 작.. 2022. 2. 3.
[백준/C++] 2370번: 시장 선거 포스터(G4) 문제 https://www.acmicpc.net/problem/2370 2370번: 시장 선거 포스터 첫줄에는 포스터의 개수 n(1 ≤ n ≤ 10,000)이 주어지고, 그 다음 n줄에는 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r이 주어진다. (1 ≤ l 좌표압축 풀이 포스터의 개수 n의 범위는 1 ≤ n ≤ 10,000 이고, 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r의 범위는 1 ≤ l < r ≤ 100,000,000 이다. 벽의 칸이 1~10^8으로 큰 범위를 가지므로 실제로 붙이는 것처럼 배열 마킹한 후 카운트하는 방법으로는 AC받을 수 없다. 포스터의 실제 길이가 중요한 게 아니라 어떠한 포스터가 보이는 구간이 '있는지'가 중요하다. 즉, 실제 간격이 중요하지 않고 .. 2022. 2. 3.
[알고리즘 개념정리] 7. 이분탐색/분할정복 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 이분탐색(Binary Search) : 정렬된 리스트 arr에서 특정한 값 key를 찾는 알고리즘 탐색 구간의 중앙값 mid와의 대소 비교를 통해 다음 탐색 구간을 설정함 탐색 연산이 반복적으로 요구될 때 사용함 key값의 유무를 반환함 https://www.acmicpc.net/blog/view/109 bool binary_search(int *arr, int len, int key){ int l = 0; int r = len-1; int mid; while(l key) { //key값이 mid 값보다 작으면 왼쪽으로 r = mid - 1; } else { //key값이 mid 값보다 크면 .. 2022. 2. 2.
[백준/C++] 17136번: 색종이 붙이기(G2) 문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 모든 경우를 따지지 않고 가지치기하는 문제 풀이 5x5색종이부터 1x1색종이까지 차례대로 붙어본다. 붙일 수 있다면(범위가 10x10이내, 사용횟수 use값이 5 이내) 색종이를 붙인 후 재귀함수로 들어간다. 색종이를 붙일때는 matrix 값을 0으로 바.. 2022. 1. 31.
728x90