'🧩 Problem Solving' 카테고리의 글 목록 (4 Page)

[백준] 28250 이브, 프시케 그리고 푸른 MEX의 아내 (python 파이썬)

2023.07.03

https://www.acmicpc.net/problem/28250 28250번: 이브, 프시케 그리고 푸른 MEX의 아내 첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 200\,000$) 둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($0 \le A_i \le 100\,000$) www.acmicpc.net 문제 이름이 특이해서 풀어본 문제. 실2라고 얕잡아봤다가 끔찍한 결과가 나왔다. 실제 코테였다면 풀었을지 장담 못하겠다. 꼭 입력값 제한을 보면서 시간을 추측하는 습관을 들이자. 여담이지만 코테 환경을 상상하며 문제를 푸는 건 도움이 되는 거 같다. 아이디어 1. 이중 for문 실패 수식을 보고 무식하게 이중 for으로 구현했다가 ..

🧩 Problem Solving/[백준]

[백준] 28017 게임을 클리어하자 (python 파이썬)

2023.07.01

https://www.acmicpc.net/problem/28017 28017번: 게임을 클리어하자 첫째 줄에 산지니가 게임을 몇 회차를 하는지 나타내는 수 $N$과 무기의 종류 $M$이 공백으로 구분되어 주어진다. $(2 \le N, M \le 500)$ 둘째 줄부터 $N$개의 줄에는 각 무기마다 게임을 클리어하는데 www.acmicpc.net 대회 초반에 삽집하다가 DP인걸 깨닫고 해결했다. pypy로 제출, 이후 python으로 다시 제출. 아이디어 1. 반복문 단순 반복문으로 작성했다 실패했다. 2. DP n회차의 각 무기마다 올 수 있는 시간을 저장하면 된다. 위 이미지처럼 이전 행에 있는 값 중 최솟값을 다음 행에 더해가며 업데이트하면 된다. 최종적으로 마지막 행의 최솟값을 출력하면 된다. 전..

🧩 Problem Solving/[백준]

[백준] 9205 맥주 마시면서 걸어가기 (python 파이썬)

2023.04.09

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 맨해튼 거리인 줄 모르고 삽질했다. 문제를 잘 읽어보자. 아이디어 1. 그래프 탐색 심플하게 맥주 20병 = 1000m라고 생각하고 1000m를 기준으로 갈 수 있는지 없는지 확인하면 된다. bfs를 사용하여 해결했다. 전체 코드 from collections import deque def cal_distance(x, y, nx, ny): return abs(nx - x) + abs(ny -..

🧩 Problem Solving/[백준]

[백준] 1759 암호만들기 (python 파이썬)

2023.03.30

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음에는 itertools 라이브러리를 사용하여 순열을 구하고, 각 순열마다 검사하는 방법으로 했는데 시간초과 되었다. 생각해 보면 최대 경우가 15P15까지 나오므로 이 방법은 당연히 아니었다. 암호를 판별하는 방식이 아닌 처음부터 암호를 조건에 맞게 만드는 방법으로 문제를 풀어 해결하였다. 아이디어 1. 암호 조건 암호에 있는 알파벳을 증가하는 순서(aescend)로 배열되었다. 암호에는 모음 1개..

🧩 Problem Solving/[백준]

[백준] 11559 puyopuyo (파이썬 python)

2023.03.26

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net bfs를 잘 사용하면 되는 문제. 아이디어 전체 코드 from collections import deque dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] field_info = [] for _ in range(12): field_info.append(list(input())) def bfs(a, b, c): global boom_flag boom_li..

🧩 Problem Solving/[백준]

[백준] 2583 영역 구하기(python 파이썬)

2023.03.16

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 그래프 탐색하는 문제. 비슷한 유형의 문제를 풀어봤으면 쉬운 문제. 아이디어 1. 모눈종이 M*N 크기의 2차원 리스트로 모눈종이를 나타냈다. 주어진 직사각형 좌표에 따라 직사각형을 표현해준다. 1은 직사각형, 0은 빈공간을 나타낸다. 문제에서는 좌표가 왼쪽 아래가 원점(0, 0)이지만, 리스트는 왼쪽 위가 원점이다. 어차피 가로축에 대해 대칭이므로 문제에서 요구한 값을 구하는..

🧩 Problem Solving/[알고리즘 for PS]

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

2022.12.22

그리디 알고리즘(Greedy Algorithm) 탐욕법으로도 알려진 문제 해결 방법이다. 이름 그대로 주어진 문제를 단순하게 탐욕적으로 푸는 알고리즘이다. 탐욕적이라는 말은 '현재 상황에서 가장 좋은 것만 계속 고르는 방법'을 말한다. 그리디 방법음 알고리즘의 각 단계에서 그 순간에 최적이라고 생각하는 것을 선택한다. 또한 그리디로 문제를 해결할때는 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용할 수 있다. 우리는 그리드 문제를 풀 때는 다익스트라(dijkstra) 또는 위상 정렬(topological sort) 알고리즘처럼 특정 알고리즘 코드를 미리 알 필요는 없다. 대신 우리는 문제를 봤을 때 '그 문제가 그리드 알고리즘으로 해결할 수 있는지'에 대해 알아야 한다. 그럼 어떻게 알 수 있..

🧩 Problem Solving/[프로그래머스]

[프로그래머스] 118666 성격 유형 검사하기 (python 파이썬)

2022.12.12

https://school.programmers.co.kr/learn/courses/30/lessons/118666 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 1. 딕셔너리 성격유형은 key, 점수는 value로 사용해서 딕셔너리를 만들어서 해결했다. choices에 있는 결과에 맞춰 성격 유형 점수를 더해준다. 전체 코드 def solution(survey, choices): answer = '' N = len(survey) personality = {'R':0, 'T':0, 'C':0, 'F':0, 'J':0, 'M':0, 'A':0, '..

티스토리툴바