코딩 기록지

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 11265번 끝나지 않는 파티를 풀었습니다. 이를 정리해보고자 합니다. 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 본문 1) 문제 2) 과정 shortest path니까 다익스트라 알고리즘을 사용하면 되겠지 싶었는데, 자꾸 시간초과가 발생하길래 다른 방법을 찾다 해당 문제를 플로이드 와샬 알고리즘으로 풀어야한단걸 알게되었습니다... 처음엔 오히려 다 구하면 오래 ..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1916번 최소비용 구하기를 풀었습니다. 이를 정리해보고자 합니다. 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 본문 1) 문제 2) 과정 처음 풀었던 shortest Path(최단거리) 문제라서 꽤나 오랜 시간... 5시간 조금 넘게 걸렸습니다... 분명 거의 다 되는데 왜 안될까 하며 삽질하는 시간이 길었어요... 이 문제는 노드에는 특별한 조건이나 문제가 없고..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 18352번 특정 거리의 도시 찾기를 풀었습니다. 이를 정리해보고자 합니다. 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 본문 1) 문제 2) 과정 18352번은 다익스트라 알고리즘의 기본흐름을 이해하니까 30분도 안되서 에러도 없이 한번에 풀어냈던 아주 간단한 문제였습니다! 제가 사용한 아이디어는 최단거리를 계산할 때 많이 사..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1753번 최단경로를 풀었습니다. 이를 정리해보고자 합니다. 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 본문 1) 문제 2) 과정 이번 문제는 푸는데 2시간 정도 걸렸습니다. 1916번 문제를 풀고나니까 쉽게 풀 수 있던 문제였어요 :) [알고리즘풀이]백준 1916 : 최소비용 구하기 JAVA 목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 ..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 11043번 경로 찾기를 풀었습니다. 이를 정리해보고자 합니다. 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 본문 1) 문제 2) 과정 이번 문제를 푸는데는 30분 정도 걸렸어요. 에러도 한번없이 빠르게 성공한 문제였답니다. 그 정도로 입력부분만 처리할줄알면 기본 탐색 알고리즘(좀 더 나아가면 다익스트라알고리즘)과 별반 다를게 없던 간단한 문제였습니다. 그리고 개선하는데 좀 오랜 시간을 투자하여 속도를 2배감축시켰답니다! 그 과정은 깃헙에서 ..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 14267번 회사 문화1을 풀었습니다. 이를 정리해보고자 합니다. 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 본문 1) 문제 2) 과정 이번 문제는 1시간 30분 정도 걸려서 풀었어요. 아이디어는 빨리 나왔지만 시간초과 때문에 고전했던,,, 문제입니다. 제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다. 1. 인덱스 별 상사를 읽을 때, 탐색 개선을 위해 HashSet으로 [상사(입력값)].a..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1068번 트리를 풀었습니다. 이를 정리해보고자 합니다. 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 본문 1) 문제 2) 과정 이번주에 풀었던 과제들은 대부분 쉬웠어요. [알고리즘풀이]백준 1240 : 노드 사이의 거리 JAVA 목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1240번 노드 사이의 거리를 풀었습니다. 이를 정리해보..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1240번 노드 사이의 거리를 풀었습니다. 이를 정리해보고자 합니다. 본문 1) 문제 2) 과정 이번 문제는 무난무난하게 1시간 정도 걸려서 풀었습니다. DFS도 해보고 BFS도 해봤는데 DFS로 했을 때 메모리 초과가 발생해서 BFS로 작성을 완료했던 문제입니다. BFS도 처음에 멍청하게 방문했던 모든 경로의 가중치를 더해버려서 이상한 값이 나왔었어요 ㅋㅋㅋㅋㅋㅋ 그래도 해결해서 잘 마쳤습니다. 제가 이 문제를 풀며 사용한 아이디어는 다음과 같습니다. 0. n+1사이즈의 array안에 ArrayList를 넣고, ArrayList안에는 int[]가 있는 구조를 준비한다. 1. 값을 입력받을 때 [..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 5639번 가장 가까운 공통 조상를 풀었습니다. 이를 정리해보고자 합니다. 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 본문 1) 문제 2) 과정 이번 문제는 너무 빨리 풀어서 골드가 맞을까 생각했었어요. 생각부터 제출까지 40분도 안걸려서 실버겠거니 했는데 골드라 알고리즘 공부하면서 가끔씩 찾아오는 뿌듯함에 기분이 좋았습니다! 이번 문제에서 그나..

목차 개요 본문 1) 문제 2) 과정 3) 코드 전체 개요 이번에 알고리즘 스터디에서 JAVA를 이용해 백준 9489번 사촌을 풀었습니다. 이를 정리해보고자 합니다. 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 본문 1) 문제 2) 과정 NoSuchElement... 진짜... 검색을 하고 다른 분들을 참고해도 왜 자꾸 틀렸다고 하는거지???? 하면서 의문만 수만개 갖고 고민했어요. 그리고 깨달았습니다. n이나 k가 1일때 0을 출력하게 한다는 건 그 뒤에 값을 읽지 않으니 Stri..