알고리즘 문제풀이
-
BOJ 17140번 이차원 배열과 연산 문제 자바(java) 풀이 랭크 : 골드4 백준 17140번 이차원 배열과 연산 문제 정리 크기가 3x3인 배열 A 1초마다 배열에 연산 적용 R연산: 배열 A의 모든 행에 대해서 정렬을 수행. 행 >= 열 C연산: 배열 A의 모든 열에 대해서 정렬을 수행. 행 < 열 각각의 수가 몇 번 나왔는지 알아야 함. 수의 등장 횟수가 커지는 순으로 정렬 그러한 것이 여러가지이면 수가 커지는 순으로 정렬 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저 R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변함 C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변함 행 또는 열의 크기가 커진 곳에는 0이 채워..
[BOJ] 삼성 sw 역량 테스트 :: 17140번 이차원 배열과 연산 (java)BOJ 17140번 이차원 배열과 연산 문제 자바(java) 풀이 랭크 : 골드4 백준 17140번 이차원 배열과 연산 문제 정리 크기가 3x3인 배열 A 1초마다 배열에 연산 적용 R연산: 배열 A의 모든 행에 대해서 정렬을 수행. 행 >= 열 C연산: 배열 A의 모든 열에 대해서 정렬을 수행. 행 < 열 각각의 수가 몇 번 나왔는지 알아야 함. 수의 등장 횟수가 커지는 순으로 정렬 그러한 것이 여러가지이면 수가 커지는 순으로 정렬 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저 R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변함 C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변함 행 또는 열의 크기가 커진 곳에는 0이 채워..
2020.10.19 -
BOJ 17779번 게리맨더링 2 문제 자바(java) 풀이 랭크 : 골드4 백준 17779번 게리맨더링 2 문제 정리 재현시의 크기 NxN 5개의 선거구로 나누어야 함 각 구역은 5개의 선거구 중 하나에 포함되어야 함 선거구는 적어도 구역 하나를 가져야 함 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함 인접한 구역을 통해 갈 수 있으면 연결되어 있다고 본다. 선거구에 있는 구역들은 모두 그 내에서 연결되어 있어야 한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자 문제 풀이 문제에서 주어진 대로 선거구를 정확히 나누기만 하면 쉬운 문제이다. 다만 처음에 0번 인덱스부터 했더니 헷갈려서 좀 걸렸다... 헤맸는데도 1시간 정도 걸린것 같다. 삼성 기출 중엔 쉬운..
[BOJ] 삼성 sw 역량 테스트 기출 :: 17779번 게리맨더링 2 (java)BOJ 17779번 게리맨더링 2 문제 자바(java) 풀이 랭크 : 골드4 백준 17779번 게리맨더링 2 문제 정리 재현시의 크기 NxN 5개의 선거구로 나누어야 함 각 구역은 5개의 선거구 중 하나에 포함되어야 함 선거구는 적어도 구역 하나를 가져야 함 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함 인접한 구역을 통해 갈 수 있으면 연결되어 있다고 본다. 선거구에 있는 구역들은 모두 그 내에서 연결되어 있어야 한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자 문제 풀이 문제에서 주어진 대로 선거구를 정확히 나누기만 하면 쉬운 문제이다. 다만 처음에 0번 인덱스부터 했더니 헷갈려서 좀 걸렸다... 헤맸는데도 1시간 정도 걸린것 같다. 삼성 기출 중엔 쉬운..
2020.10.18 -
프로그래머스 올바른 괄호 자바(java) 풀이 Level 2 Stack [올바른 괄호]](https://programmers.co.kr/learn/courses/30/lessons/12909#) 문제 정리 괄호가 올바로 짝지어져 있다: '('문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫힌다 문자열 s가 주어졌을때 올바른 괄호 문자열인지 아닌지 판별하여라 문자열의 길이는 최대 100,000 문자열 s는 '(' ')' 만으로 이루어져 있다. 힙, 우선순위 큐 이 문제는 stack을 이용하면 쉽게 구현할 수 있습니다. 이와 비슷한 문제가 이번 카카오 코테에도 나왔습니다. 그렇기테때문애 확실히 이해하는게 중요합니다. 주어진 문자열을 캐릭터(문자) 배열..
[스택] 프로그래머스 level2 올바른 괄호 c++, java 풀이프로그래머스 올바른 괄호 자바(java) 풀이 Level 2 Stack [올바른 괄호]](https://programmers.co.kr/learn/courses/30/lessons/12909#) 문제 정리 괄호가 올바로 짝지어져 있다: '('문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫힌다 문자열 s가 주어졌을때 올바른 괄호 문자열인지 아닌지 판별하여라 문자열의 길이는 최대 100,000 문자열 s는 '(' ')' 만으로 이루어져 있다. 힙, 우선순위 큐 이 문제는 stack을 이용하면 쉽게 구현할 수 있습니다. 이와 비슷한 문제가 이번 카카오 코테에도 나왔습니다. 그렇기테때문애 확실히 이해하는게 중요합니다. 주어진 문자열을 캐릭터(문자) 배열..
2020.07.09 -
프로그래머스 행렬의 곱셈 c++ 풀이 Level 2 연습문제 행렬의 곱셈 문제 정리 2차원 행렬 arr1, arr2가 주어질때 두 행렬을 곱한 결과를 반환하는 함수를 작성하여라 행과 열의 길이는 2 이상 100 이하이다. (최대 100x100) 행렬의 원소는 -10 이상 20 이하의 자연수이다. 곱할 수 있는 배열만 주어진다. 문제 풀이 20^2 x 100 = 400 x 100 = 40000으로 int형으로 가능 이 문제는 단순히 행렬 곱셈의 개념만 알고 있다면 풀 수 있습니다. 2차원 벡터를 다루는 문제로 좋은 예제라고 생각합니다. (실제로 제가 그랬음) 왼쪽 행렬의 i행, 오른쪽 행려의 j열을 sumproduct 하면 새로운 행렬의 (i,j) 위치의 값이 됩니다. 예를들어 arr1의 1행, arr2의..
[수학, 2차원 벡터] 프로그래머스 level2 행렬의 곱셈 c++ 풀이프로그래머스 행렬의 곱셈 c++ 풀이 Level 2 연습문제 행렬의 곱셈 문제 정리 2차원 행렬 arr1, arr2가 주어질때 두 행렬을 곱한 결과를 반환하는 함수를 작성하여라 행과 열의 길이는 2 이상 100 이하이다. (최대 100x100) 행렬의 원소는 -10 이상 20 이하의 자연수이다. 곱할 수 있는 배열만 주어진다. 문제 풀이 20^2 x 100 = 400 x 100 = 40000으로 int형으로 가능 이 문제는 단순히 행렬 곱셈의 개념만 알고 있다면 풀 수 있습니다. 2차원 벡터를 다루는 문제로 좋은 예제라고 생각합니다. (실제로 제가 그랬음) 왼쪽 행렬의 i행, 오른쪽 행려의 j열을 sumproduct 하면 새로운 행렬의 (i,j) 위치의 값이 됩니다. 예를들어 arr1의 1행, arr2의..
2020.07.08 -
프로그래머스 피보나치 수 c++ 풀이 Level 2 연습문제 피보나치 수 문제 정리 n이 주어질 때 n번째 피보나치 수를 1234567로 나눈 나머지를 구하여라 n은 2이상 100000 이하이다. 문제 접근 피보나치 수를 알기 위해서는 이전의 2개의 수만 알면 된다. 그렇기 때문에 2개의 수만 관리한다. n이 최대 100,000이기 때문에 배열을 모두 만들면 낭비이다. 또한 계속 값을 더해나간 후 마지막에 모듈러 연산을 하면 값이 범위를 넘어 이상한 값이 나올 수 있다. 그렇기 때문에 모듈러 연산의 성질을 이용하면 간단히 풀 수 있다. 모듈러 연산의 성질 이 성질만 안다면 간단히 풀 수 있습니다. (a + b) % c = ((a % c) + (b % c)) % c 예를들어 (10 + 1) % 3 = (1..
[수학, 모듈러 성질] 프로그래머스 level2 피보나치 수 c++ 풀이프로그래머스 피보나치 수 c++ 풀이 Level 2 연습문제 피보나치 수 문제 정리 n이 주어질 때 n번째 피보나치 수를 1234567로 나눈 나머지를 구하여라 n은 2이상 100000 이하이다. 문제 접근 피보나치 수를 알기 위해서는 이전의 2개의 수만 알면 된다. 그렇기 때문에 2개의 수만 관리한다. n이 최대 100,000이기 때문에 배열을 모두 만들면 낭비이다. 또한 계속 값을 더해나간 후 마지막에 모듈러 연산을 하면 값이 범위를 넘어 이상한 값이 나올 수 있다. 그렇기 때문에 모듈러 연산의 성질을 이용하면 간단히 풀 수 있다. 모듈러 연산의 성질 이 성질만 안다면 간단히 풀 수 있습니다. (a + b) % c = ((a % c) + (b % c)) % c 예를들어 (10 + 1) % 3 = (1..
2020.07.07 -
프로그래머스 최댓값과 최솟값 c++ 풀이 Level 2 연습문제 최댓값과 최솟값 문제 정리 문자열 s에는 공백으로 구분된 숫자가 있다. str에 나타나는 숫자중 최대, 최소 값을 찾아 "(최소값) (최댓값)" 형태로 반환해라 문자열에는 둘 이상의 정수가 공백으로 구분되어 있다. 문제 풀이 문자를 공백을 기준으로 나눈다. 나눠진 수를 차례대로 하나씩 숫자로 변환해본다. min, max와 비교해서 업데이트 해준다. 최종 min, max 값을 string으로 변환하여 정답을 완성한다. c++ 문자열 split sstream 헤더에 있는 istringstream 을 이용해서 나눌 수 있다. istringstream ss(split할 문자열)을 선언한다 자를 문자를 담을 string buffer를 선언한다(str..
[문자열] 프로그래머스 level2 최댓값과 최솟값 c++ 풀이프로그래머스 최댓값과 최솟값 c++ 풀이 Level 2 연습문제 최댓값과 최솟값 문제 정리 문자열 s에는 공백으로 구분된 숫자가 있다. str에 나타나는 숫자중 최대, 최소 값을 찾아 "(최소값) (최댓값)" 형태로 반환해라 문자열에는 둘 이상의 정수가 공백으로 구분되어 있다. 문제 풀이 문자를 공백을 기준으로 나눈다. 나눠진 수를 차례대로 하나씩 숫자로 변환해본다. min, max와 비교해서 업데이트 해준다. 최종 min, max 값을 string으로 변환하여 정답을 완성한다. c++ 문자열 split sstream 헤더에 있는 istringstream 을 이용해서 나눌 수 있다. istringstream ss(split할 문자열)을 선언한다 자를 문자를 담을 string buffer를 선언한다(str..
2020.07.05