본문 바로가기

알고리즘

 (17)
[백준 2309] 일곱 난쟁이 (c++) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 이 문제는 아홉 난쟁이들 중 7명을 뽑아(조합)하여 키의 합이 100인 경우를 찾는 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include using namespace..
[Programmers] 빛의 경로 사이클 (Python 풀이) https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 이 문제는 좌표에서의 빛의 이동 방향에 따라 어떤 사이클이 존재하는지, 또 해당 사이클의 길이는 어떻게 되는지 조사하는 문제입니다. ㅁ 각 좌표에 대해 4방향에서 전송되는 값에 대하여 탐색을 하며 빛을 이동 시킵니다. 만약 중복이 되는 방향이 나타나는 경우 탐색을 정지해야합니다. 예를 들어 좌표 A에 방향 d가 중복되서 발견되는 경우..
[Programmers] 입국심사 (Python 풀이) https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 이 문제는 풀어야할 문제는 쉽지만 제한사항이 엄격하여 알고리즘을 잘 사용하지 않으면 통과하기 쉽지 않습니다. 제한사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. 심사관은 1명 이상 100,000명 이하입니..
[Algorithm] 삼성 SW 역량 테스트(코딩 테스트) 자주 나오는 알고리즘 유형 정리(유형별 Python Code 및 문제) 본 포스팅에서 삼성 SW 역량 테스트를 준비하며 자주 출제되는 문제를 알고리즘 별로 정리하고 Python 예시 코드를 살펴보겠습니다. 삼성 SW 역량 테스트 기출 문제는 Baekjoon Online Judge 문제를 기준으로 하였습니다. 또한 각 알고리즘을 푸는 방식은 여러 방법이 존재할 수 있습니다. https://www.acmicpc.net/workbook/view/1152 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net 1. 기본 알고리즘 삼성 기출 문제는 보통 2차원 배열을 이용한 구현, 시뮬레이션 문제를 주로 다룹니다. 비교적 최근 문제인 컨베이어 벨트 위의 로봇(https://www.acmicpc.net/problem/20055) 문제는 1차원 배열로..
[Programmers] 표 편집(Python 풀이) - 2021 카카오 채용연계형 인턴십 코딩 테스트 문제 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 풀이 이 문제는 효율성 테스트까지 통과해야합니다. 따라서 각 행들의 관계를 '링크드리스트(Linked List)' 자료형으로 정의하여 풀어야합니다. 일반 배열 자료형에 비해 링크드리스트의 경우 삭제/삽입의 시간복잡도가 O(1)인 점을 이용하여야 합니다. 링크드리스트에 대한 개념이 없는 분은 다음 링크를 참조하세요..
[Programmers] 수식 최대화(Python 풀이) - 2020 카카오 인턴십 코딩테스트 문제 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 풀이 수식의 분리(숫자와 연산자 배열) 먼저 수식을 숫자와 연산자로 분리합니다. get_numbers_and_exps() 함수는 수식을 받아 숫자 배열과 연산자 배열을 반환합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def get_numbers_and_exps(expression): # 수식을 숫자와 연산자 배열로 분리 exps = []..
[백준 20058] 마법사 상어와 파이어스톰(Python 풀이) https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 이번 문제는 배열의 회전, BFS를 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다. 우선 다음과 같이 입력을 받습니다. N, Q = map(int, input().split(' ')) # N, Q len_board = 2 ** N # 얼음을 저장할 보드의 길이 board = [list(map(int, input().split(' '))) for _ in range(le..
[백준 1202] 보석 도둑(C++ 풀이) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 이 문제는 우선순위 큐를 이용하면 간단하게 풀 수 있다. 우선 보석의 정보와 가방의 정보를 담을 배열 그리고 우선순위 큐를 다음과 같이 정의한다. pair v_jewerly[MAX]; int v_bag[MAX]; priority_queue pq; 원래는 vector 자료형을 사용했었는데, 배열 최대크기(MAX = 300001)가 너..
[백준 23291번] 어항 정리(C++ 풀이) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 더보기 우선 NxN 형태의 2차원 벡터를 이용하여 어항의 배치를 표현하였으며, 어항이 존재하지 않는 좌표는 -1로 표현하였다. 그리고 문제에서는 어항이 위로 쌓이게 되지만 편의상 배열의 아래로 쌓이도록 표현하였다. 따라서 위 그림을 배열로 표현하면 다음과 같다. 코드 상에서는 board라는 변수를 사용한다. 1 2 3 4 5 6 7 8 -1 -1 3 14 9 3 11 8 -1 -1 3 5 -..
[백준 2638번] 치즈 (C++ 풀이) 2638번: 치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 더보기 더보기 치즈의 "외부 공기"와 "내부 공기"를 BFS로 판단한 후 각 치즈의 상하좌우의 값을 확인하여 녹일 치즈를 정한다. 다음은 findAirStatusBFS()는 BFS를 이용하여 외부 공기를 판단하는 함수 // BFS를 이용하여 외부공기 판단 void findAirStatusBFS() { queue q; used = vector(N, vector(M, false)); q.push(make_pair(0, 0)); /..

티스토리툴바