목록코테준비/백준 (59)
끄적끄적
출처 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. c++ 2. python 상하좌우로 인정해 있는 경우 같은 구역에 속한다고 했으므로 dfs/bfs 사용하였음 적록색약이 아닌 경우 방문되지 않은 칸에 대해 bfs 돌려줌 적록색약인 경우를 구하기 위해 먼저 초록색 칸을 빨간색으로 바꿔줌 그 다음 visited 배열과 cnt 초기화해주고 적록색약인 경우도 방문되지 않은 칸에 대해 bfs 돌려줌
출처 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. c++ 2. python graph 리스트를 빈값으로 초기화해준 후 a,b값을 입력받아 서로 연결해줌 이후 dfs를 1부터 돌며 아직 방문되지 않은 정점에 한해 방문 visited 리스트에서 True(방문된) 개수의 합 -1을 해줌 (1까지 포함되어 있으니) * 함수 내에서는 함수 밖에 있는 변수에 값을 할당할 수 없다 원래는 밖에 cnt를 선언해서 dfs함수 내에서 cnt+=1 이런식으..
출처 : https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 우선순위 큐 맨 처음에 그냥 sort 사용해서 풀었는데, 메모리 초과 오류가 나서 우선순위큐 이용해서 품
출처 : https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 그리디 AAA = 100A + 10A + A 의 방식으로 접근한다. GCF ACDEB 이 경우에는 G=100 C=10 + 1000 = 1010 F=1 A=10000 D=100 E=10 B=1 이렇게 구한 다음 내림차순으로 정렬한 후에 큰 숫자부터 9.8.7.6 순으로 대입시켜줌 10000(9), 1010(8), 100(7), 100(6), 10(5), 1(4), 1(3) 어차피 다같..
출처 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 시작하는 시간이 빨라도 늦게 끝나면 최대 회의 수를 구할 수 없기 때문에 종료시간을 기준으로 정렬해야한다. 종료시간이 가장 빠른 회의의 종료시간을 맨 처음에 넣어주고 정렬된 스케줄을 보며 그다음 시작 시간이 지금 cur에 담긴 종료시간보다 크거나 같은지 비교해주며 진행

출처 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 그리디 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 구해야하는 문제이다. 우선 키 순서대로 줄을 세웠다고 했으므로 정렬을 해줌 그 다음 인접 원소간의 차이를 각각 구해주고, 이를 정렬해줌 K개의 조가 있다고 하면 K-1개의 경계가 있을 것인데 비용을 최소로 한다고 했기 때문에 차이가 큰 K-1개를 제외하고 더해주면 티셔츠 만드..
출처 : https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 그리디 water() 함수를 통해 N을 2로 계속 나눠가면서 나머지가 있으면 cnt(ex)N=5일 때 합쳐지고 난 후의 물병 개수)를 ++해준다. 나머지가 있다는 건 남게되는 물병이 있다는 뜻이기 때문 함수를 실행하고 난 후 생기는 물병의 개수가 K개 이하이면 while문을 탈출하면 되고 K개 초과이면 상점에서 물병을 하나 더 사야한다는 의미이므로 total++(상점에서 사야하는 물병의 최솟값..
출처 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 그리디 + 우선순위큐 주어진 숫자들을 우선순위큐에 넣고 오름차순 정렬하여 차례대로 뽑아주면서 더해주면 된다. 그래야 작은수부터 나오니까 최소 비교 횟수를 구할 수 있음. 우선순위큐 오름차순 정렬(default는 내림차순) -> priority_queue pq; * priority_queue는 힙으로 구현할 수 있다.