이분탐색

💡 solutions 💬 이분탐색 이용하여 문제 해결 💬 start, end, mid 변수값들은 공유기 사이 거리로 정한다. 💬 start는 공유기 사이의 최소 거리로, end는 공유기 사이의 최대 거리로 잡고 이분 탐색을 시작한다. 💬 집의 좌표를 담은 house 리스트를 정렬한 후 맨 첫 번째 집부터 공유기를 설치하는데 이때 공유기 사이의 거리를 mid만큼 잡는다. 💬 공유기를 설치한 횟수를 나타내는 count가 주어진 공유기 개수 C 이상이면 공유기 사이의 거리를 넓히고 (이때 공유기 사이 최대 거리를 나타내는 answer값을 mid로 갱신), C 미만이면 거리를 좁힌다. 👨‍💻 code import sys def binary_search(start, end): answer = 0 while sta..

→2022.01.01

Algorithm/Baekjoon

[백준] 파티 / 1238번 / Python / 파이썬 / 다익스트라(Dijkstra) 알고리즘

💡solutions 💬 heap 최소힙 자료구조를 활용하여 다익스트라 알고리즘으로 해결하였다. 💬 먼저 N명의 학생들마다 X번 마을에 왕복으로 다녀오는데 걸리는 최소 시간을 구한다. -> 이때 편도가 아니기 때문에 최소 시간은 dijkstra(i, x) + dijkstra(x, i)으로 ① i번 학생이 본인의 마을에서 X번 마을로 가는 최소 시간과 ② X번 마을에서 출발하여 본인 마을로 돌아오는 데 걸리는 최소 시간을 더하면 된다. 💬 마지막으로 각 학생들이 X번 마을에 다녀오는데 걸린 최소 시간을 비교하여 가장 많은 시간을 소비한 학생의 소요시간을 출력하면 된다. 👨‍💻code import heapq import sys def dijkstra(start, end): distance = [INF] * (..

→2021.11.17

Algorithm/Baekjoon

[백준] 도시 분할 계획 / 파이썬 / Python / 크루스칼 알고리즘 / Kruskal

💡solutions 💬 크루스칼 알고리즘을 사용해서 문제를 해결했다. 💬 하나의 마을을 분리하여 두개의 마을로 분활하면 -> 각 마을 안에 있는 집들은 서로 연결돼 있어야 하며 이때 길의 유지비의 합은 최소가 돼야 한다 💬 크루스칼 알고리즘을 활용하여 N-1개의 집들을 연결하고 마지막 유지비가 최대인 경로는 끊으면 (즉, 연결하지 않으면) 이게 바로 유지비가 최소가 되도록 마을을 두개로 분활하는 방법이다. -> 각 집을 연결할 때마다 edge_cnt를 세서 간선의 개수가 n-2가 되면 break한다. (*참고로 MST에서 모든 간선을 연결할 때 최소 간선의 개수는 n-1이다.) 💬 처음에 파이썬으로 코드를 제출했을 때 시간초과가 났고, sys 모듈을 불러와서 input = sys.stdin.readlin..

→2021.11.14

Algorithm/Baekjoon

[백준] 보석 도둑 / 1202번 / 파이썬 / Python / heapq/ 힙큐

💡solutions 💬 heapq모듈을 사용하여 최소힙, 최대힙 자료구조를 사용하였음. 💬 보석들은 무게가 작은 순서대로 뽑힐 수 있도록 최소힙으로 구현 💬 가방은 제한된 무게를 기준으로 가벼운 것부터 무거운 순으로 나오도록 오름차순 정렬 💬 for 반복문을 통해 작은 무게 제한을 가진 가방부터 꺼내와서 제한된 무게보다 가벼운 보석들을 임시 리스트인 tmp에 모두 담아둔다 -> 이때 주의할 점은 추후 tmp에서 가장 비싼 애들부터 순서대로 뽑을 수 있게 가격에 마이너스 부호를 붙여 tmp 리스트에 heappush로 넣어준다. (이게 바로 최대힙 구현하는 방법) 💬 가방에 담을 수 있는 보석 중 가장 제일 비싼 가격의 보석을 뽑아서 answer에서 빼준다 -> 애초에 보석 가격을 음수로 넣어놨기 때문에 a..

→2021.11.12

Algorithm/Baekjoon

[프로그래머스] 약수의 합 / 자바 / Java

💡solutions ) 💬 for 반복문을 통해 n을 i로 나누었을 때 0이되는 약수들을 모두 찾아서 더해주면 되는 문제이다. 💬 참고 : 약수를 찾는 것이기 때문에 for문에서 주어진 n에 대해서 n / 2까지만 약수인지 확인해주면 돼서 계산을 반으로 줄일 수 있다. => for (int i=1; i

→2021.11.08

Algorithm/Baekjoon

[프로그래머스] 가운데 글자 가져오기 / 자바 / Java / substring()

💡solutions ) 💬 자바 언어 공부를 시작한지 얼마 안돼서, 문법 공부를 할겸 프로그래머스 기본 문제들을 다시 풀어보고 있다. 💬 파이썬에서는 문자열을 s[:2] 이런식으로 간편하게 슬라이싱할 수 있는데, 자바에서는 해당 인덱스의 문자열을 반환하는 substring() 메소드를 사용한다. substring() 메소드는 인자의 개수에 따른 차이 ✔ substring(int Index) 해당 인덱스부터 끝까지 문자열 반환 ✔ substring(int IndexA, int IndexB) 인덱스 A부터 B 직전까지의 문자열 반환 👨‍💻code ) class Solution { public String solution(String s) { String answer = ""; int a = s.length(..

→2021.11.08

Algorithm/Baekjoon

[백준] 문자열집합 / 14425번 / 파이썬 / Python / 딕셔너리

💡solutions ) 💬 쉬운 문제라고 생각하고 빠르게 풀어서 제출했더니 시간초과.... pypy로 제출해도 시간초과.. 💬 다른 방법이 있을까 하고 찾아보다가 첫 풀이와 비슷하게 딕셔너리를 사용하지만 이중 for문을 사용하지 않아 훨씬 효율적으로 풀 수 있었다. 💬 M개의 문자열 각각이 N개의 문자열로 이루어진 S집합에 존재하는지 확인하기만 하면 되기 때문에 -> 딕셔너리 자료형에 N개의 문자열을 각각 key값으로 저장한 후에 -> M개의 문자열을 반복문을 통해 key값이 존재하는지 확인하면 된다. 👨‍💻code ) 🐥첫 번째 풀이 -> 시간 초과💥 import sys input = sys.stdin.readline n, m = map(int, input().split()) s_dict = {} fo..

→2021.11.06

Algorithm/Baekjoon

[백준] 케빈 베이컨의 6단계 법칙 / 파이썬 / python / BFS 알고리즘

💡solutions ) 💬 처음 adj라는 인접행렬을 만들어 각 유저 간의 연결 상태를 나타내고 -> 덱 자료구조를 사용해서 BFS 알고리즘으로 구현하면 문제를 쉽게 해결할 수 있다. 💬 첫 시도에서 스택 자료구조를 사용해서 DFS 알고리즘 구조로 풀었더니 채점결과 실패했다. 이유는 해당 문제에선 출발지에서 각 노드까지의 최단 거리를 찾는 개념이기 때문에 DFS로 찾게 되면 최단 거리가 아닐 수 있기 때문이다. BFS와 DFS로 거리 구할 때의 차이 해당 문제에서 테스트케이스가 아래처럼 주어지는 경우 DFS로 거리를 찾는다면 ->1에서 2까지의 거리가 1, 3까지의 거리가 2가 나온다. 이와 비교하여 BFS에서는 1에서 2까지 그리고 1에서 3까지 모두 거리가 1이 나오므로 최단거리가 된다. 3 3 1 ..

→2021.11.05

Algorithm/Baekjoon

[백준] 괄호의 값 / 2504번 / 파이썬 / Python / Stack 자료구조

💡solutions ) 💬 이번 문제는 구현 문제로 자료 구조 스택(stack)을 활용해서 해결하였다. 💬 첫 번째 if 조건문은 입력값이 ')' 또는 ']'로 시작하는 경우가 -> 올바르지 못한 괄호열로 판별하기 위한 것이다. 처음에 이 조건문을 달지 않아서 채점 중간에 실패했다. 💬 sys모듈의 exit()는 프로그램 종료함수이다. -> 따라서 올바르지 못한 괄호열일 때는 print(0)을 해주고 exit(0)로 해당 프로그램을 바로 종료한다. ✔ sys모듈의 exit() 종료함수에 대한 설명 👇 참고 블로그 💬 올바른 괄호열인지 판별하는 것은 어렵지 않았으나, 괄호열의 값을 구하는 로직을 구현할 때 어려움을 느꼈다. 닫는 괄호가 나오면 그 이전에 stack 맨 끝(top)에 숫자가 있는지 확인하고 ..

→2021.11.04

Algorithm/Baekjoon

[백준] 빗물 / 14719번 / 파이썬 / Python / 구현 / 시뮬레이션

💡solutions ) 💬 기본적인 시뮬레이션 문제 💬 for반목문을 돌며 가장 높은 블록의 높이(max_height)와 인덱스(max_index)를 저장해두고, 블록들의 전체 높이의 합을 저장한다(block_sum) 💬 왼쪽 끝에서부터 max_index까지(좌에서 우→) 그리고 오른쪽 끝부터 max_index까지 (우에서 좌←) 탐색하여 블록의 높이를 비교하여 가장 높은 블록의 위치값(tmp)을 total에 더해준다. 💬 마지막에 total값에서 전체 블록들의 높이의 합인 block_sum을 빼주면 고이는 빗물의 총량을 구할 수 있다. 👨‍💻code ) import sys input = sys.stdin.readline h, w = map(int, input().split()) block = list(..

→2021.11.03

Algorithm/Baekjoon

[백준] 맥주 마시면서 걸어가기 / 9205번 / 파이썬 / python / BFS 알고리즘

💡solutions 💬 BFS 알고리즘으로 문제 해결하였다. 💬 주어진 좌표들을 사용하는데 -> 상근이네집(home_x, home_y)에서부터 탐색을 시작한다. 💬 편의점 좌표를 돌아가며 방문 가능 유무를 확인한다 -> 두 가지를 확인하는데 ①이미 방문했는지 ② 20개의 맥주로 이동할 수 있는 거리인지를 확인한다. 💬 q에서 popleft하여 다음으로 이동할 좌표가 락 페스티벌 좌표(rock_x, rock_y)이면 행복하게 페스티벌에 갈 수 있으므로 'happy'를 출력하면 된다. 👨‍💻code import sys from collections import deque def bfs(x, y): q = deque([[x, y]]) visit = [[x, y]] while q: x, y = q.popleft..

→2021.11.02

Algorithm/Baekjoon

[백준] 게으른 백곰 / 10025번 / 파이썬 / Python / Sliding Window / 슬라이딩 윈도우

💡solutions ) 💬 슬라이딩 윈도우 알고리즘(Sliding Window)을 활용하여 문제를 해결하였다. 💬 먼저 얼음 양동이들을 나타내는 ice 배열을 최대 크기만큼 만들어준다. -> ice = [0]*1000001 💬 입력을 주어진 양동이 좌표에 해당하는 얼음의 양을 넣어준다. 💬 윈도우의 고정된 범위를 next = 2*k +1(한 좌표에서 앞뒤로 k만큼씩 떨어지는 있는 범위를 모두 포함하므로)로 두고, for 반복문을 돌려 한칸씩 이동하며 맨 뒤에 있는 값 ice[i]은 윈도우값에서 (+)더해주고 맨 앞에 있는 값 ice[i-next]은 (-)빼준다. 💬 window값 업데이트할 때마다 answer도 최대값으로 업데이트해주기 📚 슬라이딩 윈도우 알고리즘(Sliding Window)이란? 윈도우..

→2021.11.01

티스토리툴바