개발/Algorithm

[Java] 다음 큰 숫자 (Programmers, Level 2)

문제 설명 상세한 설명은 프로그래머스에서 확인할 수 있습니다. 자연수 n을 이진법으로 표현했을 때의 1의 개수가 같으며 n보다 큰 자연수 중 가장 작은 값을 구하는 문제입니다. 예를 들어 4를 이진법으로 표현하면 0100이고, 이보다 크면서 1의 개수가 1개인 수 중 가장 작은 값은 1000인 8입니다. 제한 사항 n

[Java] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT)

문제 설명 상세한 문제 설명은 프로그래머스에서 확인할 수 있습니다. 카카오톡 오픈채팅방에서 채팅방에 입장 / 퇴장 메시지 출력을 구현하는 문제입니다. 이미 출력된 메시지에 표시된 닉네임은 기존 사용자가 닉네임을 변경할 때 전부 변경됩니다. "Muzi님이 들어왔습니다." "Prodo님이 들어왔습니다." "Muzi님이 나갔습니다." 위 상황에서 Muzi가 나간 후에, Prodo라는 닉네임으로 다시 들어올 경우 기존 채팅방에 남아있던 메시지의 Muzi도 Prodo로 변경됩니다. 닉네임의 중복은 허용하기 때문에 표시되는 닉네임은 겹칠 수 있습니다. "Prodo님이 들어왔습니다." "Prodo님이 들어왔습니다." "Prodo님이 나갔습니다." "Prodo님이 들어왔습니다." 이 때, 기존의 Prodo 닉네임을 사..

[Java] 영어 끝말잇기 (프로그래머스 Summer/Winter Coding(~2018))

문제 설명 상세한 문제 설명은 프로그래머스에서 확인할 수 있습니다. 아래와 같이 우리가 알고 있는 영어 끝말잇기 규칙과 같습니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다. 이전에 등장했던 단어는 사용할 수 없습니다. 한 글자인 단어는 인정되지 않습니다. 이 규칙에 맞게 N명이 끝말잇기를 진행할 때 가장 먼저 탈락한 사람의 번호와 자신의 몇 번째 차례에서 탈락하는지를 구하면 됩니다. 제한 사항 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다. words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하..

[Java] 성격 유형 검사하기 (2022 KAKAO TECH INTERNSHIP)

문제 설명 상세한 문제 설명은 프로그래머스에서 확인할 수 있습니다. 지표 번호 성격 유형 1 R, T 2 C, F 3 J, M 4 A, N 각 지표 번호에서 두 유형 중 성격이 강한 것을 조합하여 "RFMN", "TCMA" 같은 성격 유형을 결정합니다. 검사지는 N개의 질문과 아래와 같은 7개의 선택지가 있습니다. 선택지 성격 유형 점수 매우 비동의 첫 번째 유형 3점 비동의 첫 번째 유형 2점 약간 비동의 첫 번째 유형 1점 모르겠음 점수 없음 약간 동의 두 번째 유형 1점 동의 두 번째 유형 2점 매우 동의 두 번째 유형 3점 1번 질문이 "CF" 유형에 대한 질문인 경우 매우 비동의는 C 유형에 3점 동의는 F유형에 3점 이 부여되는 방식입니다. 만약 각 지표 번호에서 두 성격 유형 점수가 같다면 ..

[Java] 크레인 인형뽑기 게임 (2019 카카오 개발자 겨울 인턴십)

문제 설명 상세한 문제 설명은 프로그래머스에서 확인할 수 있습니다. 인형들이 세팅된 N x N의 2차원 배열 board에서 인형을 집어 오른쪽 바구니로 옮기는 문제입니다. 먼저 바구니로 옮겨진 인형들 위로 새로 옮긴 인형들이 쌓이는 방식인데, 같은 인형이 두 개 쌓이게 되면 해당 인형들은 사라지게 됩니다. 또한 바구니 크기는 제한이 없습니다. (최대 N * N 개의 인형이 쌓일 수도 있는 겁니다) 크레인 위치를 1~N 사이로 이동시키도록 하는 배열 moves에 따라 인형을 뽑을 때 최종적으로 사라진 인형의 개수를 구하는 문제입니다. 제한 사항 board 배열은 2차원 배열로 크기는 5x5 이상 30x30 이하입니다. board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다. 0은 빈칸을 나타냅..

[Java] 백준 2178번: 미로 탐색

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 핵심 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 밑줄 친 부분을 통해서 BFS 풀이법으로 접근해 볼 힌트를 얻을 수 있습니다. 풀이 class Point { int y; ..

[Python] k진수에서 소수의 개수 구하기 (2022 Kakao)

이 문제는 2022년도 카카오 신입 공채 1차 온라인 코딩 테스트에서 출제된 문제이며 프로그래머스에서 풀이했습니다. 문제 설명 양의 정수 n 이 주어집니다. 이 숫자를 k 진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0 처럼 소수 양쪽에 0 이 있는 경우 P0 처럼 소수 오른쪽에만 0 이 있고 왼쪽에는 아무것도 없는 경우 0P 처럼 소수 왼쪽에만 0 이 있고 오른쪽에는 아무것도 없는 경우 P 처럼 소수 양쪽에 아무것도 없는 경우 단, P 는 각 자릿수에 0 을 포함하지 않는 소수입니다. 예를 들어, 101 은 P 가 될 수 없습니다. 예를 들어, 437674 을 3 진수로 바꾸면 211020101011 입니다. 여기서 찾을 수 있는..

[Python] 정수 삼각형 (Programmers Lv. 3)

문제 설명 제한 사항 입출력 예 풀이 주어진 문제에 대한 최적값을 구하는 것이기 때문에 Dynamic Programming(동적 계획법)으로 접근해볼 수 있습니다. 하위 문제의 수가 기하급수적으로 증가할 때 유용한 접근법입니다. 즉, 하위 문제를 해결하는 과정에서 DP Table을 채우면서 주어진 문제를 해결할 수 있는 방법이라고 할 수 있습니다. 해설 (x, y)에서부터 시작한다고 하면, (x, y+1), (x+1, y+1)을 계산해 최댓값을 계속 저장하게 됩니다. (x, y)에서 계산된 (x, y+1), (x+1, y+1)과 (x+1, y)에서 계산된 (x+1, y+1), (x+2, y+1) 중에서 (x+1, y+1)이 겹칩니다. 매 계산마다 현재 해당 좌표에 저장된 값과 새로 계산된 값의 크기를 비..