griffin의 코딩상자

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해결방안 DFS를 이용하여 해결 알고리즘 결과 값을 위한 전역 변수를 초기값 -1로 초기화 (연관관계가 없을 경우를 대비) 주어진 노드 값들을 딕셔너리로 생성 관계들을 딕셔너리에 리스트 값으로 양방향으로 추가해줌 방문여부를 확인하기 위한 리스트 초기화 DFS 작성 현재의 노드 값이 원하는 노드 값과 같을 경우 촌수계산을 전역 변수에 저장하고 종료 현재 노드와 관계있는 딕셔너리의..

https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 해결방안 Graph 알고리즘 전제 조건 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다. 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다. 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다. 칸이 이동하는 방향과 방문여부를 알아야 함 모든 경우를 방문해보면 됨 1. 이미 방문했다면 종료 2. 방문한 적이 없다면 방문하고..

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 해결방안 BFS 알고리즘 알고리즘 1에서 출발하여 각 거리에 있는 노드들을 고려하기 위한 딕셔너리 생성 (result_list) vertex를 그래프로 만들기 위한 딕셔너리 생성 (graph) edge를 돌면서 graph에 양방향 그래프 초기화 중복 방문을 방지하기 위해 방문여부를 처리하는 배열 생성 (visited) BFS 수행 1번노드를 큐에 넣고 방문처리, 시작점이므로 cnt는 0으로 초기화 큐에서 노드를 뽑아서, 방문안한 노드일 경우에만 ..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 해결방안 DP를 이용하여 해결 알고리즘 n이 0 혹은 1일 경우는 미리 출력하고 종료시켜버림 dp는 [0, 0] 리스트로 구성된 n + 1 크기의 리스트 생성 (2차원) dp를 리스트로 지정하는 이유는 0과 1의 갯수를 별도로 카운팅 하기 위함 dp[0]과 dp[1] 값을 지정 dp[0]에는 0의 값은 1, 1의 값은 0을 나타내도록 [1, 0] 리스트를 할당 dp[1]에는 0의 값은 0, 1의 값은 1을 나타내도록 [0, 1] 리스트를 할당 피보나치와 동일하게 인덱스는 2부터 n번째까지 dp 수행 점화식에..

programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 해결방안 그리디 알고리즘 알고리즘 전체 인원 만큼 1로 초기화 해줌 모두 체육복을 가지고 있다는 가정 체육복을 잃어버린 사람의 index는 -1 해줌 잃어버린 사람의 경우 체육복의 갯수가 0으로 변화 됨 체육복을 여벌로 가지고 있는 사람의 index는 + 1 해줌 여벌로 가지고 있는 사람의 경우 체육복의 갯수가 2로 변화 됨 2번과 3번을 통해 여벌을 가지고 있으면서 도둑맞은 ..

www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해결방안 백트래킹 문제 조합에 대한 이해가 있으면 좀 더 쉽게 풀 수 있음 정렬과 예외 처리 참고 문제 풀이 N과 M (2) 알고리즘 l, c를 받아옴 문자열을 리스트로 만들어서 정렬 시킴 문제의 조건에 암호는 증가순이라고 쓰여있기 때문에 알파벳 순으로 정렬 l 크기 만큼 배열 생성 배열을 만드는 이유는 굳이 새로운 리스트에 append, pop하는것을 할 필요가 없기 때문 배열은 어차피 다 채워질 것 이기 때문에 ..

www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 해결방안 대표적인 백트래킹 문제 기본적인 조합에 대한 이해가 있으면 좀 더 쉽게 풀 수 있음 알고리즘 n, m을 받아옴 m 크기 만큼의 배열을 초기화 해서 생성 즉, 전체 필요한 길이 만큼의 배열을 0으로 일단 초기화 index와 cnt를 인자로 가지는 함수 정의 index는 시작지점을 뜻함. 조합의 경우 이전에 갔었던 곳을 다시 재방문 하면 안되기 때문에 시작지점을 뜻하는 index부터 다시 반복문 시작 c..

www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 해결방안 점과 점 사이의 거리를 이용한 방식 사용 점과 점 사이 거리 공식을 알아야 풀 수 있음 알고리즘 두 점 사이의 거리를 구하는 공식과 반지름의 길이 비교하는 함수 정의 출발점(x,y), 도착점(x,y) 입력 받음 x, y, 반지름 값을 튜플로 받아 리스트에 저장 리스트에서 값을 하나씩 돌면서 출발점과, 도착점, 값을 함수에 넣어서 비교 출발점과 도착점이 모두 원 안에 있는 경우, 카운트 하..

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 해결방안 백트래킹(Backtracking)을 이용한 방식 사용 알고리즘 변수 초기화 상하좌우로 움직일 수 있도록 초기화 알파벳을 딕셔너리를 이용해서 초기화 현재 알파벳 길이를 나타내는 변수 0으로 초기화 처음 알파벳은 포함되어야 하므로 함수 수행전에 1 추가시켜 줌 상하좌우 4방향에대해 반복문 수행 범위 안에 있고 그 위치에 있는 알파벳이 현재 존재하지 않을 경우에 로직 수행 알파벳재귀 함수를 이용하여 ..

www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해결방안 그리디(Greedy)를 이용한 방식 사용 알고리즘 들어오는 단어들을 숫자로 나눔 abc => 100a + 10b + c 각 문자들을 10의 배수에 대한 딕셔너리로 처리해서 넣어줌 abc라면, a에는 100, b에는 10, c에는 1 딕셔너리 아이템의 value들을 가지고 내림차순으로 정렬 시킨 리스트 생성 리스트를 돌면서 9부터 줄여가며 곱해줌 9부터 줄여가는 이유는 최대값이 9이기 때문 핵심 팁..