본문 바로가기

전체 글1014

[자바] 백준 13565 - 침투 (java) 목차 문제 : boj13565 필요 알고리즘 그래프 탐색 (bfs, dfs) 약간의 아이디어만 생각나면 dfs나 bfs 같은 그래프 탐색으로만 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주어진 격자에서 맨윗줄 중 흰색(0)칸을 찾아 거기서부터 BFS를 계속 진행한다면 좀 귀찮다. 약간의 아이디어를 더한다면 BFS 한방에 해결할 수 있다. 아이디어는 생각보다 간단한데, 주어진 격자(이미지 좌측)의 맨위와 맨 .. 2023. 12. 15.
[자바] 백준 1375 - 나이 (java) 목차 문제 : boj1375 필요 알고리즘 그래프 탐색(bfs, dfs), 값/좌표 압축 값/좌표 압축이야 그냥 String을 쓰기 편하게 int로 바꾼 것 뿐이고, 풀이는 그냥 bfs를 썼다. 의외로 별다른 것 없이 bfs나 dfs로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 입력이 String으로 들어오는데 이 부분부터 처리해보자. 그냥 새로운 문자열이 들어오면 그걸 새로운 int로 바꿔주면 된다... 2023. 12. 14.
[자바] 백준 30025 - K의 배수 (java) 목차 문제 : boj30025 필요 알고리즘 DP (동적 계획법), 수학 DP를 이용해 풀 수 있는 문제이다. 풀이를 위해 수학적인 지식이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 M자리의 양의 정수를 구하고, 그 중 K의 배수가 몇 개인지 구하는 문제이다. 물론 실제로 가능한 모든 M자리 양의 정수를 구해보면 O(N^M) = O(10^100) 이라는 천문학적인 경우의수가 되므로 불가능하다. 그럼 어떻게.. 2023. 12. 12.
[세미나] 배열, 브루트 포스 (기초 자료구조 및 알고리즘 2회차) 세미나 진행한 pdf 입니다. 이후 자료구조 설명의 기반이 되는 배열과, 역시 이후 알고리즘 설명의 기반이 되는 브루트 포스에 대해 다룹니다. 이후에 영상이나 음성이 필요하다고 생각되는 회차가 있으면 그것도 공유할 예정입니다. ppt의 우측 상단 '새 탭에서 보기' 를 누르시면 크게보거나 pdf를 다운받아 보실 수 있습니다. 2023. 12. 11.
[자바] 백준 1477 - 휴게소 세우기 (java) 목차 문제 : boj1477 필요 알고리즘 매개 변수 탐색 (parametric search), 이분 탐색 (binary search) 이분 탐색을 이용한 매개 변수 탐색으로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 2년전에 못풀었다고 되어 있는데, 이번엔 어렵지 않게 풀었다. 발전하긴 한 것 같아서 기분 좋았다. 최소가 되는 구간을 직접 찾으려면 상당히 난감해진다. 그리디처럼 구간이 크다고 무조건 세운다.. 2023. 12. 8.
[자바] 백준 2418 - 단어 격자 (java) 목차 문제 : boj2418 필요 알고리즘 DP (동적 계획법) BFS 같은걸론 시간초과가 나게된다. 동적 계획법으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 '각 칸은 중복되게 사용해도 된다.' 부분이 문제인데, 이 부분때문에 BFS나 DFS로 진행 시 중복체크를 못하므로 시간복잡도가 저 멀리 가버리게 된다. 게다가 경우의 수의 경우 최대 10^18 이라고 했으므로, 따로 시간복잡도를 계산해보지.. 2023. 12. 8.
[자바] 백준 30646 -최대 합 순서쌍의 개수(java) 목차 문제 : boj30646 필요 알고리즘 누적 합(prefix sum), 해시를 사용한 집합과 맵 누적합과 해시맵을 사용해 풀 수 있다. 물론 언제나 다른 방법들도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 누적합을 모른다면 '누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java' 글을 보자. 이 문제를 풀기위한 로직을 생각해보면 다음을 알 수 있어야 한다.. 2023. 12. 6.
[자바] 백준 20500 - Ezreal 여눈부터 가네 ㅈㅈ(java) 목차 문제 : boj20500 필요 알고리즘 동적 계획법 (DP), 정수론 정수론 특히 나머지 연산의 성질에 대해 알아야 하고, 효율적으로 풀기 위해 DP가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아래와 같이 자리수를 늘려나가 만들어지는 N자리 양의 정수 중 15의 배수가 몇 개인지 구하는 문제이다. 당연하게도 1과 5로 이루어진 N자리 수는 2^N 개나 된다. 2^1515개의 정수는 천문학적인 수치이므로 .. 2023. 12. 5.
[자바] 백준 1612 - 가지고 노는 1 (java) 목차 문제 : boj1612 필요 알고리즘 수학, 정수론 나머지 연산의 성질을 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N의 실제 배수를 계산하면서 전부 1로만 이루어져 있는지 확인하는건 상당히 난감하다. 반대로 생각해보자. 결국 1, 11, 111, 1111, .... 이런 수가 결국 N으로 나누어 떨어진다면 N의 배수인거다. 이 경우엔 좀 쉬워진다. 그냥 1, 11, 111, ... 이런 .. 2023. 12. 4.
[세미나] 개발자 배경지식, 시간복잡도 (기초 자료구조 및 알고리즘 1회차) 세미나 진행한 pdf 입니다. 1회차는 오리엔테이션 느낌으로 진행했습니다. 이후에는 영상이나 음성이 필요하다고 생각되면 그것도 공유할 예정입니다. ppt의 우측 상단 '새 탭에서 보기' 를 누르시면 크게보거나 pdf를 다운받아 보실 수 있습니다. 2023. 12. 4.