구빙그르르르

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 한줄 이해 -D S L R의 각 명령어를 수행해 A 숫자가 B가 되기 위해 필요한 최소한의 명령어 구하기 생각난 풀이 1번째 방법: 각각의 명령어를 수행해 큐에 담아서 탐색하는 BFS가 떠올랐고 이미 방문한 숫자에 대해 다시 탐색하지 않게 visited처리를 해주었다. 이때 123에 R명령어를 수행하면 312가 되는것이 아니고 3012가 되는 점을 유의하기! import sys ..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 한줄 이해 -R, G, B로 이루어진 그래프가 있을때 적록색약을 가지고 있는 사람은 R과 G를 차이를 거의 느끼지 못해 그래프를 볼때 같은 구역이라 생각한다. 이때 적록색약이 있는 사람과 없는 사람이 그래프를 볼때 나뉘어지는 구역 수 출력 생각난 풀이 1번째 방법: 그래프를 BFS를 통해 구역을 나누면서 탐색하는 방법이 떠올랐다. 적록색약이 없는 경우 단순히 탐색을 진행 적록색약이 있..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 한줄 이해 -상자에 익은 토마토와 익지 않은 토마토가 담겨있고 아무것도 담기지 않은 공간이 있을때 익은 토마트는 하루가 지나면 익지 않은 토마토를 익게 만들때 토마토를 모두 익은 상태로 만들기 위한 날짜 구하기 생각난 풀이 1번째 방법: 먼저 그래프에 익은 토마토를 먼저 큐에 담아주고 BFS를 통해 값 구하기 2차원 그래프로 선언, BFS탐색, 위층 아래층은 현재 위..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 한줄 이해 -리모콘의 숫자가 망가져 있을 수도 있고 아닐 수도 있는 상황에서 N채널로 가기위한 최소 버튼 입력 수 구하기 생각난 풀이 1번째 방법: 백트래킹을 통해 N채널 자릿수와 자릿수 +1, 자릿수 -1 의 경우의 수를 담아 값을 갱신했다. 자리수 -1 과 자릿수 +1 을 해주는 이유는 간단한 예를 들면 999 채널로 가려고 할때 망가진 숫자가 9가 망가졌다고 치자. 그..

https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 한줄 이해 -요즘 유행하는 MBTI로 사람간의 심리적 거리를 계산한다. ENFJ와 ISFP가 있을때 심리적 거리는 3! 이때 주어진 사람들 중 3명의 값이 제일 작은 경우 구하기 생각난 풀이 1번째 방법: 리스트에 사람들을 담아 백트래킹을 통해 심리적 거리를 갱신 해주자! 이때 mbti의 갯수는 총 16개 그렇다면 사람이 33명이 들어오면 무조건 심리적 거리는 0임을 생각하자 why? 최악의 경우를 생각하면 32 명안에 2,2,2,2,2,2.... 이렇게 mbti가 같은 사람이 구성 될..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 한줄 이해 -목표 지점에서 다른 지점까지의 거리 계산하기 생각난 풀이 1번째 방법: 먼저 그래프에서 목표 지점을 찾고 해당 지점에 대해서 BFS 탐색을 한 뒤 예외처리를 해주었다. import sys from collections import deque n, m = map(int,sys.stdin.readline().split()) graph = ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 한줄 이해 -가중치가 없는 방향 그래프가 있을 때 각 노드 입장에서 다른 노드를 거쳐서라도 갈 수 있는지 판단하기 생각난 풀이 1번째 방법: 각 노드들이 중간 다리 역할을 해주면서 탐색을 하는 방법이 생각났다. 예제를 그림으로 그리면 위와 같다. 이때 0번 노드 입장에서 1번 노드가 중간다리를 해주면 2번 노드로 갈 수 있다. 따라서 graph[i][k] + graph[k][j]가 2라면 graph[i][j]는 1로 ..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 한줄 이해 -배열에 정수를 넣은 다음 꺼낼때 절대값이 작은 수가 먼저 출력되고 절대값이 같은 경우에는 그 중 작은 값을 꺼내는 절대값 힙 구현하기 생각난 풀이 1번째 방법: 기본적으로 우선순위 큐를 사용 하려했고 기본적으로 파이썬에서 제공하는 heapq는 최소힙으로 제일 작은 값부터 출력이 된다. 이때 나는 힙에 넣어줄때 +라면(x의 절대값, 2), -라면(x의 절대값..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 한줄 이해 -카잉 제국에서는 해를 계산할때 이번 해 다음 해 이와 같이 1씩 증가시킨다. (단, 이번 해에서 1씩 증가시킬때 왼쪽의 값이 M보다 작으면 +1을 그렇지 않으면 1로 리셋해준다.오른쪽도 동일한 규칙을 가지고 N이 기준) 생각난 풀이 1번째 방법: while 반복문을 통해 단순히 1씩 증가시키고 조건에 걸리면 1로 리셋해주는 방법으로 했다. import sys t = int(sys..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 한줄 이해 -N이 주어질때 I가 N+1개 O가 N개가 교대로 나오는 P문자열이 있다.(P1 = IOI) 이때 S문자열에 P가 몇개 있는지 파악하기 생각난 풀이 1번째 방법: 배열 슬라이싱을 통해 갯수를 세보려했다. import sys n = int(sys.stdin.readline()) p = [] for i in rang..