![]()
4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도..
문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 코드 def binary_search(array, target, start, end): if start > end: return Fals..
https://zero0205.notion.site/4-85630a7e1bca49c2bd9d7b5a6a5b02e4 4. 정렬 기준에 따라 데이터를 정렬 zero0205.notion.site 기준에 따라 데이터를 정렬 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬을 해놓으면 이진 탐색(Binary Search)이 가능 내림차순은 오름차순해서 뒤집기만 하면 되는데, 리스트 뒤집기 연산은 O(N) 정도의 복잡도로 간단히 수행 가능 정렬 알고리즘의 종류 선택 정렬 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸고...→반복 소스 코드결과✅ 파이썬의 스와프파이썬은 다음과 같이..
https://zero0205.notion.site/3-DFS-BFS-4f49d7ab9a554b23842a265a8713f28e 3. DFS/BFS 기본 개념 zero0205.notion.site
https://zero0205.notion.site/2-1d3d5393ddb349dba1c18f33dcbe2976 2. 구현 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 zero0205.notion.site 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 ⇒ 구현 문제 유형은 모든 범위의 코딩 테스트 유형을 포함하는 개념이다. 흔히 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제’를 의미 구현하기 어려운 문제 유형 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어졌을때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제 ⇒ 사소한 조건 설정이 많은 문제 구현이 핵심이 되는 문제 유형 완전 ..
https://zero0205.notion.site/1-cb3cda34f7ff404a9aa9cd6cf23becf7 1. 그리디 탐욕법 zero0205.notion.site 탐욕법 현재 상황에서 당장 가장 좋은 것만 고르는 방법 현재의 선택이 나중에 미칠 영향은 고려하지 않음 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 다익스트라 알고리즘 같은 특이 케이스의 경우 암기 필요 정당성 분석이 중요 ⇒ 단순히 지금 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음 코테에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨. 보통 코딩테스..
