본문 바로가기

전체 글1068

[자바] 백준 1311 - 할 일 정하기 1 (java) 목차 문제 : boj1311 필요 알고리즘 bit DP (비트 필드를 이용한 다이나믹 프로그래밍) 비트 단위 DP로 푼 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제를 좀 더 간소화시켜서, N이 항상 3이라고 해보자. 이 때 dp[A][B] 를 A번 사람을 B라는 일의 조합으로 진행한 경우 비용의 최솟값이라고 정의하자. 이 경우 B는 3개의 일을 가지고 할 수 있는 모든 경우를 나타낼 수 있으면 된다. 0. .. 2023. 8. 3.
[자바] 백준 1956 - 운동 (java) 목차 문제 : boj1956 필요 알고리즘 플로이드-워셜 (floyd-warshall) 다른 그래프 탐색 알고리즘으로 되긴 하겠지만, 이 문제는 플로이드 워셜이 매우 편하긴 하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 단방향 그래프에서 '1번 마을에서 1번 마을로 가는 최소 거리, 2번 마을에서 2번 마을로 가는 최소 거리, ... , V번 마을에서 V번 마을로 가는 최소 거리' 중 최소값을 출력하면 되는 문제이다... 2023. 8. 3.
[자바] 백준 11812 - K진 트리 (java) 목차 문제 : boj11812 필요 알고리즘 최소 공통 조상 (LCA) LCA 문제이다. 근데 몰라도 푸는데 딱히 지장은 없다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 LCA를 안다면 그걸로 바로 접근 가능하고, 몰라도 딱히 상관은 없다. 어차피 첫 깊이엔 1개, 두번째 깊이엔 K개, 세번째 깊이엔 K^2개, ... 의 노드가 존재할꺼다. 그러므로 x와 y를 입력받을 시, K로 나누다보면 점점 부모 노드의 번호를 알 .. 2023. 8. 3.
인텔리제이, CLion에서 Rust 사용하기 (개발하기) 목차 Rust가 좋다고 하길래 궁금해졌다. 일반적으로 Rust 언어로 개발할 때 vscode를 많이 쓰는 것 같다. 하지만 내 경우 이미 젯브레인 계열의 단축키가 익숙해져 버린 몸이므로, 인텔리제이나 CLion으로 Rust를 사용해보고 싶었다. Rust 설치 https://www.rust-lang.org 에서 Get Started 또는 Install 메뉴에서 Rustup을 다운로드 후 실행한다. rustup은 러스트의 버전 및 환경 관리 도구라고 보면 된다. Case 1. 이미 Visual Studio가 깔려있던 경우 Rust를 사용하려면 MSVC 라는게 필요하다. 이미 Visual Studio 같은게 깔려있었다면 아래처럼 메뉴가 나타날꺼다. '1'을 선택해 안내에 따라 설치를 진행하자. 이 때, 윈도우.. 2023. 7. 28.
인텔리제이, 파이참 여러 PC 환경 동기화 (jetbrains 툴을 여러 PC에서 사용하는 경우 환경 동기화) 목차 별도로 노트북을 사용하지 않는 경우, 집과 회사에서 사용하는 PC가 다를 수 있다. 인텔리제이나 파이참 등 jetbrains의 툴들을 회사에서 사용하는 설정과 집에서 사용하는 설정을 다르게 쓰고 싶은 경우도 있겠지만, 일반적으로는 한 곳에 공들여서 설정해두고 나면 다른 쪽도 동일한 환경으로 사용하고 싶어진다. 예를들어 이번에 copilot 플러그인을 설치했다면, 다른 쪽도 굳이 plugins에서 새로 설치 안해도 알아서 설치되면 좋을꺼다. 뭐 Live Templates(예를들어 sout이라고 치면 System.out.println(); 이 나타나는 숏컷같은거)을 새로 등록한 경우, 이것도 알아서 다른 PC에도 설정되면 좋을꺼다. 또는 윈도우를 밀어서 재설치하는 경우나, 새로운 컴퓨터를 샀거나 등의 .. 2023. 7. 28.
[자바] 백준 1103 - 게임 (java) 목차 문제 : boj1103 필요 알고리즘 깊이 우선 탐색, DP, 사이클 판정 memoization을 통해 연산 횟수를 줄이면서 DFS를 진행하는 문제이다. 또한 사이클 판정하는 방법도 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 로직을 말로 하면 간단하다. 1. 가장 왼쪽 위부터 DFS를 진행한다. 2. 사이클이 한번이라도 생기는 경우 -1을 출력하고 끝낸다. 3. 사이클 없이 가장 멀리 간 거리를 .. 2023. 7. 26.
[자바] 백준 1684 - 같은 나머지 (java) 목차 문제 : boj1684 필요 알고리즘 정수론, 유클리드 호제법 의외로 GCD 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N이 2인 경우만 생각해보자. 문제에서 입력된 어떠한 정수 2개를 N1, N2라고 하면, R1==R2가 되려면 아래처럼 식이 전개될 것이다. 따라서 N2-N1 즉, 두 수의 차이는 정수인 Q2-Q1과 D의 곱이 된다. 이 때 Q2-Q1이 뭔지는 모르겠지만 아무튼 정수인 D가 가장 크.. 2023. 7. 25.
[자바] 백준 9241 - 바이러스 복제 (java) 목차 문제 : boj9241 필요 알고리즘 그리디 알고리즘 그리디 풀이는 바로 보일 것 같다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 개인적으로 약간 선 넘는 문제였다. 일단 입력받은 문자열이 A, B 라고 한다면 A와 B 각각 앞부터와 뒤부터 동일한 부분이 어디까지인지 파악한다. 선 넘는다고 생각한 부분은, 당연히 하나 이상의 DNA는 바꿔야 된다고 생각했다. 예를들어 입력이 AAA와 AA일 경우 'AA' 를 제거 .. 2023. 7. 25.
[자바] 백준 16491 - 대피소 찾기 (java) 목차 문제 : boj16491 필요 알고리즘 선분 교차 판정 선분 교차 판정만 할 줄 알면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 10밖에 안되므로, 단순하게 모든 경우 O(N!)을 보면 된다! 즉, N개의 로봇에 N개의 대피소를 모두 배치해보면서 조건을 만족하는 경우가 생기면 출력하면 된다. 조건을 만족하는 경우는, 현재까지 선택된 모든 로봇-대피소 쌍에 대해 선분 교차 판정을 해보면 된.. 2023. 7. 24.
[자바] 백준 16965 - 구간과 쿼리 (java) 목차 문제 : boj16965 필요 알고리즘 너비 우선 탐색 (bfs) 뭔가 bfs와 관련없어 보이지만, bfs 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 모른다면 우선 '이 글'을 참고해보자. 결국 이 문제에서 중요한건 '구간 (x1, y1)에서 구간 (x2, y2)로 이동하려면 x2 < x1 < y2 또는 x2 < y1 < y2를 만족' 이 부분이다. 처음엔 서로소 집합 (disjoint set)으.. 2023. 7. 23.

티스토리툴바