본문 바로가기

전체 글133

[프로그래머스] level 3 - 보행자 천국, C++ https://programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 2017 카카오코드 예선 문제로 DFS 문제를 활용한 DP 문제다. 예를들어 DP 문제는 d[i] = MAX( d[i-1], d[i-2] )와 같이 작은 문제로 나누어 계산하는 방식인데 중복되는 경우가 많을 경우 1번만 계산을 하여 연산량을 줄이는 방법이다. /* 개인적인 DP 문제 해결 방법은 점화식이 바로 떠오르면 아! DP 문제구나 하고 bottom up으로 풀다. 그게 아니면 먼저 모든 경우를.. 2020. 3. 26.
[프로그래머스] level 3 - 여행경로, C++ https://programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 DFS 문제로 주어진 모든 항공권을 이용하여 여행하는 방법을 찾는 문제다. 이때, 경로가 여러개인 경우 알파벳 순으로 앞선 경우를 return 한다. 다른 어려운 DFS/BFS 문제들은 연산량이 많아 메모리 초과가 되어 다른 방식으로 DFS/BFS 연산을 해야 하는데 이 문제는 딱 한가지 경우를 생각 못하면 풀기 힘든 문제다. 바로 [["ICN", "COO"], ["ICN", "BOO"], ["CO.. 2020. 3. 26.
[프로그래머스] 2020 KAKAO BLIND RECRUITMENT - 자물쇠와 열쇠, C++ https://programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 2020 KAKAO BLIND RECRUITMENT 문제로 정답률 7.4%다. 문제를 보면 설명이 좀 길다. 간단하게 설명하면 키를 회전과 이동을 하여 자물쇠의 모든 값이 1인 경우 true를 return하는 문제다. 문제 해결 과정은 다음과 같다. 우선 개인적으로 프로그래머스에서 vector로 입력되는게 싫다. 따라서 2차원 배열로 값을 저장하였다. cal() 함수를 이용해 키를 회전하였다. 배열.. 2020. 3. 24.
[백준 1005] ACM Craft, C++ https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 본 문제는 DAG(topology sort)를 구현하는 문제다. 각 작업마다 필요한 선행작업 개수를 구하고, 선행작업이 0인 작업 .. 2020. 3. 22.
[백준 16926] 배열 돌리기 1, C++ 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] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4 www.acmicpc.net 본 문제는 시뮬레이션 문제다. 문제의 설명은 링크를 참고하길 바란다. 배열의 크기는 300x300 이고 회전은 1000번까지 .. 2020. 3. 12.
[백준 16234] 인구 이동, C++ https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 본 문제는 삼성 SW 역량 테스트 기출 문제로 시뮬레이션 문제다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구.. 2020. 3. 10.
[백준 1525] 퍼즐, C++ https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 본 문제는 지금까지 풀었던 BFS와 저장과 확인 방식의 차이가 있어 글을 쓰게 되었다. 그 동안 BFS는 2차원 배열로 정보를 저장하여 최단 거리를 구했는데 이 문제는 string과 set을 이용하여 최단 거리를 구하였다. 실제 코딩 테스트나 시험에 나왔으면 많이 당황할 문제라고 생각한다. 설명은 주석 처리를 하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484.. 2020. 3. 9.
[백준 11051] 이항 계수 2, C++ https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 본 문제는 이항 계수의 성질을 이용하여 푸는 문제다. 이항 계수는 (n, k) = (n-1, k) + (n-1, k-1)의 식이 성립하고, (n, 0) = 1, (i, i) = 1 (단, 1 2020. 3. 8.
[백준 12358] 시험 감독, C++ https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 본 문제는 삼성 SW 역량 테스트 기출 문제다. /* 개인적인 생각으로 역대 시험 문제중 제일 쉽다고 생각한다. 왜냐하면 기존 삼성 문제는 접근도 쉽지 않았고, 구현도 힘들다. 그런데 이번 문제는 접근도 쉽고, 구현도 간단하다. 프로그래머스 level 2 수준 정도 되는거 같다. */ 문제의 조건은 다음과 같다. 각각의 시험장에 총감독관은 .. 2020. 3. 3.

티스토리툴바