SW Expert Academy
[모의 SW 역량테스트] 숫자 만들기 (C++)
연산자들의 순열을 구하고 수식을 계산한 값의 최솟값과 최댓값의 차이를 구하는 문제입니다. 구한 수식에 대해 연산자 우선순위가 적용되지 않아 그대로 구현만하면 해결할 수 있습니다. HTML 삽입 미리보기할 수 없는 소스
전체 글
백준, 프로그래머스, SWEA, 코드트리 문제 풀이 전용SW Expert Academy
[모의 SW 역량테스트] 탈주범 검거 (C++)
맨홀 위치에서 탈주범이 있을 공간의 수를 출력하는 문제입니다. 단순하게 맨홀 위치에서 시작하여 BFS로 탐색하면 되고 맨홀 위치의 시간을 0으로 두었을 때 파이프를 통해 시간을 1씩 증가시켜 L 시간 내의 범위의 공간의 수를 세면 됩니다. HTML 삽입 미리보기할 수 없는 소스
백준
백준 9657 돌 게임 3 (Python)
돌 게임 문제는 DP로 쉽게 풀 수 있지만 미니맥스 알고리즘을 사용한 풀이도 가능합니다. 미니맥스 알고리즘 풀이를 찾아봤지만 없어서 직접 구현했습니다. 미니맥스 알고리즘은 서로 게임에 최선을 다하는 알고리즘입니다. 나는 상대방에게 이득이 되는 행동을 하지 않고 상대방도 나에게 이득이 되는 행동을 하지 않도록 탐색하는 알고리즘입니다. minimax(stone, player) 함수는 남은 돌의 개수(stone)과 나 또는 상대방인지를 알 수 있는 player 인자를 갖습니다. 마지막 돌을 가져가는 사람이 지는 것이므로 내가 마지막 돌을 가져가면 0(내가 지면), 상대방이 가져가면(내가 이기면) 1을 반환하도록 작성했습니다. 이제 내가 돌을 (1 or 3 or 4)개를 가져간 후 상대방의 리턴 값은 0(내가 ..
코드트리
코드트리 채점기 (C++)
2023 삼성 상반기 코딩테스트 오후 2번 문제입니다. TLE를 해결하지 못해 다른 사람의 풀이를 보고 계속 코드를 고쳐가면서 문제를 풀었습니다. 단순한 구현이 아닌 적절한 자료구조를 사용하고 한번 더 생각해야 해서 개인적으로 잘 만든 문제라고 생각합니다. 우선 어떠한 task가 채점이 될 수 없는 조건은 다음과 같습니다. - 해당 task의 도메인이 현재 채점을 진행중인 도메인 중 하나라면 불가능합니다. - 해당 task의 도메인과 정확히 일치하는 도메인에 대해 가장 최근에 진행된 채점 시작 시간이 start, 종료 시간이 start+gap 였고 현재 시간 t가 start+3×gap 보다 작다면, 부적절한 채점이라 의심되기에 채점이 불가합니다. 채점기로 들어가는 위의 조건때문에 url을 검사해야 합니다..
코드트리
코드트리 메이즈 러너 (C++)
2023 삼성 상반기 코딩테스트 오후 1번 문제입니다. 출구와 가장 가까운 사람을 포함하는 정사각형 범위를 찾고 이를 회전해야 합니다. 이때 정사각형 범위 내 사람이 있는 경우 같이 회전시켜야 합니다. 정사각형을 찾는 코드는 반복문을 사용했는데 (10,10)인 보드에서 최대 크기 10인 사각형을 찾는 코드라서 크게 시간을 잡아먹지 않는다고 생각했습니다. 그리고 거리가 abs(x1-x2)+abs(y1-y2)로 정의되어 있어 bfs나 dfs를 사용하지 않고도 사람을 이동시킬 수 있습니다. 출구와 같은 거리를 가진 경로가 여러개라면 행 -> 열 방향으로 우선순위를 적용해야 합니다. HTML 삽입 미리보기할 수 없는 소스
프로그래머스
2022 KAKAO TECH INTERNSHIP 문제풀이 (Python)
성격 유형 검사하기 그냥 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 두 큐 합 같게 만들기 생각보다 헷갈릴 수 있는 문제라고 생각합니다. queue1, queue2의 길이가 최대 300,000이므로 이중for문으로 탐색하면 TLE를 발생시킵니다. 따라서 두 큐를 합쳐 투포인터로 탐색하여 문제를 해결할 수 있습니다. i와 j 포인터는 i ≤ j < len(queue1+queue2)의 조건을 가지고 탐색하는데 이때 몇 가지 경우를 생각해볼 수 있습니다. 첫 번째는 두 포인터가 queue1에서 모두 위치한 경우입니다. 뒤쪽의 j 포인터가 가리키는 값까지 모두 queue2로 옮기고 원래 queue2에 있던 값들과 queue1의 i 포인터 앞까지 queue1으로 옮겨야 하므로 (j+1)+i+len..
프로그래머스
2022 KAKAO BLIND RECRUITMENT 문제풀이 (Python)
신고 결과 받기 그대로 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 k진수에서 소수 개수 구하기 문제에서 주어진대로 n을 k진수로 변환하고 0과 0사이의 수가 소수인지 판별하면 됩니다. python에서 int(), bin() 등과 같이 k진수법으로 표현된 수를 10진수로 변환하는 함수는 있지만 10진수를 k진법으로 표현하는 함수는 없으므로 직접 구현해야 합니다. 변환하는 방법은 10진수를 2진수로 바꾸는 방법처럼 계속 나눠 나머지를 뒤에 추가하여 구현할 수 있습니다. def conv(n,k): base = '' while n > 0: n, mod = divmod(n, q) base += str(mod) return base[::-1] """ tc1 : n = 437674, k = 3 ----..
코드트리
코드트리 꼬리잡기 (C++)
생각보다 어려운 문제였습니다. 트랙위에 사람이 트랙을 따라가는 것을 구현하기 위해 트랙 전부를 저장하여 회전하는 것으로 구현했습니다. 예를들면, 첫 번째 예시 왼쪽 상단의 트랙에 대해 person=[1,2,3,4,4,4,4,4], track=[(0,2),(0,1),(0,0),(1,0),(2,0),(2,1),(2,2),(1,2)]으로 저장하고 person 배열을 [2,3,4,4,4,4,1]로 회전시키면 트랙위에 사람이 움직인 것과 같습니다. HTML 삽입 미리보기할 수 없는 소스
코드트리
코드트리 빵 (C++)
문제를 그대로 구현하면 됩니다. 어떤 사람이 원하는 편의점에서 가장 가까운 베이스캠프를 지정할 때 이전 사람들이 지정한 베이스캠프를 지나지 못하도록 주의해야 합니다. 따라서 베이스캠프 위치를 정할때는 미리 정하지 않아야 합니다. HTML 삽입 미리보기할 수 없는 소스
코드트리
코드트리 싸움땅 (C++)
문제에 주어진 과정을 그대로 따라가면서 구현하면 됩니다. 처음에는 땅에 하나의 총이 떨어져 있거나 없는 경우가 있지만 라운드를 거치면서 한곳에 여러개의 총이 떨어져 있을 수 있음을 알아야 합니다. HTML 삽입 미리보기할 수 없는 소스