Algorithm 백준 온라인 저지 - 5052번: 전화번호 목록 🔍 문제 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net ✏️ 풀이 - Java 어떤 값 a를 어떤 값 b가 포함하고 있다면 이를 일관성이 없다고 할 수 있다. 예를 들어서, 911 93123857 91158634 가 있으면 911을 9115863.. 더보기 문자열 검색 - 브루트 포스, KMP, Boyer-Moore 문자열을 검색하는 알고리즘을 알아보자. 문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어있는지를 조사하고 들어 있다면 그 위치를 찾아내는 것을 말한다. 예제를 설명할 때는 편의상 어떤 문자열의 문자를 말할 때 원래는 string.charAt(idx)라고 해야 하지만 string[idx]라고 쓰겠다. 브루트-포스법 브루트 포스법으로 문자열을 검색하는 과정은 아래와 같다. 텍스트 "ABABCDEFGHA"에서 "ABC"를 찾는다고 가정했을 때, 다음과 같은 과정을 거치게 된다. 3번에서 4번으로 넘어가는 과정을 보면, 패턴의 문자와 다른 문자를 만나면 패턴을 1칸씩 뒤로 옮긴 다음 다시 패턴의 처음부터 비교하는 모습을 볼 수 있다. 이미 검사를 진행한 위치를 기억하지 못해 불필요한 검사를 진행하기 때문에 .. 더보기 백준 온라인 저지 - 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이 아.. 더보기 BFS(너비우선탐색)와 DFS(깊이우선탐색) 알고리즘을 공부하다가 꼭! 알아야하는 너비우선탐색과 깊이우선탐색에 대해 알아보고자 한다. 자료구조-트리 포스트에서 가볍게 훑어보고 넘어갔었는데, 알고리즘 문제에 적용하기 위해서는 더 알아볼 필요가 있다. 특히나 검색하면서 마이구미님의 Hello World 블로그에 이 이론들을 어떻게 문제에 적용시켜 풀지 생각하는데 도움이 많이 됐다. 링크로 가기 👉 마이구미의 Hello World 그래프(Graph) 연결되어 있는 객체 간의 관계를 표현하는 자료 구조이며 비선형 자료구조이다. 정점(vertex)과 두 노드를 연결하는 간선(edge)으로 이루어져있다. 부모-자식 관계라는 개념이 없으며 2개 이상의 경로가 가능하다. 계층이 없기 때문에 루트라는 개념도 존재하지 않는다. 또, 순환 구조일 수도 있고, 비순환 .. 더보기 자료구조 - 이진트리와 이진검색트리 이진트리(binary tree) 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다. 이때 각 노드의 자식은 2명 이하만 유지해야 한다. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 완전이진트리(complete binary tree) 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 한다. 1. 마지막 레벨을 제외한 레벨은 노드를 가득 채운다. 2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다. 높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^k+1 - 1개이다. 따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n이.. 더보기 자료구조 - 트리(tree) BFS와 DFS에 대해서 알아보기 이전에 먼저, 트리라는 자료 구조에 대해 알 필요가 있다. 아래의 내용은 이지스퍼블리싱의 Do it! 자료구조와 함께 배우는 알고리즘입문 책을 참고하여 재구성하였다. 트리(tree) 데이터 사이의 계층 관계를 나타내는 자료 구조이다. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지를 통해 다른 노드와 연결되어 있다. 트리 관련 용어 루트(root): 트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 한다. 하나의 트리에는 하나의 루트가 있다. 리프(leaf): 트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라고 한다. 이때 '가장 아랫부분에 위치한다'라는 말은 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라 더 이상 뻗.. 더보기 이전 1 2 3 4 5 6 다음