Definition of Seon

1. 문제 이 문제는 직사각형 종이를 한 변이 1인 직사각형 모양의 조각으로 잘라서조각 안의 수를 왼->오, 위->아래로 붙인 수의 합을 최대로 만드는 프로그램을 짜는 문제이다.특이점은 종이의 크기가 최대 4*4로 작다는 점이다.2. 풀이이 문제는 다양한 시도를 했으나 그만큼 실패를 많이 경험했다.처음에는 단순히 생각해서 그냥 가로로 쭉 자른 종이들의 합, 세로로 쭉 자른 종이들의 합,이 두 값을 비교해서 큰 값으로 하면 되잖아? 라고 생각했다.왜냐면 종이를 쭉 이어서 자르지 않고 막 조각내면 자릿수가 작아지니까.근데 이건 잘못된 생각이었다.문제에서 나온 예시와 달리 '0'이 들어가는 경우에 이상한 상황이 생긴다. 예를 들어서, 아래와 같은 종이조각 말이다.0023001299990011 1. 가로로 쭉 ..

백준 14391 종이조각 문제를 풀면서 메모리 초과가 계속하여 떴다.아무리 해도 해결이 되지 않아 검색해보니 비트마스킹이라는 새로운 방법을 쓰는 사람이 많았다.처음 듣는 방법이지만 메모리를 아낄 수 있는 방법이라 종종 쓸 일이 있을 것 같다. 비트마스킹특정 비트를 켜고 끄거나 반전시키기 위해비트 연산에 사용되는 데이터위키 백과에 따르면 비트마스크는 비트 연산에 사용되는 데이터로,다중 비트들을 싱글 비트 연산 작업에서 켜고 끄거나 상호 반전시킬 수 있다. 일단 비트 연산들을 알아보겠다.비트 연산자설명&AND (둘 다 1이면 1 반환)|OR (둘 중 하나라도 1이면 1 반환)^XOR (둘이 서로 다르면 1 반환)~NOT ( 1-> 0, 0->1 반전)left shift (지정한 수만큼 왼쪽으로 비트 이동)>..

- 2024년 4월 22일(월) ~ 5월 7일(화) 17시 : 지원서 접수- 2024년 5월 8일(수) ~ 5월 18일(토) : 에세이 제출- 2024년 5월 11일(토) 10시, 13시, 16시 SW적성진단(비전공자)- 2024년 5월 19일(일) 11시, 15시 코딩테스트(전공자)  지원서 접수작년부터 꿈꿔왔던 SSAFY 12기에 지원했습니다.변함 없이 늘 가고 싶던 곳이라 접수 오픈일 오전에 바로 접수해버리기는 했지만그래도 정보를 더 얻어보고자 오프라인 모집설명회도 다녀오고, 또 온라인 설명회도 다시 보고 그랬네요.지원서 접수 기간은 꽤 깁니다.그 안에 홍보도 많이 하는 것 같아요! 지원서 접수 화면에 들어가면 최종학력을 등록하게 됩니다.이때, 학점평균도 들어가야 하니 미리 알고 있으면 접수가 좀 ..

1. 문제 이 문제는 접두사X집합의 최대 크기를 구하는 문제이다.주어진 배열에서 어떤 단어가 다른 단어의 접두어가 되지 않는 부분집합을 만들어야 한다.단어의 개수는 최대 50이어서 숫자가 크지 않다. 2. 풀이접두어가 되려면 자신보다 길거나 같은 길이의 문자여야 하므로길이를 기준으로 짧은 길이부터 긴 길이 순으로 정렬을 했다.이후 이중 반복문을 사용하여 가장 짧은 단어부터 시작해 자기 자신 다음 단어부터 가장 긴 단어까지 확인한다.만약 단어 j를 i 단어의 길이 만큼 잘라서 i와 자른 j가 같다면 단어 i는 부분집합에 들어갈 수 없다. 직접 배열 자체에서 그 단어를 삭제하는 것도 방법이지만,결국 출력해야 하는 것은 크기 값 뿐이므로 ans 변수를 새로 만들어 겹치는 단어를 빼주었다.처음에는 n 자체를 변..

1. 문제2. 풀이[접근 1 - 수학적 접근..?]시간초과가 계속 났다 ㅠㅠx // 2 의 값보다 작은 수만 가지고 새 배열을 만들었다.여기에서 각각의 수를 x에서 뺀 값이 기존 배열에 있으면 개수를 추가!처음에 시간초과가 나고 시간을 줄이기 위해 시도한 것1. sys.stdin.readline 사용하기2. sort해서 배열의 x//2 번째 원소까지만 확인하기3. List 의 In 보다는 Set의 In이 더 시간복잡도가 낮기 때문에 set으로 바꿔주기 등등 방법을 시도하였으나 모두 시간초과가 발생했다.이건 알고리즘이 필요한 문제였던 거다ㅠㅠ [접근 2 - 투포인터]백준 문제 아래에 있는 알고리즘 보기를 눌러 투포인터라는 힌트를 얻어냈다.수열을 sort한 뒤에 왼쪽, 오른쪽 끝부터 시작해서 계속 포인터를 ..

1. 문제 이 문제는 스티커를 뗄 때 얻을 수 있는 최대 점수를 구하는 문제이다.그러나 스티커를 떼면 맞닿는 스티커들은 사용할 수 없어진다. 2. 풀이이 문제는 코테 스터디에서 시간을 정해두고 풀었다.20분 정도 소요되어서 풀었다.이전에 풀어봤던 dp 문제들 덕에 금방 풀이 방법을 생각해냈다. 스티커 배열을 입력받고 그것과 같은 형태로 dp 테이블을 초기화한다.자기 자신을 뜯을 경우에는 바로 왼쪽 칸은 뜯을 수 없고, 대각선에 있는 걸 뜯을 수 있다.그래서 자신 + 왼쪽 대각선을 뜯은 값과 왼쪽 칸을 뜯은 값 중 최댓값으로 dp 테이블을 갱신한다.마지막에는 모든 값 중 최댓값을 출력한다.3. 코드import sysinput = sys.stdin.readlinet = int(input()) #테스트케이스f..

1. 문제 이 문제는 호텔의 홍보 비용에 따른 고객 수 증가 정보를 가지고호텔의 고객을 c명 이상 늘이기 위해 투자해야 하는 돈의 최솟값을 구하는 문제이다. 2. 풀이[접근 1 - dfs] 시간초과처음에는 dfs를 활용하여 재귀 형태로 모든 경우의 수를 확인하도록 했다.모든 방법을 확인하다가 고객 수가 c 이상이 될 경우 최솟값을 갱신하고 return하는 형태이다.답을 찾는 데는 무리가 없었으나 시간초과가 떠버렸다.이에 시간을 줄일 수 있는 다른 방법을 고민했다. [접근 2- dp]목표 고객 증가 수인 c에다가 한 번의 투자로 늘어날 수 있는 최댓값인 100을 더해서 dp테이블을 만들었다.혹시 c보다 c+1이 더 비용이 적게 들 수도 있기 때문이다.dp 테이블은 모두 큰 수로 초기화해두고 반복문을 돌렸다..

1. 문제 이 문제는 팰린드롬 수를 찾는 문제이다.팰린드롬 수란 뒤에서부터 읽어도 같은 수이다.2. 접근숫자를 문자 형태로 받아온 뒤, 0인 경우에는 종료한다.나중에 출력할 결과를 same이라는 변수로 만들어 'yes'로 초기화해둔다.숫자길이의 절반, 즉 길이를 2로 나눈 수까지 반복문을 돌려서num[i]와 num[-i-1]이 같은지 확인한다.만약 다른 경우에는 same 변수를 'no'로 바꾸고 반복문을 탈출한다. 처음에는 이상하게 에러가 생겨서 각 변수를 출력해보다가,str에 개행문자 '₩n'이 맨 뒤에 포함되어 생기는 오류임을 발견했다!rstrip()을 추가하여 오류를 해결하였다!! 3. 코드import sysinput = sys.stdin.readlinewhile True: num = str(..

1. 문제 이 문제는 선수의 능력치를 고려하여 포지션을 정해 가장 최대의 능력치를 구하는 문제이다.11명의 선수들에 대해 11개 포지션에 대한 능력치를 수치화하여 제시한다.그 숫자들 중 모든 경우의 수를 고려하여 가장 최대의 합을 구하는 문제이다.즉, 전형적인 백트래킹 문제.2. 풀이솔직히 이 문제를 어떻게 풀어야 할지 감이 안 왔다.아직 알고리즘 실력이 부족하기 때문인 것 같다.어떤 상황에서 어떤 알고리즘을 써야 하는지 아직 잘모르는 것 같아서백트래킹 알고리즘을 다시 정리해야겠다고 생각했다.https://jemarque.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Backtrackin..

최근 코딩테스트 문제를 풀면서 알고리즘 정리가 필요함을 느꼈다.자주 출제되는데 아직 나에게 어려운 백트래킹을 먼저 정리해보려고 한다. 백트래킹 모든 경우의 수를 고려하는 알고리즘 백트래킹은 재귀를 활용해 모든 경우의 수를 확인하는 알고리즘이다.대표적으로 DFS, BFS를 사용하며 코딩테스트에서 잘 다루어지는 알고리즘이기도 하다.시간복잡도는 중복이 가능한 경우, N**2이고 중복이 불가한 경우는 N!이다. 목표한 조건에 도달하는 경우를 탐색하는 것인데,절대 목표에 도달할 수 없다고 판단이 되면 앞으로 돌아가서 다시 그 조건에 맞는 경우를 탐색한다. 1. DFS깊이 우선 탐색트리에서 바닥에 도달할 때까지 한쪽 방향으로만 내려가는 방식으로재귀함수를 사용하여 목표한 바가 나올 때까지 반복한다.일반적으로 모든 경..