java

https://www.acmicpc.net/problem/1043문제분석진실을 알고 있는 사람만 조심해야 하는게 아니라, 진실을 알고 있는 사람이랑 "같이 파티하는 사람" 도 조심해야 한다. 쉽게 설명하자면, 진실을 알고 있는 사람이 진실을 퍼뜨린다. 그래서 거짓말을 하기 위해서는 진실을 알고 있는 사람과 아예 엮이지 않게끔 말해야 한다.N= 50이니, while로 반복을 하면 O(N^2)이여도 2500회밖에 안된다. 따라서 while문을 활용하여 해결하였다. 코드import java.util.*;import java.io.*;public class Main { public static void main(String[] args)throws IOException{ BufferedRead..

https://www.acmicpc.net/problem/2413 문제분석Greedy를 활용해 문제를 풀어야 한다.최적 해는 다음과 같다.1. 짝을 맞춰야 한다. n은 n-1과 위치를 바꾸는 것 밖에 안되기 때문.2. n이 n-1보다 높은 자릿수(순열의 앞쪽(왼쪽))에 있을 때, 무조건 바꿔야 한다. 가장 작은 순열을 구해야 하기 때문.3. 순열의 앞쪽(왼쪽)부터 짝을 찾아서 바꿀 수 있는지 여부를 확인해나아가야 한다.코드import java.util.*;import java.io.*;public class Main{ public static void main(String[]args)throws IOException{ BufferedReader br = new BufferedReader..

https://www.acmicpc.net/problem/2457 군자의 복수는 10년이 걸려도 늦지않는다. 문제 해결을 실패하고, 2년 좀 안되는 시점에 다시 시도해서 성공했다! 너무 기쁘다!!!문제분석어쩌면 살짝 억울하다고 느끼는 점은, 아이디어 자체는 2년 전 시도와 완벽하게 동일하다. 단지 언어 변경과 그리디 알고리즘에 대한 공부(이게 가장 큰 것 같긴 하다)를 통해 생각보다 쉽게 해결하였다.사실 쉬운 정도가 아니라, 2년 전 시도 코드와 비교하면 말도 안되게 짧다. 부분 문제의 최적해를 이어서 전체 문제의 최적해로 나아간다는 아이디어를 통해 대폭 줄인 것 같다. 풀이는 다소 간단하다. 꽃을 심으면서, 다음 조건을 만족하면 된다. 1. 직전의 꽃이 죽기 전에 피는 꽃들 중 하나를 무조건 골라야 ..

DFS : Depth-First Search - 깊이 우선 탐색가능한 한 깊이 들어가며 탐색한 뒤, 더 이상 갈 수 없을 때 되돌아오는 방식. 스택 구조를 기반으로 하며, 재귀 또는 명시적 스택 이용한다. JAVA는 구조적으로 JVM에서 각 쓰레드별로 고정된 크기의 콜 스택을 주며, 이 크기가 매우 작다. 따라서 많은 재귀 depth를 가지지 못한다. 그러므로 명시적으로 스택 자료구조를 사용한다.DFS 구현 시 유의사항1. 재귀 깊이를 구현 언어가 감당할 수 있는지 확인(JAVA는 위험이 큼).2. 방문 체크(visited) 필요 - 무한 탐색을 막기 위함(트리가 아닌, 사이클의 경우). BFS : Breadth-First Search - 너비 우선 탐색시작 정점에서 가까운 정점부터 차례로 탐색, ..

https://www.acmicpc.net/problem/7570문제분석제목 그대로 순서대로 줄을 세우는 것이다. 단, 맨 앞이나 맨 뒤로만 보낼 수 있다는 조건을 지켜야 한다.예를들어, 5 4 2 3 1로 서있는 경우, 1을 맨 앞으로,  4를 맨 뒤로, 5를 맨 뒤로 보내야 1 2 3 4 5로 정렬이 된다.최소한으로 움직여서 정렬이 완료되는 경우, 그 최소한으로 움직인 값은?해결과정"덩어리" 를 만들기로 했다. 여기서 "덩어리" 의 정의는 다음과  같다.1. 연속적인 수(3, 4, 5, 6...)2. 이 수들은 붙어있을 필요는 없다(3, 5, 2, 6, 1, 7, 4...)->덩어리 5,6,73. 최소한으로 움직이는 경우는, 이 덩어리들 중  가장 큰 덩어리가 움직이지 않는 경우.이 덩어리가 가장 클..

https://www.acmicpc.net/problem/1034문제분석가로로 111111...와 같이 모든 수가 1로 바뀌어야 켜졌다 라고 한다고 한다. 버튼을 누르면 해당 열 의 모든 숫자가 바뀐다(1과 0 서로 치환).역시 간단한 방법인 모든 경우를 탐색하려고  하니, 신경써야 할 반례가 너무 많았다. 다른 방법이 있나 찾다가, 이전 문제에서 사용했던, 순차적으로 탐색하면서 최대값을 저장하고, 최댓값보다 큰 경우에 최댓값을 갱신하는 방법을 사용하기로 하였다. 램프가 켜지고 꺼지면서 완성되는 열의 수를 각각 파악해야 한다(실제로 숫자를 변경하면, 시간복잡도에서 탈락).해결과정중복이 가능하므로, K의 갯수와 한 행의 0의 갯수의 홀수 짝수 여부가 같아야 한다(다른 경우, 무조건 한번 더 눌러야 하므로 ..