본문 바로가기

전체 글156

[백준] 14426번 접두사 찾기 _ JAVA [초기 접근 방법] 검사 문자열 inspect에 대해 집합 S 문자의 접두사가 맞는지 체크 → 시간복잡도가 O(MN * len(inspect[i])) = O(1억 * a) 으로 시간초과가 된다. [생각] 문제 유형을 보니 "Trie"라는 처음 보는 자료구조여서 블로그를 참조해 먼저 공부했다. Trie : 문자열을 저장하고 효율적으로 탐색하기 위한 '트리' 형태의 자료구조 → 자동완성, 사전 검색 등 문자열 탐색 기능 - insert() // 생성 시간 복잡도 : O(N*L) void insert(String word) { TrieNode node = this.rootNode; // 문자열의 각 단어의 자식노드를 찾아 return 하거나, 자식노드 새로 생성 // Map에서 현재 문자를 key로 Value.. 2024. 2. 21.
[백준] 1043번 거짓말 _ Python [초기 접근 방법] - 맨 처음에 제시한 사람은 무조건 "진실"만을 들어야 한다. - 각 사람마다 일관되게 "과장된 이야기 or 진실"을 들어야 한다. - 해당 파티에서는 무조건 "과장된 이야기 or 진실"을 이야기해야 한다. 1. 제시한 사람이 있는 파티는 일단 전부 진실을 말한다. 2. 위 파티에 있는 사람들 모두 "진실파티" 에 넣는다. 3. 각 파티를 탐색하면서 파티 참석 인원 중 "진실파티"에 있는 사람이 있다면 참가한 사람들을 "진실파티"에 추가를 하고, 파티를 처음부터 다시 탐색해야 한다. "진실파티"에 있는 사람이 없다면 해당 루프에서 종료한다. [생각] 1. input.split() 내에서의 슬라이싱 set(map(int, input().split()[1:])) 2. set.union().. 2024. 2. 20.
[백준] 1676번 팩토리얼 0의 개수 _ Python [초기 접근 방법] 1. N! 을 구하자 2. 0의 개수를 세자 [생각] 위와 같이 심플한 방법으로 접근하면 문제에서 N의 범위가 500까지이기 때문에 'OverflowError'가 발생한다. 따라서 OverFlow를 방지하기 위해 N!을 하는 과정에서 수의 크기를 관리해주어야 한다. 이 때, N!의 1의 자리만 보존해도 되기 때문에 다음과 같이 코드를 작성한다. # 10으로 나눠질 경우 if fact % 10 == 0: while True: # 1의 자리만 남기도록 한다. if fact % 10 != 0: fact %= 10 break fact /= 10 zeroCount += 1 [코드] # 풀이 시간 : 10 + 25분 # 시간복잡도 : O(N) # 공간복잡도 : O(1) # 참고 : - # 왜 .. 2024. 2. 18.
[백준] 18110번 solved.ac _ Python [초기 접근 방법] 1) 상위 15%, 하위 15% 절사 - 이 때, 소수점은 반올림 계산 2) 계산된 평균 반올림 계산 [생각] 1) 수식을 작성할 때, "0 / x" 와 같은 ZeroDivision 주의 2) 파이썬의 반올림은 ".5"와 같이 올림, 내림했을 때 동일하게 차이가 나는 경우에는 짝수 값으로 반올림 합니다. → 따라서 파이썬으로 풀 경우, epsilon. 즉 굉장히 작은 값을 더해 우리가 일반적으로 생각하는 반올림이 될 수 있게끔 해야 한다. [코드] # 풀이 시간 : 20분 # 시간복잡도 : O(NlogN) # 공간복잡도 : O(N) # 참고 : python round() 관련 자료 # https://blockdmask.tistory.com/418 import sys input = sy.. 2024. 2. 17.
5주차. 네트워크 레이어 1. IP주소에 대해서 설명해주세요. 더보기 IP 주소는 네트워크에서 호스트와 라우터의 각 인터페이스마다 할당되어 있는 식별 번호 입니다. "IP 주소는 컴퓨터 네트워크에서 통신 장치를 식별하기 위해 사용되는 고유한 숫자입니다." 2. IPV4와 IPV6는 어떤 차이점이 있을까요? 더보기 IPv4에서는 주소를 4바이트로 표현하고, IPv6에서는 주소를 16바이트로 표현합니다. IPv4에서 제공되는 주소 개수의 한계 때문에 IPv6가 등장했습니다. IPv6는 보편화 단계에 있으며 IPv4와 혼용해서 사용하기 위해 터널링 기법을 사용합니다. "IPv4와 IPv6의 가장 큰 차이점은 주소 길이와 형식입니다. IPv4는 32비트 주소를 사용하고, IPv6는 128비트 주소를 사용합니다. 이로 인해 IPv6는 더.. 2024. 2. 13.
[백준] 14725번 개미굴 _ Python [초기 접근 방법] 1) 개미굴 입구를 중심으로, 자식 노드들을 top [] 에 저장한다. 2) 자식노드들의 각 행에 중복되지 않는 노드들을 result[] 에 저장하도록 한다. [생각] 각 행에 중복되지 않는 노드들을 result[]에 저장하도록 구현했는데, 부모 노드가 다를 때에는 각각 저장해주어야 한다. 아래와 같은 test case 를 적어보았다. Input Output Answer 2 3 APPLE APPLE ORANGE 3 APPLE BANANA ORANGE APPLE --APPLE ----ORANGE --BANANA APPLE --APPLE ----ORANGE --BANANA ----ORANGE 올바른 접근 풀이는 다음과 같다. 1. 동굴 깊이 간선 정보를 정렬을 한다. → 사전 순서가 앞.. 2024. 2. 9.

티스토리툴바