Completion over Perfection

DAT / HashMap / ArrayList / ArrayDeque / TreeMap / PriorityQueue 는 각각 언제 최대 성능을 발휘할까? 언제 써야 될까? (결론) 상황에 따라 적절한 자료구조를 선택해야 하는데, DAT를 쓸 수 있는 조건이면 무조건 DAT를 쓰는것이 좋다. 가장 빠르다. (추가) JAVA에서는 String이 길어지면 속도가 많이 느려진다고 함. String을 key로 쓰는 경우 주의해아하며, 가급적 unique한 숫자로 바꾸는 것이 유리함. 구분Big O 시간복잡도자료구조주로 사용되는 문제 유형주요 특징 및 사용 이유삽입삭제탐색DAT (Direct Address Table)알파벳 빈도수 계산, 숫자 출현 여부 등 범위가 작은 경우의 빈도 체크인덱스를 직접 접근하는 방..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 루트노드가 1이 아닌점을 주의해서 풀이해주시면 됩니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int T, N; static int []..

https://school.programmers.co.kr/learn/courses/30/lessons/120866 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 지뢰가 있는 지역을 중심으로 8방향을 모두 위험지역으로 체크해주고, 안전한 지역을 세서 답으로 출력해주면 됩니다. 다만 주의할 점은 예를 들어 첫번째 예시에서 4X3 지역에 지뢰가 설치되어 있는데요, 이 주변 구역을 돌면서 지뢰가 있는 8방향을 숫자 1로 바꿔버린다면 다음 for문을 돌때 1로 갱신된 지역이 마치 원래 지뢰가 있었던 지역처럼 인식되어 버린다는 점을 주의해야 합니다. 그래서 저는 ..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS로 풀었는데 중간에 답이 중간에 몇개는 맞고 몇개는 런타임 에러가 뜨는 겁니다. ㅠ.ㅠ 알아보니 가로/세로 갯수가 100일 경우, 재귀가 최대 10000개 생성될 수도 있는데 파이썬의 기본 재귀 깊이가 1000이라서 런타임 에러가 뜬다고 하네요. 아래 코드를 넣어주고 나서는 정상적으로 다 맞게 나왔습니다. import sys limit_number = 10000 sys.setrecursio..

https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n과 s가 주어지는데 n개의 원소를 가진 집합의 각 원소의 합은 s가 되어야합니다. n이 3이고 s가 8일 경우, 원소는 3개이고 이 3개의 원소를 모두 합친 값이 8이 되어야 합니다. {1,1,6} {1,2,5} {1,3,4} {2,3,3} . . . 중요한 특징은 원소의 순서는 상관이 없다는 것. 따라서 위의 예시에서 {1,2,5} 와 {1,5,2}는 한개의 집합으로 취급한다는 겁니다. 이 조..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 숨바꼭질1 처럼 방문처리를 한 뒤에 해당 좌표를 방문안하게 되면 안됩니다. 왜냐하면 2배로 점프뛰는 좌표는 이동시간이 0이 들기 때문에 최소 시간을 구하려면 반드시 갱신을 해주어야 합니다. 2. 다음에 이동할 좌표의 시간값이 이미 arr 배열에 들어있는 time값보다 작을 때만 큐에 넣어줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS로 풀었습니다. 한번 큐에 담았던 숫자는 다시 큐에 담지 않도록 방문처리는 반드시 해주셔야 됩니다. 아래 반례들을 참고해서 풀어보세요. 입력 : 100000 0 출력 : 100000 입력 : 0 100000 출력 : 22 입력 : 0 0 출력 : 0 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..

https://www.acmicpc.net/problem/2738 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 2차원 배열을 2개 선언해주고(arr1, arr2), 각각 받아준 뒤 새로운 2차원 배열(ans)에 더해서 넣어주면 됩니다. 자세한 풀이는 아래 코드를 참고해주세요. 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..