본문 바로가기

전체 글1104

[자바] 백준 23813 - 회전 (java) 목차 문제 : boj23813 필요 알고리즘 구현, 문자열, 수학 문자열로 문제에서 제시된대로 구현해주는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 제한이 짧아서 그냥 문자열 자체로 자르고 붙이고 Integer.parseInt로 정수로 변경해주면서 구현해도 상관없다. 내 경우엔 숫자로 바꿔서 계산했다. 우선 mult는 입력으로 들어온 숫자의 자리수-1 만큼 0이 붙은 숫자이다. 예를들어 "12345"라면 .. 2023. 4. 3.
[종만북] ASYMTILING - 비대칭 타일링 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-ASYMTILING 풀이 일단 대칭인 경우는 생각하지 않고, 2xn 타일링부터 생각해보자. dp[x]를 x번째 열까지 타일을 높는 경우의 수라 하자. 이 경우 dp[5]의 경우 아래 그림처럼 dp[4]에 2x1 타일을 놓는 경우와, dp[3]에 1x2 타일 2개를 놓는 경우가 있을 것이다. 즉, dp[x] = dp[x-1] + dp[x-2] 로 구할 수 있다. 답은 dp[n]이 된다. 그럼 다음으로 대칭인 경우를 제외해보자. 열이 홀수개일 경우 대칭인 경우는 이하처럼 중간에 2x1 타일이 있는 경우이다. 즉, dp[n]에서 dp[(n-1)/2] 를 빼주면 된다! (대칭인 경우를 빼면 되므로) 열이 짝수개인 경우엔 다음의 두 가지 경우.. 2023. 4. 3.
[종만북] PI - 원주율 외우기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-PI 풀이 각 테스트케이스에 대해 dp[x] 를 x번째 숫자까지 표현하기 위한 최소 난이도라 정의하자. 저 정의대로 구할수만 있다면 답은 dp[문자열 길이] 가 될 것이다. 현재 문자열의 z번 문자를 보고 있다고 해보자. 이 때 dp[x]가 x번째 숫자를 표현하기 위한 최소난이도임이 확실하다면 dp[z]는, min( dp[z-3] + '이전 3개의 문자 난이도', dp[z-4] + '이전 4개의 문자 난이도', dp[z-5] + '이전 5갱의 문자 난이도') 라고 할 수 있다. 따라서 이대로 구현해주면 된다! 말한대로 이전 3개, 4개, 5개의 난이도를 계산하면서 최소값을 갱신해나가면 된다. 점수 계산은 score() 함수로 처리했다.. 2023. 4. 2.
[자바] 백준 2033 - 반올림 (java) 목차 문제 : boj2033 필요 알고리즘 구현 반올림을 직접 해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력으로 들어온 숫자를 각 자리수별로 배열로 잘라두고 직접 반올림을 진행해주면 된다! 예를들어 "446"일 경우 아래처럼 진행된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main {.. 2023. 4. 2.
[종만북] WILDCARD - Wildcard (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-WILDCARD 풀이 우선 '*'이 연속으로 있는 경우는 처리만 어렵게 만들고 하나만 있는 경우와 동일하다. 따라서 입력받은 W에서 '*'이 연속으로 있다면 하나로 변경해줬다. 즉, "ab********c" 라면 "ab*c"로 변경해준다. private String compressContinuousAsterisk(String w) { while (w.indexOf("**") != -1) { w = w.replace("**", "*"); } return w; } 그럼 이제 연속된 '*'이 하나로 합쳐진 W와 현재 보고 있는 문자열 cur에 대해 각각 포인터를 두고 움직인다고 해보자. 이 경우 두 개의 포인터가 가르키는 문자열이 동일하거.. 2023. 4. 2.
IntelliJ는 왜 jdk(java)를 설치 안해도 동작할까? 어찌보면 당연한내용인데, 인텔리제이를 처음 썼을 땐 엄청 신기했던 것 같다. 인텔리제이의 경우 jdk를 설치하지 않아도 잘 동작한다. 혹시 당연히 자바를 설치해야 한다고 생각해서 따로 설치하고 환경변수까지 등록해서 사용중인 사람들도 있을 것 같은데, 사실 환경변수에 등록 안되있어도 인텔리제이는 혼자서 잘 동작한다. 프로젝트마다 독립적으로 동작하기 위해 jdk를 환경변수로 등록 안하고 사용하는게 더 좋을 것 같다. 그렇지 않으면 프로젝트마다 실행하기 전에 환경변수를 가서 버전 바꿔주거나, 리눅스쪽이라면 sdkman 같은걸로 자바 버전을 변경해주면서 써야 할 것이다. 인텔리제이에서는 File -> Project Structure에서 자바 버전을 선택할 수 있고, 또 원한다면 추가할 수 있다. 이렇게 받아진 .. 2023. 3. 28.
[자바] 백준 25904 - 안녕 클레오파트라 세상에서 제일가는 포테이토칩 (java) 목차 문제 : boj25904 필요 알고리즘 구현, 시뮬레이션 문제에서 제시된 방식대로 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어차피 목소리 높이의 상한선은 200이므로, N이 몇이 되든 최악의 경우에도 200번만 확인해보면 된다! 따라서 어렵게 생각할 것 없이, N개짜리를 순서대로 계속 확인하면서 매번 X를 1씩 증가해준다. 그리고 X의 값이 해당 위치보다 더 커지면 해당 위치를 출력해주면 된다. .. 2023. 3. 27.
[종만북] CLOCKSYNC - Synchronizing Clocks (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-CLOCKSYNC 풀이 시계 자체에 초점을 맞추면 답이 안나온다. 스위치가 10개 밖에 없다는 부분에 초점을 맞춰보자. 결국 시계는 4번 돌면 제자리다. 따라서 각 10개의 스위치는 3번 이상 누를 일이 없고, 그럼 O(C x 4^10)으로 처리가 가능함을 알 수 있다. 즉, 시계가 몇칸인지는 상관 없고, 그냥 스위치가 10개이고 각각 최대 3번까지 누를 수 있으니 4x4x... 를 해주면 되는 것이다. 코드 : github import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTo.. 2023. 3. 20.
[종만북] BOARDCOVER - 게임판 덮기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-BOARDCOVER 풀이 모든 칸에 블록을 놓아본다고 하자. 이 경우 흰 칸의 수는 50을 넘지 않는다고 했고, 블록 하나에 3칸씩이므로 최대 16개를 덮으면 된다. 블록의 모양은 4가지이므로, O(C x 4^16) 이 필요하다. 방법을 좀 다르게 생각해서 각 칸마다 놓거나 안놓거나 해봐도 O(C x 2^50)이므로 마찬가지로 불가능하다. 여기서 생각해볼 점은, 블록의 3칸 중 가장 상단 좌측의 위치를 기준으로 놓는다고 생각해보자. 그리고 주어진 게임판의 상단부터 하단으로, 좌측에서 우측으로 쭉 보면서 블록을 놓는다고 해보자. 이렇게 되면 만약 블록을 놓지 않고 그냥 지나쳤을 때, 해당 위치엔 다시는 블록을 놓을 수 없음이 증명된다... 2023. 3. 20.
[종만북] PICNIC - 소풍 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-PICNIC 풀이 n명을 일렬로 놓는 경우의 수는 n! 이다. 따라서 일렬로 놓고 2명씩 쌍을 짓는다고 생각해보면 O(C x n!)가 필요하므로 통과할 수 없다. 더 효율적으로 하려면 2명씩 짝지어볼 수 있다. 이 때, 주의할 점은 아래의 경우들은 모두 같은 경우라는 점이다. '일부만 다르더라도 다른 방법' 이라고 써져 있는 부분은 짝이 다를 경우이지, 이미 정해진 쌍에 대해서는 상관이 없다. (0, 1), (2, 3) (0, 1), (3, 2) (1, 0), (2, 3) (2, 3), (0, 1) (3, 2), (1, 0) ... 등 그리고 모든 학생이 쌍에 포함되어야 하므로, 그냥 쌍을 지어주는 방향을 고정시켜도 결과는 동일하다... 2023. 3. 20.

티스토리툴바