개발자 퉁이리

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌렸다. 2번. 한 번은 입력받은 RGB 그대로 돌려서 구역을 찾아냈다. 마지막 한번은 R을 전부 G로 바꾸고 visited 여부를 초기화해준 후 돌려줬다. ⊙ 문제 풀이 import sys from collections import deque ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 백트래킹 ⊙ 문제 접근 과정 bfs를 사용해 문제를 풀었다. 조건을 통해 알파벳이 탐색하지 않았고 범위 안에 있다면 탐색을 추가한다. 계속해서 반복하여 answer의 최댓값을 갱신해준다. 처음에 dfs로 문제를 풀어봤는데 pypy로 해도 시간 초과가 나서 bfs로 풀었다. ⊙ 문제 풀이 i..

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/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 ⊙ 문제 접근 과정 너비 우선 탐색(bfs)을 이용해 풀었다. 거기에 for문을 한번 더 감쌌다. L과 R의 범위로 인해 연합국이 생기지 않을 때까지 이 for문을 반복한다. 한 바퀴 돌 때마다 days가 1 증가 연합국이 생기지 않는다면 days(결과)를 출력한다...

https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 같은 거리의 집을 다 탐색하고도 탐색할 집이 남아있다면 거리를 1 늘리고 다시 탐색한다. set을 이용하여 방문을 했는지 안 했는지 판별했다. ⊙ 문제 풀이 #include #include #include using namespace std; ty..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 BFS 문제라 BFS로 풀었는데 식으로도 충분히 풀 수 있다. 현재 층에 대해 위층과 아래층 값을 더하거나 뺀 값이 최고층보다 작거나 같거나, 0보다 크고 방문한 적 없는 층이라면 진행한다. 그리고 그 층을 다시 현재층에 대입하여 반복한다. 그러다가 목적층인 G와 현재층 S 값이 같다면 종..

⊙ 문제 다음과 같은 지뢰 찾기 게임 프로그램을 작성하시오. 실행 결과는 '5 10 0.3'을 명령행 인수로 사용한 예이다. 프로그램은 3개의 명령행 인수(m, n, p)를 받아들이고, m * n 크기의 배열을 생성해 지뢰를 숨긴다. 숨긴 지뢰가 있는 원소는 *로 표시하고 없는 원소는 -로 표시한다. 원소에 지뢰가 있을 확률은 세 번째 명령행 인수인 p이다. 지뢰 숨김 여부를 나타내는 2차원 배열을 출력하고, 지뢰를 숨기지 않은 원소를 -대신에 이웃한 지뢰 개수로 채운 2차원 배열도 함께 출력한다. 이웃한 지뢰는 상하좌우 및 대각선 원소에 숨긴 지뢰를 의미한다. 지뢰 숨긴 지역을 30%로 설정하려면, 난수 발생 정적 함수 Math.random() 값이 0.3보다 적은 원소에 지뢰를 숨긴다. ⊙ 문제 접근..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 트리 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 단순 트리의 부모만 구하면 되는 문제다. DFS, BFS 두 가지 풀이 방법이 있는데 DFS로 풀어봤다. vector에 값을 대칭으로 입력한다. 그리고 자식노드에 하나씩 방문하여 부모를 지정해주는 로직으로 풀었다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS 문제이다. 시작 값을 bfs() 함수에 넣고 방문할 때마다 값을 하나씩 올려준다. 그리고 마지막에 목표값에 대해 출력하면 된다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 102..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 나이트의 이동 문제다. 체스에서 나이트를 움직이는 방법은 두 칸 전진 후, 전진한 방향에서 오른쪽 혹은 왼쪽 중 한 방향으로 한 칸을 이동할 수 있다. 움직이는 거리를 dx, dy에 저장하여 나이트의 이동과 동일하게 해 주었다. 그리고 목표지점까지 arr 값을 계속해서 갱신해주었..