문제 코드 풀이 도미노 아래와 윗면이 같은 숫자는 (0+1+2+...+n)*2 도미노 아래와 윗면이 다른 숫자는 위에 있는 사진과 같은 규칙을 가짐 따라서 숫자의 규칙성에 따라 반복문을 작성해줌
Koala - 9기
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 알고리즘 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다. 신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 작성하..
0. 잡설 오랫동안 고민하던 문제를 풀게되어 글을 작성합니다. 유니온 파인드로 정답을 풀 수 있었습니다. 삽질한 기록까지 적어놓아 생각을 정리하려고 합니다. 1. 삽질 유니온 파인드 알고리즘을 연습하는 중이라 처음에 삽질이 있었습니다. 처음 생각해낸 아이디어는 다음과 같았습니다. 진실을 아는 사람은 parents배열 인덱스를 0으로 지정하고, 파티에서 진실을 아는 사람과 모르는 사람이 있는 경우, 진실을 알게된 사람의 parents배열 인덱스를 0으로 지정하자! 하지만 이렇게 하면, 순서에 따라 답이 다를 수 있었습니다. 예를 들어 다음과 같은 예제가 있겠습니다. 5 4 1 5 2 1 2 2 2 3 2 3 4 2 4 5 잘못된 생각으로 적용된 알고리즘입니다. 순서에 따른 parents 배열 변화를 적어보..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 알고리즘 요구 조건이 적록색약이 보는 사람과 아닌 사람이 보는 구역의 수다. 여기서 말하는 구역의 수란 같은 색으로 이루어진 부분이다. 따라서 상하좌우로 인접한 글자들이 같은 색이어야 같은 구역이고, 다른 색이면 다른 구역이다. bfs로 방문을 하지 않은 곳을 방문해주면서, 그래프의 상하좌우를 탐색했을 때 이미 방문한 곳이라면 방문 표시를 해준다. 방문 표시가 된 곳부터 다시 탐색을 하면서..
1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제코드
문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net Algorithm 2차원 배열 array를 입력받을 때 array의 각 위치를 지나쳤는지에 대한 배열 V를 함께 생성한다. V의 모든 원소는 False로 초기화한다. 같은 방법으로 v를 생성하는데 v는 색약이 아닌 사람, V는 색약인 사람에 대한 배열이다. 모든 과정은 색약인 사람은 "R"과 "G"인 부분을 "A"로 치환하여 진행한다. array의 행과 열 (i, j)에 대해 arra..
https://www.acmicpc.net/problem/10865 10865번: 친구 친구 첫째 줄에 도현이네 반 학생의 수 N(1 ≤ N ≤ 100,000), M(0 ≤ M ≤ 1,000,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 나타내는 A B가 한 줄에 하나씩 주어진다. A B가 입력으로 주어진 경우 www.acmicpc.net 문제 소스코드 문제풀이 학생 수+1만큼 0으로 구성된 리스트를 만들어 입력되는 학생 번호에 해당하는 index 에 1을 추가하여 리스트를 만들어서 해결했다. 학생 수n크기의 리스트를 만들어서 했을 때는 시간초과가 나왔고, +1을 해주었더니 해결되었다.
3184번: 양 (acmicpc.net) 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 문제 미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다. 마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서..
문제 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 요약 중요도가 높은 순서대로 문서를 인쇄하면서, 특정 문서가 몇 번째로 인쇄됐는 지 출력하는 문제이다. 코드 #include #include #include #include using namespace std; int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; int N, M, save, index = 0, order = 1; bool bigge..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 1 문제 코드 문제 풀이 DFS 로 풀이 1) 적록색약이 아닐 때, R,G,B 각각의 함수를 설정. 2) 적록색약일 때, R,G 값을 함수 S로 묶어서 풀이, B는 그대로 풀이함. 풀이 2 문제 코드 문제 풀이 BFS 로 풀이, 코드가 너무 길고 지저분하다는 생각이 들어서 최대한 간단하게 풀이 해 보고자 함. 코드의 길이를 줄이기 위해 하나의 함수로만 문제를 해결하려고 하였음. 1) ..
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 코드 문제 풀이 재귀함수를 활용, 중복은 불가하지만 같은 수가 2개 이상 들어있다면 [n,n] 과 같은 출력을 해야 하기 때문에 a 에서 중복제거를 할 수 없음. 따라서 1개인 숫자의 중복을 허용하지 않기 위해 t 를 두어 a[i] 가 현재 A = [] 안에 포함되어 있는지를 확인하는 작업을 추가함. 리스트 내부의 중복을 처리한 후 출력.
https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 문제 풀이 막대기를 리스트에 입력받고, 앞에서 뒤로 리스트를 탐색하면서 점점 더 높은 막대만 카운트하면 된다. 반복문으로 풀 수도 있을 것 같은데, 재귀 함수에 익숙해지고자 간단하지만 재귀 로직으로 구현해봤다. 구현 로직 첫 번째 시도 import sys input = sys.stdin.readline def go(arr, idx, cmp): global ans if idx >= len(arr): pr..
