https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 생각 듣도 못한 사람 - A그룹 / 보도 못한 사람 - B그룹 듣도 보도 못한 사람 - A U B (합집합) A그룹을 해시에 저장하고 B그룹 사람 이름의 key값이 존재하는지 확인, 존재하면 count ++ 시간복잡도? 정렬된 값으로 저장하는 것보다 해시가 가장 빠르다고 생각함. 실험을 통해 알아보자! 1. 배열 HashMap을 사용하지 않으면 시간초과남 2. HashMap 사용하기 import..
알고리즘/백준
https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net bfs를 쓰면 시간이 너무 오래걸릴 것 같아 수식으로 해결해봤다. 규칙을 찾는 데 시간이 좀 걸렸지만, 수식을 사용하기 때문에 수행시간이 빠르다. 1. 갈 수 없는 곳 판별하기 이렇게 표로 슥슥 그려보면 갈 수 없는 지점이 보인다 행(row)은 시작지점의 2의 배수만큼 떨어져 있어야하고 열(col)은 시작지점과 (2 x..
https://www.acmicpc.net/problem/9324 9324번: 진짜 메시지 스파이들은 사령부와 통신하기 위해서 SMTP(비밀 메시지 전송 프로토콜)를 사용해 비밀 회선으로 전자 메시지를 보낸다. 메시지가 적들에 의해 조작되어 보내진 것이 아닌 진짜 메시지라는 것 www.acmicpc.net 문제를 대충 읽어서 3번째만 바뀌는 줄 알았다. 알고보니 3번 째 나올 때마다 계속 두 번씩 나와야했다;; ex) A B A B AA B A B A B AA 내 풀이(HashMap 사용) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; im..
2902: KMP는 왜 KMP일까? - 브론즈2 https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.security.NoSuchAlgorithmException; import java.util.StringTokenizer; public c..
BASE64란? 8bit 이진 데이터를 문자 코드에 영향을 받지 않는 공통 ASCII 문자로 표현하기 위해 만들어진 인코딩 방식 ASCII문자 하나는 64진법의 숫자 하나를 의마한다 (base64를 번역하면 64진법이라는 뜻) 전자메일을 통한 이진 데이터 전송 등에 많이 사용 Base64 변환 표는 다음과 같다(출처: 나무위키) https://www.acmicpc.net/problem/10935 10935번: BASE64 인코딩 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.net 자바코드 public class Main { public static void main(String[] args) throws I..
SHA-256 이란? SHA 알고리즘의 한 종류 256비트로 구성되며, 64자리 문자열을 반환함 블록체인에서 가장 많이 채택하여 사용하고 있음 2^256 가지의 경우의 수를 만들 수 있다 자바에서 SHA-256로 인코딩 된 문자열을 만드는 방법 MessageDigest 인스턴스를 만든다(SHA-256으로) messageDigest를 바꾸고자하는 string의 바이트를 넣어 update한다 byte값을 받아 hex값으로 바꾼다 출력 백준문제 10930: SHA-256 https://www.acmicpc.net/problem/10930 10930번: SHA-256 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.n..
https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2
https://www.acmicpc.net/problem/14562 14562번: 태권왕 첫째 줄에 테스트 케이스의 수 C(1 ≤ C ≤ 100)이 주어진다. 둘째 줄부터 C줄에 걸쳐 테스트 케이스별로 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100) www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffe..
https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 연결리스트 사용 bfs 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOE..
https://www.acmicpc.net/problem/14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net 반례들 (예시 입력만 돌아가면 무지성으로 제출하는 습관이 있음. 그래서 이제부터는 몇 가지 반례들을 돌려보려고 한다) 5 1 1 1 1 1 1 => 5 3 7 1 1 1 => 1 5 3 1 5 2 5 1 => 4 자바코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre..
