취업을 준비하며 정리하는 컴퓨터 지식 (55) 썸네일형 리스트형 [Algorithm] 알고리즘 정리 정렬 선택 정렬(selection sort) 배열에서 가장 큰 값을 선택하여 정렬되지 않은 배열의 맨 뒤로 이동시켜 정렬하는 방법입니다. 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 버블 정렬(bubble sort) 배열에서 인접한 두 값을 비교하여 조건에 맞게(오름차순, 내림차순에 따라 다름) 값의 위치를 이동시켜 정렬하는 방법입니다. 선택 정렬과 마찬가지로 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 향상된 버블 정렬(enhanced bubble sort) 버블 정렬과 같은 방법으로 동작하지만 이중 반복문을 순환하는 동안 값이 한 번도 바뀌지 않으면 정렬되었다고 가정하는 정렬 방법입니다. 버블 정렬과 마찬가지로 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 삽.. [Problem Solving] 백준 7569번 토마토 문제풀이 백준 7569번 토마토 문제풀이에 대해서 알아보겠습니다. 문제 해설은 다음의 링크를 참고해주시기 바랍니다. 문제 해설 토마토 문제는 그래프 탐색 문제입니다. 따라서 bfs를 사용하여 구현해야 합니다. 해결 방법은 다음과 같습니다. 처음 박스에 존재하는 토마토의 위치를 저장한다. 지정한 범위에 벗어나지 않은 안 익은 토마토를 찾아서 도달한 시간을 저장한다. 박스의 정보를 순차적 탐색하여 0이 존재하는지 확인한다. (5. 0이 존재한다, 6. 0이 존재하지 않는다.) -1을 출력한다. 도달한 시간의 최대값에서 1을 뺀 값을 출력한다. 위의 과정에서 도달한 시간이란 처음 토마토에서 시작하여 해당 위치까지 몇 번의 탐색 끝에 왔는지를 나타냅니다. 다음은 해결 방법에 따라 구현한 코드입니다. # 백준 No.756.. [Problem Solving] 백준 3020번 개똥벌레 파이썬 백준 3020번 개똥벌레 문제에 대한 해설과 코드입니다. 문제는 다음의 링크를 참고해주시기 바랍니다. 문제 해설 문제에서는 짝수 번째에서는 석순이 홀수 번째에서는 종유석이 등장합니다. 그렇기 때문에 석순과 종유석을 따로 계산하여 겹치는 장애물의 개수를 세워주어야 합니다. 문제 해결을 위한 과정은 다음과 같습니다. 입력받은 n을 index로 사용하여 순서에 따라 석순과 종유석에 1을 넣어준다. 석순은 0을 기준으로 오른쪽에 있는 값들을 모두 더해서 저장한다. 종유석은 h를 기준으로 왼쪽에 있는 값들을 모두 더해서 저장한다. 2, 3에 계산된 값을 answer에 더해서 저장한다. answer에서 가장 작은 값과 가장 작은 값의 수를 출력한다. 2번과 3번의 계산 결과는 각 자릿수를 지나갔을 때 파괴되는 장애.. [Problem Solving] 백준 2468번 안전 영역 파이썬 백준 2468번 안전 영역 문제에 대한 해설과 코드입니다. 문제는 다음의 링크를 참고해주시면 됩니다. 문제 해설 문제의 설명에도 있지만 해당 문제는 비가 내리는 양이 정해져 있지 않아서 모든 영역이 잠기기 전까지의 경우를 모두 탐색해야 합니다. 따라서 해결 과정은 다음과 같습니다. 가장 높은 지역의 높이를 구한다. 비의 양에 따라 낮은 지역을 물에 잠기게 한다. 물에 잠기지 않은 영역의 개수를 계산하여 저장한다. 비의 양을 늘려 2를 반복한다. 물에 잠기는 부분과 잠기지 않는 부분을 구분하기 위해서 물에 잠기는 부분은 -1로 값을 변환시켰습니다. 낮은 지역부터 물에 잠기게 하기 때문에 한번 잠긴 지역은 결과가 나올 때까지 물에 잠겨있습니다는 것을 가정하고 진행합니다. 다음은 코드입니다. # 백준 No.2.. [Problem Solving] 백준 1715번 카드 정렬하기 문제 풀이 백준 1715번 카드 정렬하기 문제 풀이에 대해서 알아보겠습니다. 문제 해설은 다음의 링크를 확인해주시기 바랍니다. https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 해당 문제는 그리디 유형의 문제로 문제를 해결하기 위한 최적의 방법을 생각해보아야 합니다. 최소 비교 횟수를 구하기 위해서는 가장 작은 묶음을 뽑아서 비교해줘야 합니다. 문제 해결을 위해서는 다음의 과정을 거칩니다. 첫 번째로 작은 묶음을 선택한다. 두 번째로 작은 묶.. [Problem Solving] 백준 1339번 단어 수학 문제 풀이 백준 1339번 단어 수학 문제풀이에 대해서 알아보겠습니다. 문제 해설은 다음의 링크를 확인하여 주시기 바랍니다. https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해당 문제는 그리디 유형의 문제로 최적의 해결 방법에 대해서 고민해야 합니다. 처음 생각한 방법은 높은 자릿수 (백의 자릿수가 십의 자릿수보다 크다는 말)에 위치한 알파벳들에게 높은 숫자를 부여하는 것을 생각했습니다. 하지만 이 경우에 n = 10, data=[ABB, BB, B.. [Problem Solving] SQL 문제 풀이: 테이블 2개 이상 데이터 테이블이 2개 이상인 문제들에 대해서 문제를 풀어보겠습니다. 보호소에서 중성화한 동물 - 문제 해설 코딩테스트 연습 - 보호소에서 중성화한 동물 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr -- 코드를 입력하세요 SELECT A.ANIMAL_ID, A.ANIMAL_TYPE, A.NAME FROM ANIMAL_INS AS A , ANIMAL_OUTS AS B WHERE A.ANIMAL_ID = B.ANIMAL_ID AND A.S.. [Problem Solving] SQL 문제 풀이 (3) SQL 문제 풀이 (2)에 이어서 마지막 문제풀이를 이어나가겠습니다. 고양이와 개는 몇 마리 있을까 문제 설명 코딩테스트 연습 - 고양이와 개는 몇 마리 있을까 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr -- 코드를 입력하세요 SELECT ANIMAL_TYPE, COUNT(ANIMAL_ID) AS count FROM ANIMAL_INS GROUP BY ANIMAL_TYPE ORDER BY ANIMAL_TYPE COUNT를 사용하여 .. 이전 1 2 3 4 5 6 7 다음