griffin의 코딩상자

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방향에대해 반복문 수행 범위 안에 있고 그 위치에 있는 알파벳이 현재 존재하지 않을 경우에 로직 수행 알파벳재귀 함수를 이용하여 ..

Ubuntu 20.04에 A3000u드라이버 설치하기 본 USB형 랜카드 같은 경우는 산지 2년정도 된것 같다. 처음에는 노트북의 무선 랜카드가 시원치 않은것 같아서 구매했다. 하지만 ipTIME에서는 윈도우 드라이버만 제공하기 때문에 리눅스에서 사용을 하지 못했었다. 더군다나 굳이 귀찮은 일을 사서 하고 싶지 않기 때문에 그냥 하지 않고 내장 랜카드를 이용했었다. 그러다가 최근에 문제가 발생하였다. 작년 여름정도부터 데스크탑에 유선랜을 연결해서 쓰는데, 이번에 사정상 이사를 가게 되는 것이다. 하지만 유선 랜이 방에 없기 때문에 데스크탑의 경우 무선랜카드를 사서 장착해서 사용해야하는 문제가 생겼다. 뭔가 새로운걸 사기에는 돈이 너무 없다... 고로, 기존에 있던 것을 사용해보자는 생각을 했다. 하지만 ..

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이기 때문 핵심 팁..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 해결방안 BFS를 이용한 방식 사용 알고리즘 토마토 박스 초기화 전체를 돌며 익은 토마토를 큐에 넣어줌 bfs 큐에서 토마토를 꺼내와 상, 하, 좌, 우 토마토에 익은 날짜 + 1을 삽입해줌 전체를 돌며 가장 날짜가 큰 것을 찾음 0이 들어있다는 것은 토마토가 익을 수 없다는 것이므로 -1을 출력하고 종료 핵심 팁 기본적인 BFS문제 핵심 포인트는 익은 토마토에 단순히 방문 처리하는 것이 아니라..

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 해결방안 DFS를 이용한 방식 사용 재귀를 이용한 백트래킹 방식 사용 처음에는 BFS를 이용하려 했었으나, 이전에 풀었던 방식을 사용해서 풀 수 있다는 생각이 들어 DFS 사용 알고리즘 경로를 위한 딕셔너리, 방문 여부 파악을 위한 딕셔너리 생성 및 초기화 방문한 경우 1로 변경 초기화 한 것을 알파벳순으로 정렬해줌 dfs함수 생성 만약 값이 경로의 딕셔너리에 없다면 return으로 ..

[프로그래머스 level3] 배달 https://programmers.co.kr/learn/courses/30/lessons/12978 해결방안 다른 사람들의 해결방안을 보니 보통 bfs로 이용한 것 같음 다익스트라 역시 2차원 배열로 인접리스트를 이용한 것이라고 생각하면 됨 시작점에서 시작하여 모든 값을 확인하면 되니 다익스트라를 이용하면 될 것이라고 생각함 다익스트라 알고리즘에 대해서 모른다면 먼저 보고 오는것을 추천 알고리즘 순서 기본적으로 인접 리스트를 생성 각 노드까지의 거리를 저장하기 위해 노드의 갯수만큼 배열을 생성 하고 큰 수로 초기화 양방향이기 때문에 양쪽 인접리스트에 모두 거리와 노드를 삽입 시작점에서 출발하는 다익스트라 함수 실행 기본적으로 출발점의 거리는 0으로 셋팅 노드를 최소힙에..