https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs로 풀어야 겠다고 떠올렸다 그런데 보통 입력이 숫자로 주어졌고, 나는 그래프를 표현할 때 주로 이차원 리스트를 사용했는데 각각의 node에 해당하는 공항 이름들이 문자열이다보니, 처리를 쉽게 하기 위해서는 dictionary 자료형이 낫다고 생각했다. 내가 좋아하는.. 쓰기 편한 defaultdict으로 초기화 없이 우선 정의해주고, for 문에서 각각 그래프와, visited 딕셔너리에 F..
Algorithm (PS)
https://www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 애드혹 유형이라고 한다 1. ZZZ 같이 같은 문자로 연속되는 문자의 경우 어떻게 문자열을 슬라이싱하더라도 펠린드롬 문자열이므로, -1을 return 한다. 1 의 경우에 해당되지 않는다면, 해당 문자열이 펠린드롬인지 아닌지를 판단해서 쉽게 답을 얻을 수 있다. 2. 펠린드롬 문자열인 경우 : (전체 문자열 길이-1)를 return 한다. 3. 펠린드롬 문자열이..
https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net .... 광광 하 엄청난 삽질 후에 풀었다 반례를 빠르게 찾아내서 예외케이스를 처리해주는게 중요한 문자열 패턴 문제이다.. 1. f를 기준으로 문자열을 잘라서 검사한다 ex) wolfwolf -> [wolf, wolf] 2. 자른 문자열의 w, o, l, f 알파벳 개수를 세서 각각 알파벳 개수가 동일한지 확인한다. 3. 동일하다면 정규표현식을 사용해서 w+o+l+f (w,o,l,f가 각각 한번 이상 등장하고 순서대로 등장하는지 확인)를 확인해준다. 4. 그런데 이렇게 했..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투포인터 문제에 꽂혀있다 !! 핵심은 left 포인터와 right 포인터가 가리키는 용액의 특성값이 0보다 작으면 left 포인터를 오른쪽으로 한칸 움직이고, 0보다 크면 right 포인터를 왼쪽으로 한칸 움직여서 0에 가깝게 만드는 것이다 투포인터 문제는 포인터를 움직일때의 기준을 찾는 것이 핵심인 것 같다 # 2470 두 용액 n = int(input()) d..
https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 처음에는 단순하게 대각선 4방향 + 상하좌우 4방향 총 8방향을 모두 체크해야겠다고 생각했으나, 1.오목의 특성상 그럴 필요없이 총 4가지 방향만 체크해주면 된다 ⇩, ⇘, ⇗ ➔ 하, 우하, 우상, 우 네가지 방향을 확인해주면 된다. dx = [1, 1, -1, 0] # 하, 우하, 우상, 우 dy = [0, 1, 1, 1] 2.항상 좌측, 위 부터 시작하도록 하여 연속된 5개 오목 중 가장 왼..
https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 다익스트라 알고리즘을 이용하여 최단거리를 구해주면 되는 문제이다. # https://www.acmicpc.net/problem/5972 import heapq n, m = map(int, input().split()) graph = [[]*(n+1) for _ in range(n+1)] INF = int(1e9) distance = [INF]*(n+1) for i in range(m): a, b, cost..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 2차원배열에서의 회전할때 규칙과, 후진할 때 칸의 이동을 찾으면 풀 수 있는 시뮬레이션 문제이다 n, m = map(int, input().split()) r, c, d = map(int, input().split()) array = [] visited = [[False]*m for _ in range(n)] # 청소한 여부 기록 visited[r][c] = True # 방문처리 count = ..
https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net import sys import heapq input = sys.stdin.readline n = int(input()) times = [] temp = [] for _ in range(n): start, end = map(int, input().split()) times.append([start, end]) times.sort() # 시작 시간을 기준으로 오름차순 정렬 temp.appen..
