매일코딩

G4 9466 텀 프로젝트 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 정의 각 학생마다 텀 프로젝트를 같이 하고 싶은 팀원 숫자를 갖고 있다. s1 → s2, s2 → s3 ... sn → s1이면 한 팀이 된다. 어느 프로젝트 팀에도 속하지 않은 학생들의 수를 출력하라 학생의 수 2≤n≤100,000 문제 풀이 각 숫자들이 포인팅하는 수를 갖고 있다. 이 문제의 핵심은 사이클이 발생하지 않는 수가 몇개인지 카운팅하는 것이다. 현재 정점에서 다음 정점을..

백준 P5 14003 가장 긴 증가하는 부분수열5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 백준에 가장 긴 증가하는 수열 시리즈가 있는데 그 중 플래티넘5로 끝판왕격인 놈이다. LIS로 풀면 되겠거니 했는데 LIS에서 같은 위치를 참조하는 수일때 뒤에 입력되는 원소를 출력하는 로직을 처리하는게 까다로웠다. 문제 풀이 1. binarySearch로 LIS에 가장 긴 증가하는 수열의 원소를 넣어준다. 2. 입력..

개미의 위치 x, y로부터 t만큼 이동할 때의 위치이다. 그냥 x, y에서 각각 t를 더한 후 넓이와 높이로 나눈 나머지가 된다. 그러나 문제는 개미가 벽에 닿으면 방향이 반대로 바뀐다는 점이다. 분명 규칙성이 있는데 안떠올라서 그림을 그리면서 풀었다. 방법 1. (x + t) / w가 짝수일때는 (x + t) % w이 되고 홀수일 땐 - (x + t) % w이 된다. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_S5_10158_개미 { public static void ..

문제 링크: www.acmicpc.net/problem/4307 개미의 방향이 바뀐다는 사항이 훼이크였던 문제였다. 이것때문에 얼마나 고생을 했던지;; 가장 늦은 시간을 구하는 방법이다. 중간에 개미가 부딪쳐서 다시 돌아가는데까지 걸리는 시간과, 그대로 쭉 L까지 가는 시간은 결국 같다. L이 10이고 개미가 2, 6, 7일때 예시를 들어보겠다. - 2 개미가 6 개미와 4에서 만난다 . cnt = 2 - 6 개미가 10 방향으로 되돌아가다 7 개미와 4.5에서 마주친다. cnt = 0.5 - 6 개미가 0 방향으로 가는데까지 걸리는 시간. cnt = 6.5 개미가 가장 늦게 떨어지는 시간은 8초다. 그런데 이는 2 개미가 10까지 쭉 갔을 때 걸리는 시간과 같다. 모든 개미는 1cm/s로 동일하게 움직..

시계방향으로 차례대로 수를 입력해야 하는 문제이다. 방향을 상, 우, 하, 좌로 이동할 수 있게 좌표 배열을 설정해주었다. 구현방법 1. 방향대로 한칸씩 이동하며 cnt를 입력해준다. 2. 다음칸이 좌표 범위 밖이거나 이미 점거된 좌표면 방향을 틀어준다 3. cnt가 K와 만나면 종료해준다 주의! - k가 R * C보다 크다면 0을 바로 출력하고 탐색하지 않아 시간을 단축시킨다. 회고 알고리즘 분류에 재귀가 있어서 처음에 재귀로 풀다가 안돼서 while문으로 푸는 방향으로 고쳤더니 정답이었다. 보통 배열 문제를 풀 때는 r, c 기준으로 생각했기 때문에 배열에 체크할 때 x, y가 헷갈렸다. 또한 while의 종료조건을 cnt < K로 하면 쉽게 풀릴텐데 이것을 찾는것도 한참 걸렸다. 실버 5밖에 안되는..

[SWEA D3 1493 수의 새로운 연산] 체감상 난이도는 D4였다ㅠㅠ 수에 약해서 진짜 너무 힘들었음.. 대각선으로 수가 1씩 늘어나는 규칙을 찾고 그 규칙을 방정식으로 구현할 수 있으면 할만하다. 두 가지 방식으로 풀 수 있는데 미리 배열을 만들고 각 배열에 어떤 값이 들어가는지 계산하고 문제 시작 테스트케이스마다 값이 들어오면 즉시 좌표로 계산하고, 다시 좌표를 값으로 변환 배열을 200 x 200 하니까 부족하고 300x300으로 하면 괜찮았다. 보면 y가 1씩 늘어날때마다 차가 1씩 늘어나는 계차수열이다. 그럼 다음과 같은 공식을 도출할 수 있다. y가 n일 때, y 레벨에서 가질 수 있는 값의 범위: $$ 1 + {n \times (n-1) \over 2} \le y의 범위 \le 1 + {..

조합으로 풀 수 있는 문제다. 단어는 무조건 anta와 tica가 포함되므로 가르쳐야 할 알파벳에 a,c,i,n,t 를 기본으로 저장해준다. boolean[26] 배열로 알파벳의 사용여부를 체크할 수도 있지만 나는 비트의 자리수를 체크해 알파벳이 사용됐는지 안됐는지를 체크해줬다. flag에 a,c,i,n,t를 사용해줘야하니 각 자리를 1로 표기한다. K가 5보다 작으면 애초에 읽을 단어가 없으니 0, K가 26이면 전부 읽을 수 있으니 N으로 예외처리를 해줬다. flag를 이용해 선택할 알파벳 K-5개를 뽑음. 다 뽑으면 각 단어의 알파벳을 하나씩 체크하며 현재 뽑은 단어로 단어를 만들 수 있는지 확인한다. 어차피 단어는 앞에 4개, 뒤에 4개는 볼 필요 없으므로 범위설정을 4 ~ word.length(..

[SWEA D3 6808 규영이와 인영이의 카드게임] 순열로 구할 수 있는 문제이다. 규영이가 낼 수 있는 카드 9개의 순서는 고정되어 있으니 인영가 낼 수 있는 카드 9개 순서만 순열로 구해주면 된다. 처음에 재귀함수 인자로 규영이와 인영이의 현 라운드 sum을 보내려고 했는데 너무 복잡해져서 포기. 인영이의 카드 순서만 순열로 구하겠다고 생각하면 간단해지는데 유도조건에서 계산을 하려다보면 꼬인다. 기저조건에서 규영이 카드랑 인영이 카드를 비교하고, 더해준 결과값으로 win, lose를 구해주니까 간단해졌다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.S..

[SWEA D4 1233 사칙연산 유효성 검사] 완전이진트리 문제이다. 수식이 성립되려면 숫자 사이에 무조건 연산자가 있어야 한다. 8*2 이렇게. 그러면 단말 노드(리프노드)는 무조건 숫자여야 하고, 연산자 노드는 무조건 자식 노드(왼, 오)가 둘 다 있어야 한다. 처음엔 dfs로 중위순회해서 8/2*6-4 이런 순서로 전부 노드를 검사해야하나 싶었다.그런데 문제를 풀다 보니 입력이 주어질 때 [노드 번호 노드정보 왼노드 오른노드] 이렇게 주어지는게 아닌가? 그럼 그냥 입력받으면서 현재 노드가 숫자인데 뒤에 자식 노드 정보가 있는지, 연산자인데 뒤에 자식 노드가 없는지 두 가지만 체크해주면 된다. import java.io.BufferedReader; import java.io.IOException; ..