목록Computer/Coding Test (70)
Machineboy空
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제요약 connected component 개수 찾기 난이도 Silver 2 풀이 포인트 깊이우선탐색(DFS) 리프 노드에 닿을 때까지 재귀 실행하는 특성을 이용하여, 연결 요소(coonnected component)의 개수를 구할 수 있음 2차원 좌표 탐색에 DFS 사용시, 매개변수만 두개로 늘려주어 2차원 배열 요소 접근하면 됌. fill을 이용한 초기화 fill(array_name, array_name..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제요약 N*M 크기의 배열로 표현되는 미로. (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수 난이도 Silver 1 풀이 포인트 너비우선탐색(BFS) 한 정점에서 다른 정점으로의 최단 거리를 구할 때 적합. queue의 선입선출 특성을 활용하여 인접한 것을 차례로 push, 먼저 들어온 것을 pop하는 로직으로 탐색! 2차원 좌표를 1차원 노드로 치환하여 생각하기. pair tie(int, in..
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제요약 A와 B로 이루어진 단어. 서로 교차하지 않게끔 짝지을 수 있다면 좋은 단어 난이도 Silver 4 풀이 stack pop() : 삭제 push() : 삽입 REVIEW 경우의 수로 풀려고 했다. 글자 개수가 짝수인지, 완벽 대칭인지 등. 도전이라도 해야할 것 같아 4개 이상인 경우엔 ABAB를 가지고 있으면 좋은단어가 아니라고 판단하는 이상한 로직을 짰다. 자료구조 공부를 열심히 해야겠다. 컴..
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제요약 A를 B번 곱한 뒤 C로 나눈 나머지를 구하라 난이도 Silver 1 풀이 분할 정복 ( Divide and Conquer) 작은 문제로 분할하여 해결하는 방식 모듈러 연산 (% 나머지 연산)에서 교환법칙이 성립한다는 것 (a+b)%c = a%c + b%c (a*b)%c = a%c * b%c log n = k 2를 k번 곱하면 n이 된다. ① 제곱수를 구할 때, 지수를 작은 덩어리로 나누어 곱셈 연산 횟수를 줄이는 것 ② 모듈러 연산에서 교환법칙이 성..
https://www.acmicpc.net/problem/1213
https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제요약 서로 다른 패션의 범주, 그 범주안에 속하는 서로 다른 아이템의 종류를 파악, 서로 다른 코디의 경우의 수를 구하는 문제 난이도 Silver 3 풀이 여집합 활용 : 전체 경우의 수 - 해당되지 않는 경우의 수 REVIEW 서로 다른 주머니, 주머니 안의 서로 다른 공의 종류 이렇게 치환해 생각하..
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제요약 숫자와 포켓몬 이름이 매핑되어 있는 도감에, 숫자를 넣으면 포켓몬 이름이, 포켓몬 이름을 넣으면 숫자를 출력. 난이도 Silver 4 풀이 입력값이 숫자인지 문자인지 판단 atoi(), stoi() *atoi()사용하지 않는 방법 추후 추가 배열과 map의 탐색 시간복잡도 배열 탐색 : O(N) map 탐색 : O(logN) ios_base::sync_with..
https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 요약 n개 범위의 구간 합 중 최대값을 출력 난이도 Silver 3 풀이 구간합(prefix sum) 최댓값 갱신 슬라이딩 윈도우 REVIEW 단순하게 중첩 for문으로 시작점으로부터 N개의 원소를 더해 vector에 push_back()했더니 메모리 초과. vector형이 문제인가 싶어 int 배열로 바꾸었더니 시간 초과가 났다. 정답률이 35%인데 너무 단순하게 접근한 것부터..