728x90

목sssssss록파이썬 (109)

개발조아

[BOJ/백준] 12904 A와 B 파이썬

문제 링크 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 시작 문자열에서 조건에 맞게 A,B 문자 추가해서 목표 문자열까지 갈수 있냐 없냐 판별하는 문제이다. 처음에는 BFS로 접근했더니 메모리 초과가 났었다. 문자열이 엄청 많아지니까 초과가 날수밖에 없는 것 같다. 문제의 조건은 다음과 같다. 1. 문자열의 뒤에 A를 추가한다. 2. 문자열을 뒤집고 뒤에 B를 추가한다. 그래서 그리디하게 접근했다. ..
알고리즘/백준 2021. 8. 18. 23:59
[BOJ/백준] 13459 구슬 탈출 파이썬

문제 링크 : https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net BFS로 풀면 된다는 것은 간단하게 캐치 할 수 있다. 하지만 단순히 2차원 배열가지고 해결하기에는 힘들다. 할 수 있는지도 잘 모르겠다. 핵심은 각 구슬의 위치를 동시에 가지고 가야한다는 것이다. 그렇기 때문에 방문 체크도 동시에 해야한다. 따라서 방문배열를 4차원으로 같은 시점의 빨간공, 파란공의 좌표를 동시에 체크해줘야한다. 이부분..
알고리즘/백준 2021. 8. 18. 23:05
[BOJ/백준] 백준 1022 소용돌이 예쁘게 출력하기 파이썬

문제 링크 : https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 위의 사진 처럼 나선형으로 숫자가 있는 배열에서 조건에 맞는 범위의 숫자를 같은길이로 예쁘게 출력하는 문제이다. 역시나 처음에는 그냥 1억개 숫자 다 만들고 했어서 역시나 메모리 초과가 났다. 출력해야하는 범위 칸의 개수는 최대 50x5이고 해당 범위에 들어오는 인덱스만 배열에 저장하면 된다. 배열의 좌표는 음수가 없으니 5000을 더해서 맞춰주고 실제 배열에 들어갈때는 이를 0,0을 기준으로 이동시켜서 넣었다. 나선형의 시작 인덱스는 당연히 5000,5000에서 시작했다. 예를 들어 -3 -3 0 2..
알고리즘/백준 2021. 8. 15. 18:14
[프로그래머스] 순위 검색 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72412 = target: right = mid else: left = mid+1 return len(scores)-right def trans_info(info): for i in info: new_info = i.split() new_info[4] = int(new_info[4]) count_info(new_info,['-','-','-','-'],0) for key in info_dict: info_dict[key].sort() def count_info(info,new_info,start): global info_dict new_condition = ''.join(new_info) if ne..
알고리즘/프로그래머스 2021. 8. 13. 22:25
[프로그래머스] 메뉴 리뉴얼 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 주어진 메뉴를 주어진 주어진 길이만큼 조합해서 새로운 메뉴를 만들고, 같은 길이의 새로운 메뉴 중 가장 많이 나온 메뉴를 리스트에 담아 정렬해서 리턴하면 된다. 주의 할점은 ["XYZ", "XWY", "WXA"] 3번 테스트케이스에서 2자리로 메뉴를 만든다고 했을 때 "XW"와 "WX"는 같은 메뉴로 친다. 이것 때문에 계속 답을 못찾고 있었다. 새..
알고리즘/프로그래머스 2021. 8. 13. 17:42
[프로그래머스] 정수 삼각형 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 간단한 DP 문제이다. 맨 꼭대기에서 양 옆 대각선으로 더해 내려갈때 최대값을 구하는 문제이다. 점화식이랄것도 없다. 현재 점에서 양 옆 위 대각선의 값 중 큰 값을 현재 값에다 더해서 내려가면 된다. 주의할 점이라면 위에서 아래로 내려가면서 위의 대각선을 확인하므로 1부터 시작하고 양끝 점은 대각이 하나만 있으므로 처리해주면 된다. def solution(triangle): for x in ..
알고리즘/프로그래머스 2021. 8. 13. 17:09
[프로그래머스] 순위 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 고민고민하다가 접근법을 모르겠어서 검색해본 문제이다. 접근방법은 플로이드와샬로 하면 됐었다. a가 b를 이겼다면 b는 항상 a 아래이고, b가 c를 이겼다면 c도 항상 b 아래이다 결국 c는 항상 a아래 이므로 a->b, b->c이면 a->c 인 것이므로 플로이드와샬로 접근이 가능하다. a와 b 관계에서 a가 c를 이기고 c가 b를 이기는 관계가 있으면 a가 b를 이긴것으로 체크하고 (b,a), (c,a), (b,c)는 모두 진것으로 체크하면 된다. 마지..
알고리즘/프로그래머스 2021. 8. 13. 16:29
[프로그래머스] 네트워크 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 간단한 BFS 문제이다. 한지점에서 출발하여 도달할 수 있는 모든 지점은 같은 네트워크이다. 이때 네트워크의 개수를 구하는 것이다. 방문한 점을 방문 표시해주고 그 점에서 BFS를 시작한다. 이때 BFS를 몇번 돌렸는지 구하면 된다. from collections import deque def solution(n, computers): ans..
알고리즘/프로그래머스 2021. 8. 13. 15:36
Prev 1 ··· 9 10 11 12 13 14 Next
728x90