https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 3차원 큐브를 탈출하는 문제입니다. 한 층씩 좌우로 층을 회전할 수 있고, 한 층씩 마음대로 쌓을 수 있기 때문에, 각 층을 회전하여 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS) 1번, 각 층을 쌓아 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS..

https://uknowblog.tistory.com/364 [알고리즘] 그래프 탐색 - 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Bread uknowblog.tistory.com 위 DFS/BFS 글을 쓰기 위해 자료조사를 하고 있을 때 였습니다. DFS의 예시로 좋은게 뭐가 있을까 찾던 중에 한 충격적인 영상을 보게 되었습니다. https://www.youtube.com/watch?v=0kaHIfrB3T4&ab_channel=DaveStephens DFS를..

www.google.com을 브라우저 주소창에 입력하면 벌어지는 일. 기술 면접 질문으로 꽤 많이 나오는 질문이며, 구글링을 해보면 자료가 굉장히 많이 나오는 주제 중 하나입니다. 이미 매우 훌륭한 글들이 많긴 하지만, 공부할 겸 블로그에 정리해보고자 이렇게 포스팅을 해봅니다. 아무래도 자신이 쓴 글이 가장 보기 편한 법이니까요. DNS 서버에서 서버 IP 주소 찾기 DNS(Domain Name Server)는 도메인 이름과 IP 주소간의 변환을 담당하는 서버입니다. 웹사이트 등의 주소는 사실 IP 주소입니다. http://123.456.789.01과 같이 IP 주소를 통해 접속을 하는데, IP 주소의 경우 사람들이 외우기 쉽지 않습니다. 따라서 www.google.com, www.naver.com 과 ..

꼬리재귀 (Tail Recursion)? 재귀함수는 함수가 자기 자신을 호출하는 함수를 의미합니다. 그 중에서도 꼬리재귀(Tail Recursion)는 재귀 함수 종류 중에서도 재귀 함수의 마지막 부분에서 자기 자신을 호출하는 재귀 함수를 의미합니다. 재귀함수의 대표적인 예시 중 하나인 팩토리얼을 갖고와봤습니다. 위 코드 같은 경우는 자기 자신을 호출하는 부분이 함수의 맨 마지막 줄이 n * fact(n-1)로, n을 곱하는 추가적인 연산이 있습니다. 마지막 줄에 n을 곱해주는 연산을 없애기 위해 인자를 하나 더 늘려 재귀 호출이 함수의 마지막 부분인 꼬리 재귀 형태로 만들었습니다. 재귀함수의 문제점? 재귀 함수는 간결하게 짤 수 있어 DFS 등에서 저도 애용하나, 몇 가지 문제점이 있습니다. 1. 때때..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 난이도 : 실버 3 태그 : 수학, 기하학, 많은 조건 분기 설명 x1, y1과 반지롬 x2, y2와 반지름이 주어졌을 때, 위치의 개수를 출력하는 문제입니다. 즉, 외접하거나 내접하는 경우를 찾으면 되겠네요. 위치의 개수가 무한대일 경우 두 원이 일치할 경우, 적이 있을 수 위치는 무한대입니다. 위치의 개수가 0개일 경우 터렛의 두 사람의 위치가 같으나, 반지름이 다를 때, 두 원은 서로 교차하지 않습니다. 따라서 적이 있을 수 있는 위치의 경우..

위와 같은 이중 for문이 있습니다. 위 코드에서 break문은 어떤 반복문을 탈출할까요? 가장 가까운 반목문인 안쪽 반복문 입니다. 하지만, j가 5가 될때 두 반복문 모두 탈출하고 싶다면 어떻게 해야 할까요? for문 바깥쪽, 혹은 첫 번째 for문 안쪽에 flag 변수를 두고, j == 5가 됬을 때, flag를 true로 바꿈으로써 두 반복문을 모두 탈출할 수 있습니다. 하지만 별도의 flag를 두어 관리하는게 조금 번거로워 방법을 찾아보던 중, for문에 라벨링을 붙이는 방법을 알게 되었습니다. 바깥쪽 for문에 outer라는 이름으로 라벨링을 붙여주고, 안쪽 for문에서 해당 반복문에 break를 걸 수 있게 되었습니다. 바깥쪽 반복문을 탈출하므로 안쪽 반복문 역시 자연스레 탈출하게 됩니다. ..

https://www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net 난이도 : 실버 5 태그 : 정렬 설명 문제 자체는 쉬웠으나, 입력이 꽤 특이하여 애먹었던 문제였습니다. 처음엔 카운팅 변수를 하나 두고 체크했는데 왜인지 계속 오류가 나서, BufferedReader를 사용해 null을 입력받을 때 까지 계속 입력받는 방법으로 구현했습니다. (BufferedReader는 더 이상 입력받을게 없을 경우 null 반환) 소스코드 import java.util.Strin..

그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다. 물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요. 깊이 우선 탐색 (DFS, Depth - First Search) DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다. 한 노드의 연결된 노드를 먼저 탐색한다는 의미죠. 해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다. 한 노드를 탐색할 때, 해당 노드와 연결된 ..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 난이도 : 실버 3 태그 : 다이나믹 프로그래밍 설명 다이나믹 프로그래밍에서 웰노운 문제들인 타일 시리즈. 이번엔 1과 00이라는, 조금 특이한 경우네요. 음... 어떻게 풀지 고민하다가, 결국 그냥 하나씩 써보면서 규칙성을 찾아보기로 했습니다. n = 2 11 00 2개 n = 3 100 001 111 3개 n = 4 0000 0011 1100 1001 1111 5개 n = 5 00001 00100 ..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프탐색, 그래프이론, 너비우선탐색 설명 한 좌표에 다른 좌표의 불을 켤 수 있는 스위치가 있습니다. 복수개일 수 있으며, 스위치를 총 몇 개나 작동시킬 수 있는지(불을 킬 수 있는지)를 구하는 문제입니다. BFS를 사용하면 될 것 같지만, 스위치를 켜서 갈 수 있는 좌표가 늘어남에 따라, 해당 좌표와 인접한 좌표..