Algorithm/BOJ
-
[BOJ] 최단경로Algorithm/BOJ 2020. 8. 25. 19:12
[1753] 최단경로 https://www.acmicpc.net/problem/1753 방향 그래프 정보와 시작점이 주어졌을 때 다른 모든 정점으로의 최단 경로를 구하는 프로그램 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) Solution 다익스트라 알고리즘을 알고 있다면 쉽게 아이디어를 떠올릴 수 있지만 정점 V의 개수가 최대 2만개로 인접 행렬로 풀이했을 경우 메모리 초과로 틀리게 된다. 인접 리스트와 우선순위 큐로 풀이하였다. 최단경로 FAQ https://www.acmicpc.net/board/view/34516 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ..
-
[BOJ] 심심한 준규Algorithm/BOJ 2020. 7. 2. 18:58
[2892] 심심한 준규 https://www.acmicpc.net/problem/2892 문제 설명의 표에있는 excrypted message가 입력이 되고, 암호화된 메시지의 글자가 문자인지 아닌지 출력하는 문제 Solution 애초에 xor 연산하는 방법도 몰라서 답을 봤다. excrypted message에서 문자와 문자가 아닌 글자의 숫자 범위를 보고 유추하는 방법이였다. '0'~'9'까지 숫자키와 'a'~'z'까지의 소문자를 xor 연산했을 때 나오는 결과 범위는 64~95 까지 이고, '0'~'9'까지 숫자키와 ' ', '.'을 xor 연산했을 때 나오는 숫자범위는 16~31 까지이다. excrypted message를 16진수 정수로 변환했을 때 어떤 범위에 속하는지에 따라 '-' 혹은 '..
-
[BOJ] 나는야 포켓몬 마스터 이다솜Algorithm/BOJ 2020. 5. 27. 16:59
[1620] 나는야 포켓몬 마스터 이다솜 https://www.acmicpc.net/problem/1620 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 말하면 포켓몬 이름을 말하는 는 프로그램 Solution HashSet 두 개를 만들어 문자가 입력되면 숫자 출력, 숫자가 입력되면 문자가 출력되도록 구현 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..
-
[BOJ] 회사에 있는 사람Algorithm/BOJ 2020. 5. 27. 15:36
[7785] 회사에 있는 사람 https://www.acmicpc.net/problem/7785 어떤 사람이 회사에 들어왔는지, 나갔는지 기록된 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램 Solution Set 자료구조에서 로그 기록이 "enter"일 경우 put, 아닐경우에 remove() 연산 모든 기록대로 연산을 끝낸 후에 배열에 넣고 오름차순 정렬한 다음 역순 출력 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.io.BufferedReader; import java.io.IOExcepti..
-
[BOJ] 패션왕 신해빈Algorithm/BOJ 2020. 5. 27. 14:51
[9575] 패션왕 신해빈 https://www.acmicpc.net/problem/9375 해빈이가 가진 옷들로 만들 수 있는 모든 조합의 수 구하기 Solution 해빈이가 가진 의상의 이름과 종류가 공백으로 주어지면 의상의 종류와 count를 HashMap에 저장한다. answer = (의상종류1 + 안 입는 경우) * (의상종류2 + 안 입는 경우) * (...) * (의상종류n + 안 입는 경우) - 다 안 입는 경우 answer *= ( map.get(key) +1 ); answer -= 1; 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..
-
[BOJ] 연구소3Algorithm/BOJ 2020. 4. 28. 21:07
[17142] 연구소3 https://www.acmicpc.net/problem/17142 연구소2의 응용 문제 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. Solution 바이러스 자체에 좌표와 더불어 시간을 저장할 수 있는 step 멤버변수를 설정해서 풀 수 있었다. 입력에서 빈칸은 -1, 바이러스 칸은 -2로 저장 permutation으로 m개의 바이러스를 선택해서 모든 경우에 대해 BFS 함수를 돌렸다. map[nx][ny]의 빈칸 or 비활 바이러스 여부에 따라..
-
[BOJ] 캐슬디펜스Algorithm/BOJ 2020. 2. 13. 15:06
[17135] 캐슬디펜스 https://www.acmicpc.net/problem/17135 게임이 진행되는 곳은 크기가 NXM인 격자판이다. 각 칸에 포함된 적의 수는 최대 하나이며, N+1행의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 성이 있는 칸(N+1)에 궁수 3명을 배치하려고 한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적은 아래로 한 칸 이동하며 성이 있는 칸으로 내려간 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 입력 : N(행) M(열) D(거리 제한), NxM(격자판의 상태) 출력 : 궁수의 공격으로 제거할 수 있는 적의 최대 수 Solution permutat..
-
[BOJ] 배열 돌리기 3Algorithm/BOJ 2020. 2. 11. 21:06
[16935] 배열 돌리기 3 https://www.acmicpc.net/problem/16935 d크기가 N x M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1. 상하 반전 2. 좌우 반전 3. 오른쪽으로 90도 회전 4. 왼쪽으로 90도 회전 5, 6. 배열을 크기가 N/2 x M/2인 4개의 부분 배열로 나누어 시계방향, 반시계방향으로 이동 Solution 문제 조건에 맞추어 구현하였다. 하면서 너무너무너무 풀기 싫었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46..