본문 바로가기

코딩테스트

 (13)
[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차원 배열로..
[백준 23290] 마법사 상어와 복제(Python 풀이) https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 이 문제는 구현 문제로 문제에서 요구한 순서에 맞게 구현하는 것이 중요합니다. 주의할 점은 다음과 같습니다. 배열의 index가 0이 아닌 1번 부터 시작하도록 되어 있습니다. 물고기의 방향 정보 또한 1~8번 까지의 정보를 가지기 때문에 헷갈리지 않도록 조심해야합니다. 물고기의 냄새가 있는 곳은 '이동'을 못하는 것입니다. 따라서 물고기가 잡아 먹혀서 물고기 냄..
[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 풀이) - 2022 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 풀이 이 문제는 이진 트리에서 조건에 따라 순회 가능한 모든 경우의 수를 탐색하면서 최대 양의 개수를 구하면 정답이 됩니다. 순회는 순서에 따라 영향을 받습니다. 따라서 같은 번호를 순회하더라도 여러 경우의 수가 ..
[Programmers] 신고 결과 받기 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from collections import defaultdict def solution(id_list, report, k): answer = [] report_to_from = defaultdict(set) # key(id)를 신고한 목록 report_from..
[Programmers] k진수에서 소수 개수 구하기(Python 풀이) - 2022 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 풀이 1. k진수로의 변환 1 2 3 4 5 6 def to_k_number(n, k): # n을 k진수로 반환 ret = "" while n > 0: ret += str(n % k) n = n // k return ''.join(reversed(ret)) cs 입력 값 n이 0보다 큰 값을 가지는 동안 n을 ..
[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..
[백준 16234번] 인구이동(C++) 풀이 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 더보기 복잡한 2차원 영역을 1차원으로 변환한 후 bfs 알고리즘을 이용하여 문제 해결하였습니다. 위 사진 처럼 각 국경선이 열린 경우 점선으로 표시가 되는데 이를 나타내기 위해서 2차원 영역을 1차원으로 변환하는 게 좋다.(구현이 가능하지만 복잡해지기 때문에) 각 2차원 좌표에 차례대로 번호를 붙여 1차원 좌표로 변환한다. 2차원 좌표를 1차원 좌표로 변환하는 코드는 다음과 ..
[백준 21608번] 상어 초등학교 (Python) 문제 더보기 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N^2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생..

티스토리툴바