본문 바로가기

분류 전체보기

그림으로 공부하는 IT 인프라 구조 📚 후기 저번에 후기 작성한 책도 '그림으로 배우는'이었는데 이번에는 그림으로 '공부하는' IT 인프라 구조 책이다. 이 책은 사실 학원 막 다니기 시작하고 얼마 안 돼서 산 책인데, 그때 한 번 대충 훑어서 읽고 다시 꺼내서 읽게 되었다. 그때는 읽으면서 알듯 말 듯하면서 몰랐다(?) 그래도 지금은 중간에 정처기도 따고 예전보단 아예 지식이 없는 건 아니어서 훨씬 읽을 만 해졌다. 크크크 지난번 책은 제목 그대로 주로 http와 네트워크에 좀 더 치중되어 있었지만 이 책은 뭔가 더 전체적인 부분을 굉장히 짜임새 있게 볼 수 있었다. 나처럼 비전공자들이 컴공 지식을 쌓고 싶을 때 어렵지 않게 읽을 수 있는 책으로 추천한다. 📝 정리 아키텍쳐 집약형 아키텍쳐 - 한대의 대형 컴퓨터만 있으면 되므로 구성이 .. 더보기
백준 온라인 저지 - 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 탐색 안으로 들어가면, 상하좌우 인접한.. 더보기
백준 온라인 저지 - 11403번: 경로 찾기 🔍 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net ✏️ 풀이 - Java 처음 출발하는 정점을 고정시켜놓고 정점을 탐색할때마다 출발 정점에서 탐색가능한 정점으로 간주하여 입력으로 들어온 배열에 경로로 갈수 있는 값을 1로 바꿔주었다. bfs는 큐, dfs는 스택을 이용해서 풀어보았는데 bfs가 근소한 차이로 조금 더 빨랐다. boj사이트에서 이 문제를 가장 빨리 푼 사람의 코드는 내 코드와 비교 했을 때 실행시간이 2배정도 빨랐는데, 입력값으로 들어오는 인접행렬을 boolean값으로 바꿔 이 하나의 2차원 배열을 3중 for문을 돌려서 [0, 1.. 더보기
백준 온라인 저지 - 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개 이상의 경로가 가능하다. 계층이 없기 때문에 루트라는 개념도 존재하지 않는다. 또, 순환 구조일 수도 있고, 비순환 .. 더보기

티스토리툴바