지난해 sdc2024를 본 경험과 인상깊었던 점,
내가 평소에 생각하는 협업, 및 플젝 과정 중 고민했던 부분들을 자소서에 녹여냈었다.
인턴 서류 합격을 해서
sw역량테스트 준비과정기를 적어보려한다.
sw역량테스트
바로 인터넷을 찾아봤다.
준비 방향성은 어렵지 않게 찾을 수 있었다.
https://company-n-job.tistory.com/44
[[삼성전자] 1. 코딩테스트 후기 및 꿀팁 feat."삼성전자 인재개발원 환경"
우선 나는 삼성전자 DX (삼성리서치)에 지원하여, 오늘 용인에 있는 인재개발원에서 오전에 코딩시험을 보고 왔다. ps. 나는 2문제 중에 주로 1번이라고 표현하는 구현(시뮬레이션) 문제에 올인하
company-n-job.tistory.com](https://company-n-job.tistory.com/44)
위 방향성을 토대로 풀어야할 문제들을 정리했다.
대체로 아래 두 개로 통일된다.
https://www.acmicpc.net/workbook/view/1152
https://www.codetree.ai/ko/frequent-problems/problems/virus-detector/description
그리고 6일 전부터는 sw expert 구현 환경에서의 감을 익혀야 한다.
매일 20문제...ㅋㅋㅋㅋ 씩 풀어보자. 면 좋겠지만, 최대한 많이 투자를 하려고 한다.
매일 10시간씩! 가보자!!
4/4
백준 13458 시험감독
더보기
package 알고리즘_코딩테스트.dayone.apr04;
/*
삼성sw역량테스트
주의
answer(최소 감독수 결과값) 최악의 경우 int범위(2_147_483_648)를 넘어갈 수 있음
*/
import java.io.*;
import java.util.*;
public class boj_13458 {
static int n;//시험장의 개수
static long[] arr;//각 시험장 마다 응시자 수
static long[] gamdok = new long[2];//총감독관 , 부감독관이 한 시험장에서 감시할 수 있는 응시자 수
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args)throws IOException {
input();
solve();
/*
조건1: 총감독관은 없어도 되고 있으면 최대 1명
*/
}
private static void solve(){
long answer = 0;
//구현
answer += n;//주의 : gamdok[0]이 아님!!
for(int i = 1; i < n+1; i++){
arr[i] -= gamdok[0];//총감독관 쓰기
if (arr[i] <= 0) continue; //끝!
answer += arr[i] / gamdok[1];//부감독관 쓰기
if (arr[i] % gamdok[1] != 0){//남은거
answer++;
}
}
System.out.println(answer);
}
private static void input()throws IOException{
n = Integer.parseInt(bf.readLine());
arr = new long[n+1];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i = 1 ; i < n+1; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
//총 감독관, 부 감독관
st = new StringTokenizer(bf.readLine());
gamdok[0] = Long.parseLong(st.nextToken());
gamdok[1] = Long.parseLong(st.nextToken());
}
}answer += n 더하는 값에 대해 신중히 생각하자.
백준 14501 퇴사
더보기
package 알고리즘_코딩테스트.dayone.apr04;
import java.io.*;
import java.util.*;
/*
삼성sw역량테스트
주의
dp[i + arr[i].t] = Math.max(dp[i + arr[i].t], dp[i] + arr[i].p )
=> 현재날의 상담 기간을 계산했을 때 끝나는 날에 받을 보수
i일에 마무리한 일에 대한 보수는 i+1일에 누적됨
*/
class pack{
int t;
int p;
pack(int t, int p){
this.t = t;
this.p = p;
}
}
public class boj_14501 {
static int n; //남은 n일
static pack[] arr; //주어지는 t, p 정보를 담은 배열
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException{
input();
solve();
/*
조건1: arr[i]의 t값 동안은 다른 상담 못함
조건2: 1일에 일한 돈은 2일차에 누적됨
*/
}
private static void solve(){
int[] dp = new int[n+1];
//dp[i] : i일까지 벌 수 있는 최대 수익
//dp[i+arr[i].t - 1] = 현재 i날에 잡힌 상담의 보수를 계산했을 때 끝난 날에 얻는 보수
//보수를 얻은 것은 상담이 끝나는 날인 i+arr[i].t -1 일에 기록됨
/*
i = 1인 경우, => 1일차에 잡을 수 있는 상담을 잡은 경우
arr[i].t = 3일이 걸리는 상담일때,
i+arr[i].t-1 = 3 => 3일차에 dp[3]에 보수 받음
dp [ i + arr[i].t - 1 ] 값은 보수를 안 받았을 때 보수 받을 예정인 날의 지금까지의 보수
dp[i-1] + arr[i].p 값은
: 현재 i일째의 잡을 수 있는 상담을 했을 때 받을 수 있는 보수 -> arr[i].p와
: dp[i-1] 지난 i-1날까지의 최대 보수
*/
for(int i =1 ; i<= n ;i++){
if (i + arr[i].t - 1 <= n){//보수는 최대 n일차까지 받을 수 있음
dp[i+arr[i].t -1] = Math.max(dp[i + arr[i].t - 1], dp[i-1] + arr[i].p);
}
if (i+1 <= n){
dp[i+1] = Math.max(dp[i], dp[i+1]);
}
}
System.out.println(dp[n]);
}
private static void input() throws IOException {
n = Integer.parseInt(bf.readLine());
arr= new pack[n+1];
int t = n;
StringTokenizer st;
int i = 1;
while(t-- > 0){
st = new StringTokenizer(bf.readLine());
int pack_t = Integer.parseInt(st.nextToken());
int pack_p = Integer.parseInt(st.nextToken());
arr[i] = new pack(pack_t, pack_p);//i일차에 잡을 수 있는 상담 정보
i++;
}
}
}dp문제로, dp배열에 대한 정의를 i일까지 벌 수 있는 최대 수익으로 정의하면 된다.
if (i + arr[i].t - 1 <= n)날짜에 대한 조건문
dp[i+arr[i].t -1] = Math.max(dp[i + arr[i].t - 1], dp[i-1] + arr[i].p);해당 점화식에서 맨 오른쪽 dp[i]가 아닌 dp[i-1]임을 주의하자. dp의 배열에 대한 정의는 정확히 dp[i]는 무엇이다라고 정의하자.
4/5
백준 14888
더보기
package 알고리즘_코딩테스트.dayone.apr05;
import java.util.*;
import java.io.*;
/*
2
5 6
0 0 1 0
30
30
----------
3
3 4 5
1 0 1 0
35
17
*/
/*
최댓값을 구할 경우
- 다음 /
+ 다음 x
최솟값을 구할 경우
+ 다음 %
- 다음 x
-----------
*/
public class boj_14888 {
static int n;
static int[] arr;
static long max = Integer.MIN_VALUE;
static long min = Integer.MAX_VALUE;
static int[] op = new int[4]; //덧셈, 뺄셈, 곱셈, 나눗셈
public static void main(String[] args) throws IOException{
input();
solve();
}
private static void solve(){
dfs(arr[0], 1);
System.out.println(max);
System.out.println(min);
}
private static void dfs(int num, int idx){//num은
if (idx == n){
max = Math.max(num, max);
min = Math.min(num, min);
return;
}
for(int i = 0 ; i < 4; i++){//연산자의 개수는 n-1개
//연산자 사용
if (op[i] > 0){
op[i]--;
int check = i;
switch (check){
case 0:{
dfs(num + arr[idx], idx+1);
break;
}
case 1:{
dfs(num - arr[idx], idx+1);
break;
}
case 2:{
dfs(num * arr[idx], idx+1);
break;
}
case 3:{
dfs(num / arr[idx], idx+1);
break;
}
}
//연산자 다시 복귀
op[i]++;
}
}
}
private static void input()throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bf.readLine());
arr = new int[n];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < n ; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < 4 ; i++){
op[i] = Integer.parseInt(st.nextToken());
}
}
}dfs문제이다.
- 한 가지 정점과 연결된 모든 정점을 탐색하는 경우
- 경로를 찾아야 되는 경우
- 사이클이 존재하는 경로 찾는 경우
첫번째 경우는 일반적인 dfs 알고리즘을 사용하면 된다.
void dfs(int v, int[] c){
c[v] = 1;
for(int a : adlist[v]){
if (c[a] == 0)
dfs(a,c);
}
}
/*
해당 지점을 방문 여부를 체크할 수 있는 배열을 선언한 뒤, 한 정점씩 방문 후 그 정점과 인접한 방문하지 않은 정점을 다시 재귀 호출
*/두번째 경우는 연결 요소를 찾는 것이 아닌 경로를 찾는 경우이다.
그렇기에 dfs를 약간 변형해야된다.
void go(int v, int[] c){
for(int a : adlist[v]){
if (c[a] == 1) continue;
c[a] = 1;
go(a,c);
c[a] = 0;//경로 찾는 것이므로, 다시 복귀 (백트래킹)
}
}위의 14888 문제의 유형이다.
마지막 세번째 경우는 사이클이 존재하는 경로를 찾는 문제이다. (https://www.acmicpc.net/problem/9466)
사이클이 존재한다는 것은 이전에 방문했던 곳을 다시 방문해 일종의 원형 반복이 생겼다는 것을 의미한다.
일반적인 dfs와 같은 경우, 방문했던 곳을 다시 방문하지 않는다. 그렇기에 dfs에 약간 변형을 주어야 한다.
백준 9466>
더보기
package 알고리즘_코딩테스트.dayone.apr05;
import java.io.*;
import java.util.*;
public class boj_9466 {
static int T;
static int n;
static int[] arr;
static int[] visited;
static int[] done;//팀 결성 못했든 했든 끝난 요소 체크
static int count = 0;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args)throws IOException{
input();
System.out.println(sb);
}
private static void dfs(int start){
if (visited[start] == 1){//방문했을 때
done[start] = 1;
count++;
}else{//방문 안했을 때
visited[start] = 1;
}
if (done[arr[start]] == 0){//팀 결성을 못한 경우
dfs(arr[start]);
}
visited[start] = 0;
done[start] = 1;//팀을 구했든 안 구했든 끝남
}
private static void solve(){
for(int i =1 ; i <= n ; i++)
if (done[i] == 0)
dfs(i);//start
sb.append(n-count).append("\n");
}
private static void input() throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(bf.readLine());
int i=1;
while(T-- > 0){
n = Integer.parseInt(bf.readLine());
arr = new int[n+1];
visited = new int[n+1];
done = new int[n+1];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int j=1 ;j <= n; j++ ){
arr[j] = Integer.parseInt(st.nextToken());
if(arr[j] == j){
done[j] = 1;//자기 자신
count++;
}
}
solve();
count = 0;//초기화
}
}
}참고: https://myeongmy.tistory.com/55
bfs문제의 경우도 잠깐 정리해보자.
- 최단 거리를 구해야하는 경우
- 최단 거리를 구하되 조건이 여러 개 존재하는 경우 (방문한 지점도 다시 방문 가능)
첫번째, 최단 거리를 구해야하는 경우는 일반적인 bfs 로 풀 수 있다.
void bfs(){
Queue<Integer> q = new LinkedList<Integer>();
int [] c = new int[n];
q.offer(1);
c[1] = 1;
while(!q.isEmpty()){
int a = q.poll();
for(int v: addlist[a]){
if (c[v] == 0){
q.offer(v);
c[v] = 1;
}
}
}
}코드트리로 넘어가자...
2015 하반기 1번 문제 <바이러스 검사>
단순히 몫과 나머지로 풀 수 있다.
private static void solve(){
long answer = 0;
answer += n;//필요한 팀장 더하기
for(int i = 1; i <= n; i++){
arr[i] -= gomsa[0];//팀장이 감시할 수 있는 사람 수 빼기
if (arr[i] > 0){
answer += (arr[i] / gomsa[1]);
int left = arr[i] % gomsa[1];
if (left > 0)
answer++;
}
}
System.out.println(answer);
}내가 푼 풀이는 좀 더 직관적이고, 해설에서는 좀 더 깔끔하게 정리되게 풀었다.
// 식당별로 필요한 최소 검사자 수를 검색합니다.
for(int i = 0; i < n; i++) {
// 팀장은 꼭 한 명 필요합니다.
ans++;
// 필요한 팀원 인원수만큼 더합니다.
ans += requiredMemberNum(customers[i] - leaderCapacity);
}
public static int requiredMemberNum(int customerNum) {
// 남은 고객이 없다면 검사 팀원은 필요가 없습니다.
if(customerNum <= 0)
return 0;
// 정확히 나누어 떨어지는 경우라면, 몫 만큼의 인원이 필요합니다.
if(customerNum % memberCapacity == 0)
return customerNum / memberCapacity;
// 나누어 떨어지지 않는 경우라면 1명이 추가적으로 더 필요합니다.
else
return (customerNum / memberCapacity) + 1;
}2016 하반기 1번 문제 <정육면체 굴리기>
펜필요 (집가서 풀기)
2017 상반기 오전 1번 문제 <테트리스 블럭 안의 합 최대화 하기>
이 문제는 가능한 모양을 모두 int[][][] blocks로 정의해서 완전탐색으로 푸는게 가장 간단하다.
다른 풀이도 (집가서) 보기 https://bono039.tistory.com/1013
4/6
백준 14891 톱니바퀴
시뮬레이션 회전 문제 (처음에 시계,반시계를 체크하는 배열, 12시 방향에 있는 인덱스를 저장하는 배열 등 너무 복잡하게 접근했다. 1번 문제는 간단하게!! 단순히 생각하자. 시간초과 안 나니까)
- 인풋에 대한 처리
0011 공백없이 주어지는 경우, charAt()사용
wheels = new int[4][8]; // 톱니바퀴 상태 입력
for (int i = 0; i < 4; i++) {
String s = br.readLine();
for (int j = 0; j < 8; j++) {
wheels[i][j] = s.charAt(j) - '0';
}
}- 과정 : 회전여부 저장 배열에 대해 한 번의 회전 횟수 묶음마다 회전 시뮬 돌리기
기준 톱니바퀴(j=0)에서 좌측을 비교할 수 있는 곳까지 비교하고 wheels[][6], wheels[][2]값이 다르면, isTurn배열 값 바꾸기
- 회전 직접 돌리기
// 반시계방향
private static void goBack(int n) {
int temp = wheels[n][0];
for (int i = 0; i <= 6; i++)
wheels[n][i] = wheels[n][i + 1];
wheels[n][7] = temp;
}
// 시계방향
private static void goTurn(int n) {
int temp = wheels[n][7];
for (int i = 6; i >= 0; i--)
wheels[n][i + 1] = wheels[n][i];
wheels[n][0] = temp;
}2016 하반기 1번 문제 <정육면체 굴리기>
cube[0] = 정육면체에서의 맨 아래 값 cube[1] = 정육면체에서의 오른쪽에 있는 값, cube[2] = 정육면체에서의 맨 위의 값, cube[3] = 정육면체에서의 왼쪽에 있는 값, cube[4] = 정육면체에서의 앞에 있는 값, cube[5] = 정육면체에서의 뒤에 있는 값
이렇게 정의하고 시뮬레이션 했는데, 테스트케이스는 잘 돌아간다. 그런데, 통과가 안된다. 반례를 찾아보자..
4/7
10971 외판원 순환
숨 좀 돌리자..
dfs 를 돌리는데, 시작 점으로 부터 다른 점으로 가는 방법이 여러 개니, 그 부분을 solve메서드에서 for문을 돌린다.
방문 안 한 점일 때,
- 방문 표시하고
- dfs(다음 방문 노드 인덱스, 갱신된 비용 합계, 갱신된 종료조건을 위한 변수)
이렇게 구성하면 된다.
/**
* start : 메서드 실행 전 위치
* now : 현재 내가 위치한 도시
* sum : 현재위치한 도시까지 사용한 비용
* depth : 1부터 n이 될때까지만 -> dfs 종료조건 변수
*/
private static void solve(){
for (int i = 1; i < n+1; i++) {
visited[i] = true;
dfs(i, i, 0, 1);
}
System.out.println(answer);
}
private static void dfs(int start, int now, long sum, int depth){
if (depth == n){
if (arr[now][start] != 0){
sum += arr[now][start];
answer = Math.min(answer, sum);
}
return;
}
for(int i = 1 ; i <= n ; i++){
if (!visited[i]){//방문안한 점이면
if (arr[now][i] != 0){
visited[i] = true; // 방문 함
dfs(start, i, sum + arr[now][i] , depth + 1);
visited[i] = false; // 방문 끝
}
}
}
}4/8
스타트 링크 14889
해당 문제도 dfs이다. 명수 중 n/2만 방문해도 팀이 정해지므로 이를 이용해 종료조건을 정의한다.
private static void combination(int depth, int start) {
if (depth == n / 2) {
calculateDiff();
return;
}
for (int i = start; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
combination(depth + 1, i + 1);
visited[i] = false;
}
}
}
private static void calculateDiff() {
int startTeam = 0;
int linkTeam = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (visited[i] && visited[j]) {
startTeam += arr[i][j] + arr[j][i];
} else if (!visited[i] && !visited[j]) {
linkTeam += arr[i][j] + arr[j][i];
}
}
}
로봇청소기 14503
4/11
2331 반복수열
ArrayList에 각 수를 P만큼 제곱한 값을 계속 추가하면서 어떤 수가 이미 ArrayList에 포함되어있다면, 그 수의 인덱스를 반환하면 되는 문제
int형 숫자에서 각 자릿수를 구하는 법
1. 나눗셈 연산을 이용해서 구하는 법
ArrayList<Integer> toseparate = new ArrayList<>();
while(num > 0){
toseparate.add(num % 10);
num /= 10;
idx++;
}2.문자열로 변환해서 구하는 법
int num = 12345;
String strNum = Integer.toString(num);
int[] arrNum = new int[strNum.length()];
for(int i = 0 ; i < strNum.length(); i++){
arrNum[i] = strNum.charAt() - '0';
}3. stram을 이용하는 법
int num = 12345;
int[] arrNum = Stream.of(String.valueOf(num).split("")).mapToInt(Integer::parseInt).toArray();아래 코드가 훨씬 더 깔끔
더보기
public class Main {
public static void main(String\[\] args) throws NumberFormatException, IOException {
BufferedReader br \= new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw \= new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st \= new StringTokenizer(br.readLine());
int A \= Integer.parseInt(st.nextToken());
int P \= Integer.parseInt(st.nextToken());
List<Integer\> list \= new ArrayList<\>();
list.add(A);
while (true) {
int temp \= list.get(list.size() \- 1);
int result \= 0;
// 어떤 수의 각 자리에 대해 P제곱만큼하여 각 자리를 더한 값을 구함.
while (temp !\= 0) {
result +\= (int) Math.pow(temp % 10, (double) P);
temp /\= 10;
}
// result가 이미 list에 포함되어있다면,
// 그 result가 가리키는 인덱스를 반환.
if (list.contains(result)) {
int ans \= list.indexOf(result);
bw.write(ans + "\\n");
break;
}
list.add(result);16964 DFS 스페셜 저지
현재 노드와 연결된 방문하지 않은 자식노드들을 set에 추가하고
각 자식노드에 대해서 set에서 삭제하면서 dfs를 수행하면 된다.
반드시 모든 점을 방문할 필요가 없다.
방문해야하는 순서가 주어지는 문제이므로, 해당 숫자가 dfs를 탐색할때 나오지 않는 경우 check = false처리해서 끝내면 된다.
private static void dfs(int cur){//-1 ,1, 1 //1, 3, 2
if (visited[cur])
return;
visited[cur] = true; //visited => false, true, false, false, false //visited => false, true, false, true,false
HashSet<Integer> sets = new HashSet<>();
//가능한 자식 노드를 모두 저장
for(int e : edge[cur]){//sets => 2, 3 //sets => nothing
if (!visited[e])//방문하지 않은 점이면
sets.add(e);
}
if (sets.size() == 0){
return;
}
while(! sets.isEmpty()){//자식노드들을 모두 방문할 때까지
if (sets.contains(suggest[++idx])){//자식노드 아래에 포함하고 있으면
sets.remove(suggest[idx]);//자식노드의 모든 걸 다 탐방
dfs(suggest[idx]);//dfs(3)
}else{
answer = false;
return;
}
}
}'기록 > 알고리즘' 카테고리의 다른 글
| upper bound, lower bound 이분탐색 (0) | 2025.03.30 |
|---|---|
| [알고리즘] union find 경로 압축 (0) | 2025.03.18 |
| [알고리즘] 1300 k번째 수 (0) | 2025.03.04 |
| [알고리즘] 2343 블루레이 만들기 (0) | 2025.03.03 |
| [알고리즘] 1167 트리의 지름 (0) | 2025.03.03 |