SW Expert Academy
[모의 SW 역량테스트] 특이한 자석 (C++)
주어진 문제 그대로 구현하면 되는 시뮬레이션 문제입니다. 자석의 N과 S극이 닿게되면 같이 움직이므로 회전하는 방향이 바뀌는 것만 주의하면 됩니다. HTML 삽입 미리보기할 수 없는 소스
분류 전체보기
SW Expert Academy
[모의 SW 역량테스트] 원자 소멸 시뮬레이션 (C++)
원자들이 충돌할 경우 가지고 있는 에니저를 발산한 뒤 소멸하는 시뮬레이션 문제입니다. 원자가 1초에 1만큼 이동하지만 0.5초에 충돌할 수 있어 전체 격자를 2배로 늘려 계산해야 합니다. C++을 사용할 경우 vector와 같은 2차원 벡터를 사용할 수 있는데 int[][]보다 랜덤접근이 느려 TLE가 발생합니다. 원자를 저장하는 atoms 배열과 원자들의 수를 카운트하는 board, 원자들이 충돌했는지 확인하는 crash 모두 vector 구조를 사용하지 않았습니다. 아래 코드에서 위의 3개 중 하나라도 vector를 사용하면 TLE가 발생했습니다. HTML 삽입 미리보기할 수 없는 소스
SW Expert Academy
[모의 SW 역량테스트] 숫자 만들기 (C++)
연산자들의 순열을 구하고 수식을 계산한 값의 최솟값과 최댓값의 차이를 구하는 문제입니다. 구한 수식에 대해 연산자 우선순위가 적용되지 않아 그대로 구현만하면 해결할 수 있습니다. HTML 삽입 미리보기할 수 없는 소스
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]로 회전시키면 트랙위에 사람이 움직인 것과 같습니다.