본문 바로가기

컴퓨터/알고리즘36

[BOJ] 16926. 배열돌리기 1 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 배운점 : 규칙적으로 돌리면 코드가 더 깔끔해진다. ^^ ( ​ 죄송합니다.. 설명하려고 그림 그렸는데 다 푼 문제에 똥을 뿌려버렸네요 ​ 그.. 삽입정렬 아시죠? 2,3,4,5 에서 배열을 추가하지 않고 옮기려면 어떻게 했나요? ​ X 2 3 4 5 맨 뒤에 1칸을 더 할당해서 맨 오른쪽부터 왼쪽으로 .. 2021. 8. 30.
[Programmers] 2021 카카오 인턴십 2번 - 거리두기 확인하기 https://programmers.co.kr/learn/courses/30/lessons/81302?language=cpp 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 처음에 풀었을때 방향이 너무 많아서 이게 뭐지? 싶었는데.. 침착하.. 2021. 8. 25.
[BOJ] 12865. 평범한 배낭(0-1 knapsack) ttps://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 그리디를 하면 망해버립니다. ​ 처음에 0-1 knapsack이란걸 모르다가, 이건 DP인것 같은데 DP를 어떻게 해야할까? 라는 고민을 했습니다. 그 다음에 했던건 그리디의 느낌으로.. ​ 1. 실패한 과정 (그리디) Value 순으로 내림차순 정렬을 했습니다. 맨 위에부터 계속 value를 더합니다. 그다음 w도 누적으로 더해줍니.. 2021. 8. 20.
[BOJ] 2579 계단오르기, C Macro function(매크로함수) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 실수를 남기는 글입니다. 풀이방법 : DP DP는 어떻게 풀까요.. 이론상 O(N)인데, 이 안에 맞추려면 점화식을 찾고, 이전에 계산한 내용으로 다음 내용을 맞추죠. 테이블을 채워나간다고 생각하더라구요. 뭐 지금 그렇게 느끼고 있습니다. 이건 2차원 배열로 풀었습니다. DP table을 왜 2차원으로 만드는 생각은 못했을까요. 항상 다른 방향으로 생각하자고 생각하는데.. 열정으로 노력합시다!! 열정!! 규칙.. 2021. 7. 26.
[BOJ] 1016. 제곱ㄴㄴ수 (에라토스테네스의 체) https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 풀이방법 : 에라토스테네스의 체 + 약간의 조정 (제한시간 2초) ​ 접근 : 가장 naive한 방법으로 생각해봤다. for( i = 2; i 2021. 7. 8.
[BOJ] 1080. 행렬 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 그리디 알고리즘... 매 순간마다 최적의 선택을 한다. 결론이 나왔을때 이것이 최고가 아닐수도 있다. 하지만 그렇게 푸는거다. ​ 이 문제는 그리디 알고리즘인데, 가장 적게 뒤집으면서 B 행렬과 같은지 판단해야한다. ​ 난 무지성인간이라 처음에 그냥 브루트포스로 다 뒤집었다. 이게 최적이 될리가 없었다. 평소에 일단 완전탐색처럼 풀고, 비효율적인걸 걷어내는식으로 했는데.. 이건 그 방식으로 접근하다가 머리가 너.. 2021. 3. 16.
[BOJ] 2573 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net #include #include typedef long long ll; using namespace std; int board[305][305]; int board2[305][305]; bool visited[305][305]; int mx[4] = {0,0,1,-1}; //동 서 남 북 int my[4] = {1,-1,0,0}; int year; int solve(int n,int m) { int tx,.. 2021. 2. 23.
[SWEA] 9700. USB 꽂기의 미스터리 (문제 꼼꼼히 읽어야하는 이유) swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AXDNEA3aaU0DFAVX&categoryId=AXDNEA3aaU0DFAVX&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=2 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com #include #include typedef long long ll; using namespace std; int main(void) .. 2021. 2. 20.
[SWEA] 10726. 이진수 표현 (비트마스크),연산자 우선순위 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXRSXf_a9qsDFAXS SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com #include typedef long long ll; using namespace std; int main(void) { int size; ll n,m,t,t2; scanf("%d",&size); for(int i = 0; i < size; i++) { scanf("%lld %lld",&n,&m); t = (1 2021. 2. 17.
[SWEA] 10570. 제곱 팰린드롬 수 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXO72aaqPrcDFAXS SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com #include #include typedef long long ll; using namespace std; int check_pal(int num)//맞으면 1, 아니면 0리턴 { if( num / 10 == 0) return 1; else if(num / 10 < 10) { if(num % 10 == num / 10) return 1; }else{ if(num / 100 == num % 10) .. 2021. 2. 16.
728x90

티스토리툴바