문제https://www.acmicpc.net/problem/14757 풀이 위상 정렬과 관련된 문제로, 위상 정렬에 대해 아직 모른다면 블로그에 포스팅이 https://hyeon0117.tistory.com/84 있으니 확인하고 오길 바란다. [Algorithm] 위상 정렬(Topolgy Sort)위상 정렬 위상 정렬이란 사이클이 없는 유향 그래프에서 노드 순서를 찾는 알고리즘이다. 여기서 유향 그래프는 방향성이 있는 그래프를 의미한다. 위상 정렬은 사이클이 없는 그래프에서 사hyeon0117.tistory.com 위상 정렬 알고리즘의 동작 방식에 대해 물어보는 문제인데, 문제가 영어인지라 번역기를 이용해 문제를 해결하였다. 문제가 굉장히 길지만 물어보는 내용은 주어지는 그래프에서 위상 정렬 결과가 ..

문제https://www.acmicpc.net/problem/1926 풀이 이전에 너비 우선 탐색 포스팅을 했었는데, 이 알고리즘을 적용해보기 좋은 문제다. 우선 BFS에 대해 아직 모른다면 아래 포스팅을 한번 짧게 보고, 이 문제를 풀어보자. https://hyeon0117.tistory.com/86 [Algorithm] 너비 우선 탐색너비 우선 탐색 너비 우선 탐색 BFS 알고리즘 DFS와 유사한 그래프를 완전 탐색하는 알고리즘이다. 시작 노드에서 탐색할 분기를 정해 최대 깊이까지 탐색하는 DFS와는 다르게 시작 노드를 기준으hyeon0117.tistory.com 문제는 간단하다. 0과 1로 이루어진 2차원 배열에서 상하좌우가 1인 구역의 개수를 찾고, 1로 구성된 구역의 넓이 중 가장 큰 넓이의 ..

문제https://www.acmicpc.net/problem/14567 풀이 다양한 선이수 과목 정보가 주어졌을 때, 주어진 과목들을 최소 몇 학기 내에 이수 가능한지 물어보는 문제이다. 먼저 수강해야 하는 과목을 수강해야만 수강할 수 있는 과목들이 있다. 예를 들어 컴퓨터공학과에서 프로그래밍 기초 -> 자료구조, 확률 및 통계학, 선형대수학 -> 인공지능과 같이.. 이 예시에서는 프로그래밍 기초 과목을 수강하지 않았으면 자료구조 과목을 수강할 수 없으며, 인공지능 과목 역시 확률 및 통계학, 선형대수학 과목 둘 중 하나라도 수강하지 않았다면 인공지능 과목을 수강할 수 없다. 여기서 과목을 정점으로 생각하면 방향 그래프를 그릴 수 있는데, 위상 정렬을 이용하면 그래프의 방향에 맞게 노드를 순서대로 배열할..

문제https://www.acmicpc.net/problem/1448 풀이 N개의 수를 입력받고, 입력받은 수들 가운데 3개를 선택해 만들 수 있는 가장 큰 삼각형의 둘레를 구하는 문제이다. 다만, 입력받는 수 N의 범위가 3 ~ 1,000,000인 것을 유의해야 한다. N의 범위가 최대 1,000,000인 만큼 $N^2$의 시간 복잡도로는 해결할 수 없을 것 같아 입력받는 수들을 순차탐색 하는 방식으로 문제를 해결할 수 있다고 생각했다. 먼저, 삼각형이 만들어지기 위해서는 빗변의 길이가 나머지 두 변 길이의 합보다 작아야만 한다. 이 조건에 따라 입력받은 수들을 배열에 저장한 뒤, 오름차순으로 정렬을 수행하면 가장 큰 값인 arr[N-1]이 빗변의 길이가 되고, arr[N-2]와 arr[N-3]이 ..

문제https://www.acmicpc.net/problem/18774 풀이 형식언어를 복습하던 중 CS 관련 문제도 백준에 있을까 싶어서 백준 유한 오토마타를 검색하니 관련 문제가 나왔다. 그래서 예전에 학교에서 배웠던 어셈블리 관련 문제도 있나? 해서 검색해봤는데 진짜 있었다. 서론은 이쯤하고, 이 18774번 문제가 어셈블리 코드를 짜는 문제인데, 장황한 문제 설명에 비해 요구하는 것은 사실 간단하다. 한 자리 이진수를 7번 입력받고, 입력받은 이진수의 비트를 반전시켜 출력하면 되는 문제이다. 그런데 이제 not 연산을 단 1회만 사용할 수 있으며, get과 put 연산은 각각 7회 사용해야만 하는 조건이 있다. 일단 어셈블리 관련 포스팅은 하지 않았는데, 간단하게 문제에서 제공하는 어셈블리어 연산..

문제https://www.acmicpc.net/problem/11478 풀이 입력으로 문자열이 하나 주어졌을 때, 해당 문자열의 부분 문자열의 개수를 구하는 문제이다. 이때, 서로 다른 부분 문자열들의 구해야 하는 점만 고려한다면 문제를 쉽게 해결할 수 있다. 부분 문자열이란 문자열에서 연속된 일부분을 말하는데, abcd에서 부분 문자열들은 a, b, c, d, ab, bc, db, abc, bcd, abcd가 10개가 있다. 이때, 같은 부분 문자열을 중복으로 세면 안되므로 간단히 해시 셋을 을 이용하여 문제에서 요구하는 서로 다른 부분 문자열의 개수를 구할 수 있다. 코드12345678910111213141516171819202122import java.io.BufferedReader;import ..

문제https://www.acmicpc.net/problem/1058 풀이람들의 친구 관계 정보가 행렬 형태로 입력으로 주어질 때, 문제에서 정의하는 2-친구의 수가 가장 많은 사람의 2-친구의 수를 출력하면 해결할 수 있는 문제이다. 문제에서 정의하는 2-친구는 다음 조건을 만족한다. 1) 두 사람이 서로 친구, 2) A가 B와 친구이고, B와 C가 친구라면, A와 B는 2-친구 관계이다. 정의하는 2-친구의 조건이 좀 난해한데, 조건 1)은 쉬우니 넘어가고 조건 2)를 파헤쳐보자. 사실 조건 2)는 한 사람을 건너서 친구 관계라면, 그 사람과 2-친구 관계라는 것이다. 이제 두 조건을 파악하였으니 이것을 코드 상으로 옮겨주면 된다. 이 아이디어를 생각하고, 주어지는 예제 입력을 살펴보니 더 확실한 ..

문제https://www.acmicpc.net/problem/1051 풀이 문제에서 N * M 배열이 입력으로 들어오고, 이렇게 들어온 배열에 대해 네 꼭짓점의 값이 같은 가장 큰 정사각형의 넓이를 결과로 출력하는 문제이다. 태그에 '브루트포스 알고리즘'이 붙어있고 N과 M 범위가 매우 작아서 완전 탐색을 해도 충분히 풀릴 것으로 생각되었다. 여기서 N과 M 두 값 중 하나라도 값이 1이라면 어차피 한 변의 길이가 무조건 1이 될 것이니 정답은 1이 될 것이다. 이제 반대의 경우에는 N과 M 두 값 중 더 작은 값을 기준으로 3중 반복문을 돌아 네 꼭짓점에 위치한 값들이 일치하는지 검사하고, 네 값이 모두 같다면 이때의 정사각형 넓이를 출력하도록 하였다. 그리 어렵지 않은 문제니 아래 코드를 보면 오래 ..