두 수 XOR 합과 유사한 문제이다. 숫자를 이진수로 변경하여 트라이에 넣어주고, 숫자 중 i번째까지 XOR한 값을 prefix에 저장해서 답을 구한다. 같은 수를 XOR 연산하면 항상 0이 된다. 따라서 S[i] = A[1] ~ A[i]를 XOR 연산한 결과라고 한다면, A[i] ~ A[j]까지 XOR 연산한 결과를 S[j] - S[i - 1] 이라고 할 수 있다. 따라서 수를 트라이에 넣으면서 연산을 누적해나가며 S[i]와 S[j]를 XOR한 값이 가장 큰 것으로 찾는 것으로 변형할 수 있다. #include #include using namespace std; struct Node { int children[2]; bool valid; Node() { children[0] = children[1] ..
👻 문제 설명 BFS문제이지만, 인접한 칸으로 이동하는 기존 문제와 다르게 90도로 이동해야 하는 점 + 거울을 설치할 수 있는 곳까지 연속으로 쭉 이동해야하는 점이 달랐습니다. 이 점을 유의해서 BFS 코드를 조금 고쳐서 풀어보았습니다 : ) 😔 해결 과정 편의 상, 시작점 (#)에서 도착점(#) 까지 '빛이 이동한다'라고 표현하겠습니다. BFS를 수행하는 목적은, 빛이 시작점에서 도착점까지 이동하였을 때 '거울이 최소 몇 번 사용되느냐' 입니다. 이 말은 즉, '빛이 최소 몇 번 꺾이느냐'를 의미합니다. 따라서 거울을 놓을 수 있는 모든 위치에 대해서, 빛이 꺾일 수 있는 다음 위치를 모두 찾아 이동하는 것을 시뮬레이션하고 도착점(#)에 도달하였을 때 사용한 거울의 최솟값을 구하면 됩니다. 이 때 유..
🥲 문제 설명 https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 🐹 문제 해설 이 문제는 아래 두 가지로 나뉜다. (1) 돌을 2개 놓는 부분 (경우의 수 : 400 * 400 = 160,000) (2) 죽일 수 있는 상대 돌의 개수를 구하는 부분 (경우의 수 : (400 * 400) ^ 3 = 64000000) 방문하지 않은 돌을 찾는다. 그 돌에 속한 그룹을 찾는다. 그룹은 최대 3개씩 속하므로, 4..
https://school.programmers.co.kr/learn/courses/30/lessons/60057# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👻 문제 설명 😔 해결 과정 문자열을 자를 수 있는 단위는 최소 1에서 최대 s의 길이의 절반이다. 모든 경우를 탐색하면서, 문자열 압축을 하였을 때 가장 짧은 길이를 찾는 방식으로 문제를 풀었다. "abcabcabcdede" 의 문자열이 주어졌을 때, x = 3 즉 3개 단위로 자르는 경우를 예제를 들어보겠다. string target = s.substr(i, x); int k = 0; whi..
😙 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/150369# [프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/150369#) 🌸 해결 과정 deliveries와 pickups 배열의 마지막 부분부터 접근하여, cap 만큼의 짐을 배달하고 수거하는 것을 반복하였다. 이 때 무작정 cap 크기의 짐을 실고 가게 되면, 다 배달하지 못하여 돌아올 때 회수할 수 있는 택배의 개수가 줄어들..
🐹 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 😊 해결 과정 1. 주문된 모든 메뉴 조합 orders에 대해서, 코스요리 메뉴로 선정 가능한 후보를 모두 뽑는다. void findCombination(string order, int index, string& result, set& combinations) { if (index == order.size()) { if (result.size() >= 2){ set s; for(ch..
https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧐문제 설명 문제에서 banned_id라는 배열로 주어진 아이디의 목록을 분석해, 제재 아이디를 만드는 경우의 수를 구하는 문제이다. ⭐ 해결 과정 나는 이 문제를 중복 set을 이용해 풀었다. 예제 입력 2번을 이용해 설명해보자면, graph를 만들듯이 각 banned_id에 포함되는 user_id들을 찾아 이차원 배열 candidiates에 넣어주었다. 그 다음, 재귀함수를 사용해 candid..
https://school.programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 school.programmers.co.kr 문제 설명 이렇게 board가 주어져 있다면, 빈칸 (0)에서만 로봇을 움직여 (n -1, m -1) 로 가야한다. 갈 수 있는 모든 경우의 수에서 최단 시간을 구하면 된다. 일반적인 BFS 문제와 다르게 로봇은 두 칸을 차지하고, 회전이 가능하다는 점이 특징이었다. 로봇은 어느 방향으로든 90도 회전이 가능하나, 이동하는 방향의 대각선 칸이 벽(1)이라면 회전할 수..
https://school.programmers.co.kr/learn/courses/30/lessons/17682 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 문자열을 파싱하여 다트 게임에서의 점수를 구하는 문제이다. 해결 과정 (1) 점수는 최대 10까지 있으므로 while문을 돌려 점수를 구해 score 변수에 저장하였다 . (2) 다음 인덱스에 접근해 보너스가 S, D, T인지에 따라 score의 값을 늘려주었다. (3) 다음 위치가 정수라면 옵션이 없는 것이므로 패스하고, 정수가 아니라면 *, #인지 여부를 파악해 점수를 수정하였다. ..
