스택/큐) 프로그래머스 : 올바른 괄호, 기능개발

1. 올바른 괄호 문제 접근 : '('의 개수에 맞게 끔 ')'을 이어주면 되는 문제다. 따라서 ( 의 개수를 파악하고 이 개수만큼 ) 가 오면 되는 것이다. (는 괄호의 시작이므로 배치에 제약이 없다. 핵심은 여는 괄호가 몇 개이든 간에 어쨌든 닫히기만 하면 되는 것이다. 즉, 스택을 활용하여 (를 저장하고 )를 만날 때마다 하나씩 제거해주면 된다. 이는 +,- 관계로 생각하여 리스트로도 풀이가 가능하다. 스택에 들어가는 타입은 문자이므로 Character 타입으로 선언한다. 주어진 배열 s의 처음부터 끝까지 문자를 탐색하기 위해서 charAt( ) 메서드를 사용한다. 스택의 추가는 push, 제거는 pop으로, ( 를 만날 때마다 push를 한다. ) 를 만났을 때는 두 가지 상황이 주어진다. 스택이..

• format_list_bulleted 알고리즘
• · 2022. 12. 18.
• textsms

해쉬) 프로그래머스 : 전화번호 목록, 위장

1. 전화번호 목록 문제 접근 : 각각의 번호를 저장하여, 한 번호가 다른 번호의 접두어인지를 판단하면 된다. 중복이 없기 때문에 hashSet을 이용해도 될 것 같다. 어쨌든 값들을 다 저장한 후에 하나씩 꺼내서 비교하면 된다. hashMap의 containsKey 메서드를 통해 저장된 전화번호부에 해당 키가 존재하는지 확인할 수 있다. String 클래스의 substring을 통해 각 전화번호의 맨 앞부터 끝에서 두 번째까지의 번호를 확인한다. (끝까지 가면 자기 자신을 확인하기 때문에 예외가 발생할 수 있다.) import java.util.*; class Solution { public boolean solution(String[] phone_book) { /* 해쉬 셋 contains 확인 ->..

• format_list_bulleted 알고리즘
• · 2022. 11. 27.
• textsms

해쉬) 프로그래머스 : 완주하지 못한 선수 / 폰켓몬

1. 완주하지 못한 선수 문제 접근 : 참가 명단과 완주 명단을 비교하는 것이므로, 선수 이름을 대조하기 위하여 명단을 저장하는 자료구조로 해쉬를 사용한다. 이 때, Key는 이름, Value는 인원 수이다. 이름이 중복될 수 있기 때문에 Value 가 필요하다. 참가 명단과 완주 명단을 저장한 각각의 해쉬 맵을 비교하며 차이나는 한 명을 반환한다. for문을 통해 해쉬 맵의 요소를 탐색하면서 값이 1인 이름을 반환한다. 이 때, 해쉬를 순회하기 위해서는 인덱스를 통한 접근이 불가능하므로, hashMap의 keySet()(Key가 저장된 Set을 반환)이나 entrySet()(Key-Value 구조인 엔트리가 저장된 Set을 반환)을 사용한다. import java.util.*; class Solutio..

• format_list_bulleted 알고리즘
• · 2022. 11. 26.
• textsms

백준 2667번 : 단지 번호

1. BFS로 풀었을 때 # 문제 : https://www.acmicpc.net/problem/2667 # 백준 2667번 : 단지번호 from collections import deque num = int(input()) # 스페이스바 없이 출력 : https://lifeignite.tistory.com/51 graph = [list(map(int, input())) for _ in range(num)] # map 객체의 index에 접근하려먼 list형으로 캐스팅해줘야 한다! # 좌표 값 설정 dx = [0,0,1,-1] dy = [-1,1,0,0] # 단지 수 house_num = 0 # 단지 수 배열 house_array = [] # BFS : 1이 있을 때 그와 인접한 노드들을 방문 (1이 없을..

• format_list_bulleted 알고리즘
• · 2022. 6. 15.
• textsms

백준 2606번 : 바이러스

# 문제 : https://www.acmicpc.net/problem/2606 from collections import deque # 백준 2606번 : 바이러스 n = int(input()) m = int(input()) #adjacent 배열로 구현 # computers=[[0]*(n+1) for _ in range(n+1)] # for _ in range(m): # a,b = map(int, input().split()) # input한 값들을 int 함수로 바꿔주는 map 함수로 구현 # computers[a][b] = 1 # computers[b][a] = 1 # 풀이 : https://velog.io/@wjdtmdgml/%EB%B0%B1%EC%A4%80%EB%B0%94%EC%9D%B4%EB%..

• format_list_bulleted 알고리즘
• · 2022. 6. 7.
• textsms

알고리즘의 복잡도 (Complexity of Algorithms)

방법(method)이란 어떤 목적을 달성하기 위해 해야 할 작업을 명확하게 지시한 것입니다. 그리고 방법 중에서도 작업의 횟수가 항상 유한한 것을 특별히 알고리즘(algorithm)이라고 부릅니다. 55p 알고리즘의 복잡도는 크게 시간 복잡도(time complexity)와 공간 복잡도(space complexity)로 나뉜다. 알고리즘의 복잡도란 이 알고리즘이 얼마나 복잡한가를 나타내는 것이 아니라 데이터의 개수(문제의 크기), N에 따라 얼마나 많은 시간(공간 : 메모리 용량)을 소요하는가를 나타내는 척도이다. Big-O 표기법은 최악의 경우 (worst-case)에 대하여 표기하며, 최악의 경우라도 이정도의 성능은 보장한다는 뜻이다. (따라서 O(N)인 알고리즘이라고 하더라도 소요시간이 O(N)보다..

• format_list_bulleted 알고리즘
• · 2022. 4. 20.
• textsms