백준

[python] 백준 - 2615. 오목

🤔문제 해결 6목은 안된다. 답을 출력할 때, 왼쪽 우선, 위쪽 우선 이므로 바둑돌을 기준으로 우상, 우, 우하, 하 이렇게 4방향만 고려해줬다. 먼저 바둑돌 하나를 선택하고 이 바둑돌이 끝에서 시작하는지 or 끝이 아니라면 내가 체크할 방향의 반대방향으로 상대 바둑돌이 없는지 육목 방지 위의 조건에 맞다면 내가 정한 방향으로 탐색하며 같은 색의 바둑돌을 계속 찾음 상대 바둑돌을 만나거나 바둑판 밖으로 나가면 내가 찾은 바둑돌의 개수를 체크 바둑돌을 4개 더 찾았으면 성공 아니면 실패 💻소스 코드 import sys input = sys.stdin.readline LENGTH = 19 board = [list(map(int, input().split(" "))) for _ in range(19)] # 우..

[python] 백준 - 1052. 물병

🤔문제 해결 S1 | 이진법 물의 양이 1, 2, 4, 8, 16, ... 이렇게 증가하므로 이진수처럼 생겼다. 같은 수를 더하면 다음 수 하나가 나온다. 이진수로 보면 ex) 100 + 100 = 1000 예시로 설명해보자면 N = 11 일 때 물병: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 물병합: 2, 2, 2, 2, 2, 1 물병합: 4, 4, 2, 1 물병합: 8, 2, 1 물병은 결국 3개가 된다. 11을 이진수로 바꾸면 1011 이다. 결국 1의 개수가 다 합쳤을 때의 물병의 개수가 된다. 그럼 1의 개수를 줄이고 싶으면 이진수 덧셈을 이용한다. 1011(11) + 0001(1) => 1100(12) 1100(12) + 0100(4) => 10000(16) 🚀 이진수를 잘 이..

[python] 백준 - 17140. 이차원 배열과 연산

🤔문제 해결 G4 | 시뮬레이션, 구현 문제를 이해하는데 시간이 좀 걸렸다. k값이 맞는지 확인하고 아니라면 시간을 +1 증가시킨다. R연산인지 C연산인지 확인한다. R 연산일 경우 각 행의 숫자와 해당 숫자의 개수를 리스트나 튜플 형태로 저장한다. [(1, 1), (2, 1)] 이런식으로 sort를 이용해 정렬한다. 튜플을 풀어서 숫자 하나하나의 형태로 리스트에 저장하고 나머지 길이를 0으로 채워넣는다. C 연산일 경우 행과 열을 바꿔서 위의 과정을 똑같이 진행한 후 다시 행과 열을 바꿔준다. 💻소스 코드 def is_k(): if r - 1 < len(arr) and c - 1 < len(arr[0]): if arr[r - 1][c - 1] == k: return True return False de..

[python] 백준 - 10819. 차이를 최대로

🤔문제 해결 S2 | 완전탐색, 백트래킹 백트래킹을 하려고 했으나, 순열로 푸는게 더 간단해보여서 조합을 이용했다. 숫자들을 배치할 수 있는 모든 경우의 수를 뽑아서 규칙에 맞게 계산을 해주고 최대값을 찾는다. 💻소스 코드 from itertools import permutations def my_sum(numbers_tuple): # 문제의 규칙에 맞게 더하기 total = 0 for i in range(N - 1): total += abs(numbers_tuple[i] - numbers_tuple[i + 1]) return total if __name__ == '__main__': N = int(input()) numbers = list(map(int, input().split())) answer =..

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라 정말 기본적인 다익스트라 문제! 따로 키 리스트를 설정하지 않아도 쉽게 풀 수 있다. 💻소스 코드 import sys import heapq input = sys.stdin.readline def dijkstra(s, e): pq = [] heapq.heappush(pq, (0, s)) # 출발지로 가는데 0원의 비용 visited = [0] * (N + 1) while pq: cost, w = heapq.heappop(pq) if w == e: return cost if visited[w]: continue visited[w] = 1 for newt_w, next_cost in adj[w]: if not visited[newt_w]: heapq.heappush(pq, (..

[python] 백준 - 2493. 탑

🤔문제 해결 G4 | 자료구조, 스택 문제를 푼 뒤 문제 유형을 봤는데 스택이라고 되어있었다. 하지만 내 풀이는 스택을 사용하지 않았다. 그런데 다른 사람보다 효율이 좋게 나왔다. 메모리는 평균인듯. 풀이 방법 1번탑부터 마지막탑 순으로 탐색했다. 현재탑과 이전탑과 같을 때 현재탑의 레이저 신호를 수신하는 탑은 이전탑의 레이저 신호를 수신하는 탑과 같다. 현재탑이 이전탑보다 낮을 때 현재탑의 레이저 신호를 수신하는 탑은 이전탑이다. 현재탑이 이전탑보다 높을 때 🐱‍🐉 이전탑의 레이저 신호를 수신한 탑으로 건너 뛴다. 그 탑을 위의 3가지 방법으로 체크한다. 아직 현재탑이 높은 상태라면 또 그 탑의 레이저 신호를 수신한 탑으로 건너 뛴다. 이렇게 3가지로 분리했다. 💻소스 코드 if __name__ == ..