본문 바로가기
반응형

전체 글1305

[BOJ] 백준 1764 듣보잡 출처: https://www.acmicpc.net/problem/1764 Input 3 4 ohhenrie charlie baesangwook obama baesangwook ohhenrie clinton Output 2 baesangwook ohhenrie 원소의 중복 여부를 파악하기 위해 contain() 함수를 이용했지만 시간 제한을 만족 못함. Map을 이용해 『key : value』 중복 여부 처리 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com import .. 2021. 2. 22.
HTML 태그 주석 <!-- --> 각 언어마다 주석 기능이 존재하며, 기호는 동일한 것도 있지만 다른 것도 존재한다. HTML 소스도 마찬가지로 주석 기능이 존재하며, 소스에만 표시하며 화면상에 보이지 않는다. ※ 모든 브라우저에 상관없이 지원 ※ CSS /* */과 // 로 사용 아래와 같이 HTML 태그 사이에서 영역을 구분할 때 사용되기도 한다. 2021. 2. 22.
[BOJ] 백준 17070 파이프 옮기기 1 출처: https://www.acmicpc.net/problem/17070 Input 6 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Output 13 파이프pipe 종류 * 종류마다 이동 방법이 다르다. ① 『 → 』 의 경우, 2가지 ② 『 ↓ 』 의 경우, 2가지 ③ 『 ↘ 』 의 경우, 2가지 - Pipe의 끝지점 경로 고려. - Pipe 상태에 따른 경로를 고려하면 아래의 범위에서 움직인다. 가로, 세로 방향은 다음 끝지점이 벽이지만 확인하면 되지만 대각선의 경우에는 3 군데를 확인해야 한다. ※ Pipe 이동이 처음부터 불가능하다. Input 5 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .. 2021. 2. 22.
[BOJ] 백준 17136 색종이 붙이기 출처: https://www.acmicpc.net/problem/17136 Input 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 Output 9 5가지 종류의 색종이로 10 x 10 종이 위에 『 1 』을 색종이 최소 개수로 덮는 문제입니다. ※ 색종이 종류: 1×1, 2×2, 3×3, 4×4, 5×5 - 『 0 』인 부분을 덮어서는 안됩니다. - 색종이가 겹쳐서는 안됩니다. Greedy 방식으.. 2021. 2. 22.
[BOJ] 백준 10814 나이순 정렬 출처: https://www.acmicpc.net/problem/10814 Input 3 21 Junkyu 21 Dohyun 20 Sunyoung Output 20 Sunyoung 21 Junkyu 21 Dohyun 회원을 나이 순, 나이가 같으면 가입한 순 정렬하는 문제입니다. 우선순위 큐를 이용하여 처리. import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); PriorityQueue pq = new Priority.. 2021. 2. 22.
[BOJ] 백준 1708 블록 껍질 출처: https://www.acmicpc.net/problem/1708 Input 8 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 Output 5 블록 껍질(Convex Hull) 구현하는 문제 블록 껍질(Convex Hull) Cunvex Hull(블록 껍질)은 2차원 평면상에 여러개의 점이 있을 때, 그 점들 중에서 일부를 이용하여 볼록 다각형을 만들되, 볼록 다각형 내부에 사용하지 않은 모든 점을 포함시키는 것을 의미합니 zoosso.tistory.com ① 기준점(first) 설정 ← 일반적으로 y 좌표가 가장 작은 것. (가장 작은 y 좌표값이 2개 이상이라면 x 좌표 값이 작은 것 ) ② 기준점(first)을 중심으로 각도순 정렬 - CCW(반시계 방향), 일직선상 거리 비교 ※.. 2021. 2. 22.
블록 껍질(Convex Hull) Cunvex Hull(블록 껍질)은 2차원 평면상에 여러개의 점이 있을 때, 그 점들 중에서 일부를 이용하여 볼록 다각형을 만들되, 볼록 다각형 내부에 사용하지 않은 모든 점을 포함시키는 것을 의미합니다. 이를 구현하는 알고리즘은 크게 3가지 존재합니다. (1) Jarvis March 알고리즘 ← O(NH) (2) Monotone Chain 알고리즘 ← O(NlogN) (3) Graham Scan 알고리즘 ← O(NlogN) Graham Scan 알고리즘을 이용한 Convex Hull 구현 ① 첫번째 기준 좌표를 설정합니다. 일반적으로 y 좌표가 가장 작은 것. (가장 작은 y 좌표값이 2개 이상이라면 x 좌표 값이 작은 것) ② 기준점(first)을 중심으로 각도순 정렬(반시계 방향(CCW)으로 좌표 .. 2021. 2. 22.
[BOJ] 백준 17135 캐슬 디펜스 출처: https://www.acmicpc.net/problem/17135 Input 6 5 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 Output 9 - 궁수의 위치는 끝 행 + 1에 위치하며 3명이 배치됩니다. (각 칸의 궁수는 최대 1명 배치) 턴의 진행 방식 - 3명의 궁수는 동시에 가장 가까운 거리의 적 1명을 공격 - 공격할 수 있는 거리는 D 이하. 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2| - 가장 가까운 거리의 적이 여러명인 경우 가장 왼쪽에 있는 적을 공격 - 적은 여러명의 궁수들로부터 공격될 수 있습니다. - 공격 받은 적은 게임에서 제외 - 궁수의 공격이 끝나면 살아남은 적이.. 2021. 2. 22.
[SWEA] 3954 파이의 합 출처: [SWEA] SW 문제해결 심화 - 이산수학 Input 3 1 30 100 200 1000 2000 Output #1 278 #2 9228 #3 912796 ϕ(1) ~ ϕ(N) 합을 구해야 하므로 ϕ(i)를 하나씩 구해서 합하면 TLE 발생 ① 에라토스테네스의 체를 이용해 소수 판단. 소수 (Prime Number) 찾기 - 3 소수 (Prime Number) 찾기 - 3 해당 게시글은 에라토스테네스의 체를 이용해서 소수 찾기를 구현한 게시글입니다. - 소수 (Prime Number) 찾기 - 1 - 소수 (Prime Number) 찾기 - 2 ★ 에라토스테네스의 체의 핵심은 소수의 배수를 제 zoosso.tistory.com ② 소수 여부에 따른 오일러 함수 처리 오일러 피(파이) 함수 ϕ(n.. 2021. 2. 22.
[BOJ] 백준 4355 서로소 출처: https://www.acmicpc.net/problem/4355 Input 7 12 0 Output 6 4 오일러 피(파이) 함수 ϕ(n)를 이용합니다. 오일러 피(파이) 함수(Euler's phi function) 오일러 피(파이) 함수 ϕ(n) 1~n까지의 수 중에서 n과 서로소인 수의 갯수 ※ 서로소 관계: 두 수 a, b의 공약수가 1뿐인 두 정수를 의미한다. ϕ(1) = 1 (1은 1과 서로소) ϕ(8) = { 1, 3, 5, 7 } =.. zoosso.tistory.com import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamRead.. 2021. 2. 22.
반응형

티스토리툴바