본문 바로가기

Algorithm/문제풀이

백준 온라인 저지 - 2468번: 안전영역 🔍 문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net ✏️ 풀이 - Java 높이가 될 수 있는 범위는 2에서 100사이이 므로 2에서 100까지 높이를 반복문으로 돌려주면서 안전한 영역의 개수를 세주었다. 지금까지 풀던 문제랑 비슷해서 어렵지 .. 더보기
백준 온라인 저지 - 1012번: 유기농 배추 🔍 문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net ✏️ 풀이 - Java 너무 bfs로만 문제를 푼 것 같아서 이번에는 재귀를 이용해서 dfs로 풀어보았다. 입력값으로 테스트케이스가 1개 이상으로 들어오기 때문에 테스트케이스 개수 t값을 받.. 더보기
백준 온라인 저지 - 2667번: 단지번호붙이기 🔍 문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net ✏️ 풀이 - Java 이전에 풀었던 미로 탐색과 비슷하면서 조금 다른? 문제였다. 큐를 이용해서 bfs 탐색으로 풀었고 값이 1인 좌표에서만 bfs 탐색을 시작하도록 했다. bfs 탐색 안으로 들어가면, 상하좌우 인접한.. 더보기
백준 온라인 저지 - 2178번: 미로 탐색 🔍 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✏️ 풀이 - Java 최단 거리를 구하는 문제여서 bfs로 풀게 되었다. 처음에 bfs탐색으로 풀었을 때 모든 지점을 bfs로 탐색하기는 탐색하는데 최단거리를 구하지를 못해서 굉장히 많은 시간을 허비했다. 풀고보니까 아니 이걸 왜 이렇게 생각못했냐고!!!!!!!하는 자괴감이 들었다...하.... 어쨌든 풀고나니까 언제 그랬냐는 듯이 속시원 그래도 이 맛에 코딩합니다... 어쨌든 풀이는 아래와 같다. 어떤 좌표 값으로 오기까지의 거리는 현재 좌표 이전 좌표까지의 거리 + 1이다. ma.. 더보기
백준 온라인 저지 - 1260번: DFS와 BFS 🔍 문제 말그래도 입력값으로 주어진 그래프를 dfs와 bfs로 탐색한 결과를 출력하면 된다. 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net ✏️ 풀이 - Java Codility에서는 함수 인자로 필요한 값들이 주어기 때문에 함수 안에서 필요한 코드를 작성해주고 문제에서 원하는 값을 return 해주면 된다. 하지만 온라인 저지 사이트에서는 표준 입력값이 주어지고, 입력을 받아서 return이 아.. 더보기
Codility Lesson13 - Ladder 🔍 문제 어떤 사다리가 있고, 발을 밟고 올라갈 수 있는 발판이 N개가 주어진다. 이때 발판을 한번에 이동할 수 있는 칸의 수는 1칸 아니면 2칸만 허용된다. 예를들어, 3개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1] or [1, 2] or [2, 1] 로 세가지이며 4개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1, 1] or [1, 1, 2] or [1, 2, 1] or [2, 1, 1] or [2, 2]로 5가지 방법이 존재한다. 따라서 주어진 사다리를 올라갈 수 있는 경우의 수를 return하면되는데, 발판의 수가 커질 수록 그 경우의 수는 기하급수적으로 커지기 때문에 배열 B에 주어진 수를 이용해서 2^B[i]를 한 값으.. 더보기
Codility Lesson12 - CommonPrimeDivisors 🔍 문제 두 배열 A와 B가 주어지고, 같은 index의 두 요소가 최대 공약수와 똑같은 인자를 가지고 있을 경우의 수를 구하는 문제이다. CommonPrimeDivisors coding task - Learn to Code - Codility Check whether two numbers have the same prime divisors. app.codility.com ✏️ 풀이 - JS Lesson의 소제목이 유클리드의 호제법이므로, 최대 공약수는 유클리드의 호제법을 이용해서 구해주었다. 유클리드 호제법 포스트보기 👉 유클리드 호제법(Uclidean algorithm) 먼저, 두 수의 최대 공약수를 구해 준 후, 각 수를 최대 공약수와의 최대 공약수를 다시 구해주면된다. 그리고 나서 각 수를 구한 .. 더보기
Codility Lesson12 - ChocolatesByNumbers 🔍 문제 N개의 초콜릿을 원 형태로 나열한 뒤, 0번째 초콜릿을 먹고 포장지만 남긴다. 그리고나서 현재 먹은 초콜릿 자리 + M의 자리에 있는 초콜릿을 먹는다. 원의 형태로 나열되어 있으므로 초콜릿의 자리는 (i + M)%N의 공식으로 구하면 된다. 이 순서로 초콜릿을 먹어가면서 이미 먹고 포장지만 남은 초콜릿의 자리로 다시 돌아오게된다면 먹는것을 멈춘다. 이 과정을 거쳤을 때 먹게되는 초콜릿의 개수를 구하면 된다. ChocolatesByNumbers coding task - Learn to Code - Codility There are N chocolates in a circle. Count the number of chocolates you will eat. app.codility.com ✏️ 풀이 .. 더보기
Codility Lesson11 - CountNonDivisible 🔍 문제 어떤 주어진 배열 A의 원소인 A[i]의 약수가 아닌 원소가 해당 배열에 몇개인지 구하는 문제이다. CountNonDivisible coding task - Learn to Code - Codility Calculate the number of elements of an array that are not divisors of each element. app.codility.com ✏️ 풀이 - JS 원소 A[i]의 약수가 아닌 수는 전체 원소의 개수에서 약수인 수를 빼서 구했다. 맨 처음에는 배열안에서 각각의 수가 몇개인지 구해준다. 원소의 개수를 담는 배열의 범위는 idx값이 1부터 N*2까지 담을 수 있도록 만들었다. 왜냐하면 문제의 조건 중에 A[I]의 원소가 될 수 있는 범위는 1부터 N.. 더보기
Codility Lesson11 - CountSemiprimes 🔍 문제 주어진 범위내에서 두 소수의 곱의 값인 semiprime의 개수를 구하는 문제이다. CountSemiprimes coding task - Learn to Code - Codility Count the semiprime numbers in the given range [a..b] app.codility.com ✏️ 풀이 - JS Lesson의 소제목이 Sieve of Eratosthenes(에라토스테네스의 채)이길래 이 이론에 대해서도 정리해보았다. 링크로 가기 👉 Sieve of Eratosthenes(에라토스테네스의 채)에 대해서 알아보자. 로직은 아래와 같으며, 시간 복잡도는 O(N * log(log(N)) + M) 가 나왔다. 1~N 까지의 인덱스를 가진 배열을 만들어준 후, 인덱스를 기준.. 더보기

티스토리툴바