개발자 퉁이리

https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 char 값으로 받은 데이터를 0과 1로 변환하여 int arr에 넣고 bfs 함수를 만들어줬다. 그리고 한 바퀴가 다 끝나서 queue를 탈출시 count up을 해주고 마지막에 저장된 count 값을 출력한 후, 배열과 방문 기록을 초기화..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 플로이드-와샬 ⊙ 문제 접근 과정 플로이드 와샬을 통해 다시 돌아온 arr[i][i] 값 중 가장 작은 값을 출력해주면 된다. 만약 갱신이 안 되었을 시 -1을 출력해주면 된다. 자세한 설명은 코드에 주석으로 적어놨다! ⊙ 문제 풀이 #include using namespace std; #d..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 구현 ⊙ 문제 접근 과정 N = int(input()) input_ = "" for i in range(1,N+1): input_ += str(i) print(len(input_)) 처음에는 위와 같이 코드를 짰다. 하지만 시간 초과. dp처럼 공식을 세워서 문제를 풀어야지 주어진 시간제한 안에 문제를 풀 수 있었다. 가만 생각해보니 패턴이 존재했다. 1부터 9까지의 값의 합이 아닌 자릿수의 합은 9이다. 마찬가지로 10부터 99까지 자릿수의 합은 90..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 스택 ⊙ 문제 접근 과정 stack pair를 이용하여 index와 value를 동시에 push 해주었다. 가장 위에 있는 값의 value는 st.top().second이고 그것에 대한 index는 st.top().first이다. 현재 입력 값이랑 기존에 stack에 저장되어 있는 값이랑 비교 후, 신호 수신 가능( 기존에 ..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 정수론 소수 판정 에라토스테네스의 체 ⊙ 문제 접근 과정 범위를 입력받는다. 범위 안에서 소수를 에라토스테네스의 체 알고리즘을 통해 찾는다. 찾았다면 값 출력 ※주의 시간 초과를 해결하기 위해 에라토스테네스의 체 범위를 제곱근까지 했다. 그래도 무방하기 때문. ⊙ 문제 풀이 import sys M, N = map(int, sys.stdin.readline().sp..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 브루트포스 알고리즘 ⊙ 문제 접근 과정 list에 2개의 쌍으로 저장 후, 조건문을 통해 결괏값을 도출해내자. ⊙ 문제 풀이 N = int(input()) #전체 사람 수 people = [] #사람 정보를 받을 list for _ in range(N): #입력한 순서대로 정보를 입력받는다. x, y = map(int,..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 문자열 정렬 정수론 ⊙ 문제 접근 과정 이런 문제는 수학만 잘하면 엄청 쉬운 문제라고 생각한다. 30의 배수 조건은 그냥 각 자리 수를 다 더했을 때, 3으로 나누어 떨어지고 일의 자리수가 0이면 된다. 아래는 위 공식에 대한 코드다. ⊙ 문제 풀이 N = list(input()) N.sort(reverse=True) sum = 0 ..

https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 비트마스킹 백트래킹 플로이드-와샬 외판원 순회 문제 ⊙ 문제 접근 과정 플로이드 와샬을 이용하여 모든 행성 방문 시 최단거리를 구하는 문제이다. 플로이드 와샬에선 문제없이 풀었지만, dfs 구현하는 부분에서 어려움을 느껴 어흥님의 블로그에서 해당 문제의 dfs 부분을 참고했다. 자세한 건 코드 주석에 적어놨다! ⊙ 문제..

https://www.acmicpc.net/problem/5622 5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 ⊙ 문제 접근 과정 각 타입(알파벳)에 대한 그룹(숫자)을 만들어서 숫자를 출력할까라고 생각했다. 그리고 생각을 바로 접었다. 코드가 엄청 길어질 것 같다고 생각했다. 근데 지금 다시 생각해보니 int group[] = {3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10}; 이런식으로 짜면 짧게 구현할 수 있다. 각설하고, 나는 아스키코드로 문제를 풀었다. 그리고 식..

https://www.acmicpc.net/problem/2490 2490번: 윷놀이 우리나라 고유의 윷놀이는 네 개의 윷짝을 던져서 배(0)와 등(1)이 나오는 숫자를 세어 도, 개, 걸, 윷, 모를 결정한다. 네 개 윷짝을 던져서 나온 각 윷짝의 배 혹은 등 정보가 주어질 때 도(배 한 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 ⊙ 문제 접근 과정 윷 한번 던질 때마다 초기화다. 즉, 독립이란 소리! 입력받은 숫자들을 다 더해 각자의 케이스(도, 개, 걸, 윷, 모) 별로 정리한다면 쉽게 풀 수 있다. 정말 오랜만에 switch문을 사용해 풀어봤다. if문을 사용해도 상관없다. ⊙ 문제 풀이 #include using namespace std; in..